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:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 4/4/2022 11:23 AM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 4/4/2022 10:32 AM, Ben Bacarisse wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 4/4/2022 5:14 AM, Ben Bacarisse wrote:
>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>>>>>>>>>>
>>>>>>>>>>>> It might be time to skip ahead because the next exercise is to do the
>>>>>>>>>>>> same for P, a TM that decides if a string encodes a prime number. Can
>>>>>>>>>>>> you think of how to specify that without giving an algorithm?
>>>>>>>>>>>> P.q0 ??? ⊦* P.qy if ???
>>>>>>>>>>>> P.q0 ??? ⊦* P.qn otherwise.
>>>>>>>>>>>> (The three ??? won't all be the same things.) Any idea how to flesh
>>>>>>>>>>>> this out? If you can, you will be able to do it for E very easily too.
>>>>>>>>>>>
>>>>>>>>>>> P.q0 S ⊦* P.qy if Is-Prime-Number(S)
>>>>>>>>>>> P.q0 S ⊦* P.qn otherwise.
>>>>>>>>>> That's getting close. We know, from how the notation works, that S is a
>>>>>>>>>> string of symbols in the TM's alphabet. But writing Is-Prime-Number(S)
>>>>>>>>>> suggests that is not natural language. That's a very hard route to go
>>>>>>>>>> down. I'd have to ask you for the definition of Is-Prime-Number.
>>>>>>>>>> Defining it symbolically is messy and if the definition is /not/ formal,
>>>>>>>>>> dressing the definition up with a formal-looking name is just
>>>>>>>>>> superficial.
>>>>>>>>>
>>>>>>>>> It goes through some tedious steps to see if it is a prime number:
>>>>>>>>>
>>>>>>>>> A prime number is a natural number greater than 1 that is not a
>>>>>>>>> product of two smaller natural numbers.
>>>>>>>> We've hit a bit of a road-block rather sooner that I had expected.
>>>>>>>> First off, there's no need to define what a prime number is. If at some
>>>>>>>> point it turns out that your readers do not know, go ahead and define
>>>>>>>> it, but it's too widely understood by comp.theory readers to bother
>>>>>>>> about.
>>>>>>>> But writing (as I think you are suggesting)
>>>>>>>> P.q0 S ⊦* P.qy it goes through some tedious steps to see if it is a
>>>>>>>> prime number
>>>>>>>> is not really adequate. There are two 'it'. To what do they refer?
>>>
>>> The TM determines that S is a prime number.
>> Saying "P" rather than "the TM" is simpler. The first 'it' refers to
>> P. The second 'it' refers to the string S. But being prime is a
>> property of numbers not strings.
>>
>>>>>>>
>>>>>>> You told me to make sure that I do not provide an algorithm.
>>>>>> Yes, that good. You didn't.
>>>>>> Now, to what do the two 'it's refer?
>>>>
>>>> OK, maybe things have gone too far already, but why are you ignoring my
>>>> questions? Your phrase used 'it' twice. What did you intend to refer
>>>> to by these two pronouns? It was not an idle question. I think when
>>>> you answer it, at least one problem will become clear.
>>>
>>> Andre thought that you were simply looking for English:
>>> "p is a prime number"
>> I didn't read that sub-thread.
>>
>>>>>>> This is somewhat algorithmic:
>>>>>> No, no. The non-algorithmic way is best. You should be able to
>>>>>> specific what a computation does even when yo have no idea how to write
>>>>>> the an algorithm to do it. Sometimes there isn't ad algorithm!
>>>>>>
>>>>>>>> and nothing in P.q0 S ⊦* P.qy is a number so there is nothing there to
>>>>>>>> be a prime number.
>>>>>>>> Can you see how you (a) make it shorter, (b) make it clearer?
>>>>>> My reply has three questions in it (depending on how you count) but you
>>>>>> didn't answer any of them. This will only work if you try to answer
>>>>>> these questions. Sometimes the answer will be "I don't know what you
>>>>>> mean", but that's a perfectly good answer.
>>>>>
>>>>> Anything besides the bare function name is somewhat algorithmic so
>>>>> what you are asking for seems impossible.
>>>> 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.

Aside: TMs are often specified to operate on numbers in unary notation
because it is so simple. One is represented with a single symbol (any
symbol can be chosen) "X". Two by two of them "XX", three by three of
them "XXX" and so on.

>>>> It's easy to assume conventions from everyday life that should be stated
>>>> explicitly. You must have come across this in software: "the manual
>>>> said the input should be a number but it went wrong for सहस्र."
>>>> Finally, don't fuss about the prime bit. Just use the word prime.
>>>> Everyone one knows what it means. The key thing here is to state /what/
>>>> must be prime for P to correctly accept a string.
>> You will need to find a way to describe what symbols can be in the
>> string and what the resulting strings mean.
>>
>
> The algorithm already does that.
> The ultimate semantics of the data is the algorithm.

(1) How will you specify what's needed in those cases where you don't
know an algorithm to solve the problem?

(2) Algorithms are usually many orders of magnitude more complex than
specifications.

(3) Have you never specified the expected behaviour of function or
subroutine before? I thought your background was in software
engineering. A function is rarely specified by giving the algorithm.
Look up and standard C function and you'll find something like this:

NAME
sqrt, sqrtf, sqrtl - square root function

SYNOPSIS
#include <math.h>

double sqrt(double x);
float sqrtf(float x);
long double sqrtl(long double x);

DESCRIPTION
These functions return the nonnegative square root of x.

No algorithm in sight.

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

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

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.

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

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

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.

Now actually write out, in full, a TM that meets your specification.
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.

Once you've written a TM, we can look at the main topic: talking about
TMs that decide things about TMs.

--
Ben.