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.

>>>>> (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.

>>>>>>> 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.
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. I simply always refer to the input as a string of characters
of some alphabet.

>>>>> 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.

> 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.

> 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

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.

>>>>> 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.
>

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

>>>>> 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?
>

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

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer