Re: How do computations actually work?

On 5/25/25 5:39 AM, Richard Heathfield wrote:

On 25/05/2025 10:14, Mikko wrote:

On 2025-05-24 15:18:57 +0000, olcott said:

 <snip>
 

All termination analyzers are required to report on the
behavior that their input finite string specifies.

>
To report correctly. Though the input string to a termination analyzer usially is incomlete: the input string usually
specifies different behavours depending on the input that is
not shown to the termination analyzer, and the analyzer's
report must cover all of them.

  I think 'input string' is ambiguous here.
 It would be clearer if people used 'program string' if they mean the program whose halting behaviour is being investigated and reserved 'input string' for when they mean the data - that is:
 The analyser must determine whether the program string would terminate if applied to the input string.

But the string given *IS* the input to the analyzer. Turing Machines have two parts, the "State Machine", and the "Input String".
Note, that only Halt Deciders (or similar deciders) have this confusion, not Termination Analysers (since Olcott doesn't understand what that term means), With Halt Deciders, and other "Program Deciders", the input to the decider is a single string which represents both the program and its input string. In this case both are generally given name.
Note, Termination Analysers don't have the second string, as they are supposed to determine the harder problem of determining if the program will halt for ALL possible inputs, not just one given one.

 Clearer still would be to drop 'string' and set up a couple of unambiguous aliases:
 The analyser must determine whether program P would terminate if applied to input tape T.

But, as PO has pointed out, you can't DIRECTLY give a Turing Machine a "program P", it only tasks as its input, the tape, which has a finite string from a finite alphabet.
A Turing Machine isn't a finite string, and thus you can't directly give it a prograom, but need to "represent" or "describe" that program, a step he seems to not to understand.
This is just like Turing Machines can't add "numbers", as a Number isn't a finite string of finite characters either, it is just a concept.  The difference is that we regularly write down the representation of numbers, so we something think of that as "the number", but it isn't.
This is like the number we call 12, can be written as 12 in base ten, or 0x0C in Hexidecimal, or 1100 in base 2, and the fact that we can write in differently in different bases shows that the string representation isn't the number its self, just its representation.
Just like some good representations of a program would be its source code or it final object code. But then Olcott forgets that Programs need to be COMPLETE, and then tries to define a fragment as if it was a full program.

 In the above, requoted here:
  > To report correctly. Though the input string to a termination
 > analyzer usially is incomlete: the input string usually
 > specifies different behavours depending on the input that is
 > not shown to the termination analyzer, and the analyzer's
 > report must cover all of them.
 I can't decide which 'input string' means P and which means T.
 

The key point here is that the definiton of a Termination Analyzer is a machine that decides if the program described by its input will halt for ALL posssible inputs to it, thus the only "input string" that it sees is the representation of the program. The various inputs strings to the program are not specified.
In real analysis, everything is given a name, which resolves the ambiquity.