olcott <NoOne@NoWhere.com> writes:

> On 4/5/2022 9:40 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 4/4/2022 7:57 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 4/4/2022 6:14 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 4/4/2022 2:51 PM, Ben Bacarisse wrote:

>>>>>>>> Here's a supporting exercise. Write down at least half a dozen strings
>>>>>>>> that might be passed to P. At least one of them should be a string that
>>>>>>>> P must accept and at least one must be a string the P should reject, but
>>>>>>>> you should say, for each one, whether P accepts of rejects it.
>>>>>>>
>>>>>>> (is prime?)
>>>>>>> 1 yes
>>>>>>> 2 no
>>>>>> 2 is prime, 1 is not. I'll assume this is a typo.
>>>>>>
>>>>>>> 3 yes
>>>>>>> 4 no
>>>>>>> 5 yes
>>>>>>> 6 no
>>>>>>
>>>>>>>> Be prepared for me to raise questions about what the strings
>>>>>>>> represent.
>>>>>> So what about the following strings:
>>>>>> 0x11
>>>>>> IX
>>>>>> nineteen
>>>>>> 1001
>>>>>> सहस्र
>>>>>> ?
>>>> You commented on only one of these.
>>>>
>>>>> I would simply make tape elements UTF-32.
>>>> (1) UTF-32 (both of them!) are transfer encodings and TMs work on
>>>> abstract symbols. The encoding of the symbols is immaterial.
>>>> (2) You could define the tape alphabet to includes all Unicode symbols
>>>> but there is no point. You need no more the one symbol to represent any
>>>> number, so that would be adding unnecessary complexity.
>>>
>>> Less than two seems too counter-intuitive, thus cumbersome.
>> But this is just because you have not yet written a TM. For many tasks,
>> unary makes the TM much simpler -- by an order of magnitude in many cases.
>>
>
> OK.
>
>>> Complexity is not the size of the encoding it is the mental effort
>>> required to achieve complete understanding.
>> For numerical problems there is less mental effort involved with unary.
>> That's why tally sticks can be found dating from the Palaeolithic.
>>
>
> OK.
>
>>>> Aside: TMs are often specified to operate on numbers in unary notation
>>>> because it is so simple.
>>>
>>> The notation is simple making the algorithm more complex.
>> No. This exercise will help you see why that is not true:
>> Write a TM that adds two numbers. The input will be strings of the
>> form {n}+{m} where {x} is the unary representation of x. The TM
>> should halt with only {n+m} on the tape.
>>
>> Now do the same where the numbers are represented in the usual decimal
>> notation.
>
> I was referring to the difference between binary and unary.

The same is true for binary. But you'd know this if you'd tried. Does
this mean you are not going to try?

>> The first part is easy and you should definitely do it, especially as
>> the "even" decider is proving too big a step. This adder is easier to
>> write than E.
>
> What is there to an binary E decider besides verifying that the last
> digit is a 0 ?

Almost nothing. What's holding you up? I am having trouble seeing how
I can help.

>>>> (2) Algorithms are usually many orders of magnitude more complex than
>>>> specifications.
>>>
>>> With a mapping between many levels of abstraction complexity remains
>>> pretty constant. Every element at every level only has very few parts.
>>
>> But when there is no algorithm? All you have is the top-level
>> specification of what is wanted. Would you like me to set an exercise
>> consisting of a problem for which you won't be able to find an
>> algorithm?
>
> If a problem has no solution then cateogorically exhaustive reasoning
> will determine that the category where a solution could be found does
> not exist.

I can't make head or tail of this. Without a specification there is no
defined decision problem.

>>>>>> Since this is taking way longer than I had thought, you can just ask me
>>>>>> how I'd do it and you can see if you agree or not.
>>>>>
>>>>> Anything that you think is best.
>>>> In my experience, people learn best when they solve problems on their
>>>> own with a little help, but since I'm not sure why this is proving so
>>>> hard for you, I don't know what help you need.
>>>
>>> Basically what I am doing is structured programming that has been
>>> elaborated 1000-fold more robust. I think in terms of multiple levels
>>> of hierarchies thus able to organize enormous complexity as simple
>>> connections between simple things.
>> That does no explain why you have not yet been able to specify a simple
>> TM like P.
>
> The way that you frame things mentally is not the same way that I
> frame them mentally.

Do you mean you may not be able to do these exercises?

>>>>> I think that we are finally on a path of full mutual dialogue.
>>>> I had hoped you would be able to specify a simple TM by this time, but
>>>> you are struggling with that task. I'll show you what I'd write for you
>>>> to comment on, but I don't think that's the best way for you to learn.
>>>> My first stab at it might be:
>>>> P.q0 S ⊦* P.qy if S is prime, and
>>>> P.q0 S ⊦* P.qn otherwise.
>>>> No good because S is a string not a number. Another go:
>>>>
>>>
>>> Ultimately the entire set of human knowledge is merely string transformation rules.
>>>
>>>> P.q0 S ⊦* P.qy if the number represented by S is prime, and
>>>> P.q0 S ⊦* P.qn otherwise.
>>>> Much better. But this does not say exactly what the representation
>>>> should be. How about this:
>>>> P.q0 S ⊦* P.qy if S is the conventional binary representation of a
>>>> prime number, and
>>>> P.q0 S ⊦* P.qn otherwise.
>>>>
>>>
>>> This is good we keep making headway.
>>>
>>>> It's still not watertight but it covers all the important bases. The TM
>>>> should reject "nineteen" and "2001" but must accept "10" and
>>>> "100000000000000000111".
>>>
>>> If we only have binary digits then "Hello how are you?" would be
>>> construed as a binary integer that must be tested.
>>
>> That depends on the TMs alphabet. If it includes such symbols then of
>> course the TM must test that string. But, in my experience, students
>> are clever at reducing work. When asked to write a TM they will pick an
>> alphabet that makes the task as simple as possible.
>
> When we have the typical single bit alphabet representation cannot
> possibly be an issue because there is only a single representation for
> everything a finite string of "1".

I don't think you understood what I was saying here. One problem I see
is that you are asking me far fewer questions than I would have
expected. If you don't know what I am asking for, asking me for
clarification is the simplest solution.

>>>> What I had hoped to be the lesson from this is that the starting point
>>>> when asking if some set is decidable is an agreed representation for
>>>> instances (in this case just numbers). Once we have that we will be
>>>> prepared to be lax and say things like "the prime numbers are a
>>>> decidable set" even though it's really "here is a mapping between
>>>> strings and numbers such that there is a TM that accepts only those
>>>> strings that map to prime numbers".
>>>
>>> That is why I started with ASCII digits.
>>
>> I don't see a connection between the paragraph I write and this remark.
>> When that happens (as a teacher) I worry that you have not understood
>> the paragraph. Normally, I'd ask a few question to see if the student
>> had understood, but that's no ideal using Usenet. I propose to press on
>> assuming you did understand.
>
> OK
>
>>>> So, next exercise. Go back to E. Specify how you want the "problem
>>>> instances" (the numbers) to be represented and then specify the TM in a
>>>> similar way to the way I did for P:
>>>> E.q0 S ⊦* E.qy if ???
>>>> E.q0 S ⊦* E.qn otherwise.
>>>
>>> If S in {0,2,4,6,8} then E
>> Hmm... Not sure what the problem is here. What should you write in
>> place of the ??? to make the specification of E clear.
>
> I put a variable name as a placeholder for a string of characters.

What should you write in place of the ??? to make the specification of E
clear?

I am at a loss as to what the problem is. There is a key issue about
what a decider is deciding and that requires accurate specification.
It's not just an issue with toy problems like this, it's an issue for
you in regard to a halt decider too.

You really need to specify E as I specified P for you. As far as I can
see you are suggesting this:

E.q0 S ⊦* E.qy if S in {0,2,4,6,8} then E,
E.q0 S ⊦* E.qn otherwise.

but that makes no sense.

>>>> Now actually write out, in full, a TM that meets your specification.
>>>
>>> This is merely a finite state transition table
>>> NextState = States[Current_State][Current_Input]
>>> combined with some tape head moves.
>>>
>>> When we use ASCII digits then we can have the single BLANK delimiter.
>>> To closest thing that I can refer to that might help you understand is
>>> a layered architecture.
>>>
>>> https://en.wikipedia.org/wiki/Multitier_architecture Each layer is not
>>> too complex. The interface between layers is not too complex. My
>>> specifications are in this same kind of hierarchy.
>>
>>>
>>
>> Would it help to start with a simpler TM? This is the one I used to use
>> in class, but I am sure there are simpler problems I could find. I
>> could also help by suggesting a representation for numbers that will
>> make the task easier than your choice of decimal.
>
> OK

OK what? You want to start with a simpler TM than E, or you want me to
suggest a simper representation that decimal? Maybe both?

A simpler TM than E... Let me see... I think the unary adder from
earlier is a bit simpler, certainly than a decider for decimal even
numbers. But then the second suggestion would be to use either unary or
binary for E (rather than you suggested decimal) and that makes almost
trivial.

>>>> You can make up any notation you like to write out the state transition
>>>> function, but you might consider using the TM simulator you found
>>>> before. That way you could actually test your TM in some sample inputs.
>>>
>>> I have two patents on DFAs.
>> Right. Not sure what do with the information.
>
> I know state transitions better than most people with a CS degree.

That does not seem to be helping you and I am running out of ways to
make it simpler.

>> Shall I just wait, or do you think I might be able to help you along
>> with this exercise?
>
> http://www.lns.mit.edu/~dsw/turing/examples/addbin.tm

Now I am baffled. What do you want me to do with that example?

Shall I just wait a bit longer? Is there anything you need to ask?

--
Ben.