olcott <NoOne@NoWhere.com> writes:

> On 4/5/2022 8:54 PM, Ben Bacarisse wrote:
>> 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.
>
> Then the exercise of doing it is of negligable benefit.

I think you would benefit from writing an actual TM, fully encoded. You
don't have to. I thought you were prepared to trust my experience
teaching this material.

>>>>>> (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.
>>
> The above is a system of reasoning such that the error of omission is
> impossible. It is the ultimate basis of all of my work.

I think we should put this to one side. I don't think this will help
you to specify and write E.

>>>>>>>> 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?
>>
> We can still keep pressing on.

OK.

> Ultimately the whole purpose of all of this is to simply achieve
> mutual understanding of a single English sentence, posted today.
>
>>>>>>> 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.
>
> Any talk of "representations" for a machine that only has single bits
> is ridiculous.

Yes. No one is talkig about that (though your use of "machine" and
"bit" is open to misinterpretation).

> I simply always refer to the input as a string of characters
> of some alphabet.

I don't know why you brought up any else. Did you think I was talking
about anything but a string of symbols over some alphabet?

(I prefer to avoid "character" -- TMs operate on abstract symbols.)

>>>>>> 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?
>>
>
> "S" obviously as I have already done.

So you specification

E.q0 S ⊦* E.qy if S
E.q0 S ⊦* E.qn otherwise.

I don't think that's what you meant.

>> 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.
>
> A decider has some finite string of characters of some alphabet as its
> input.

And I hope we'll get to that, but it's not going fast so far.

>> 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.
>>
>
> Here is something that actually makes no sense:
> 0i8hwedfiubzX79jodsf-r., lk-9asdf-9ysewrfo in2weklojc

indeed.

> I forgot to move to the last tape element of the finite string.
> E.q0 S ⊦* E.qy if S represents an even number
> E.q0 S ⊦* E.qn otherwise.

Yeah! That's a good forst stab at it. I'd have preferred you to say
what representations are to be considered (as I did for P), but I'll
take it.

>>>>>> Now actually write out, in full, a TM that meets your specification.

> I have already fully specified E,
> Do you think that I can't possibly code it correctly?

I don't know. The point of the exercises is to get a deeper
understanding of what TMs are. Writing a few is essential.

>> Shall I just wait a bit longer? Is there anything you need to ask?
>
> I have already fully specified E,
> Do you think that I can't possibly code it correctly?

I don't know. Can you?

--
Ben.