Re: Turing Machine computable functions apply finite string transformations to inputs VERIFIED FACT

Richard Heathfield <rjh@cpax.org.uk> writes:

On 29/04/2025 11:00, joes wrote:

Am Mon, 28 Apr 2025 21:50:03 -0500 schrieb olcott:

On 4/28/2025 3:13 PM, Richard Heathfield wrote:

 

What matters is whether a TM can be constructed that can accept an
arbitrary TM tape P and an arbitrary input tape D and correctly
calculate whether, given D as input, P would halt. Turing proved that
such a TM cannot be constructed.
This is what we call the Halting Problem.
>

Yet it is H(P,D) and NOT P(D) that must be measured. Computer science
has been wrong about this all of these years. When I provide the 100%
concrete example of the x86 language there is zero vagueness to slip
through the cracks of understanding.

No, H gets P(D) as input, not itself. H is the "measurer", not being
measured.

>
Mr Olcott has contradicted you, and even though he's wrong about almost
everything else I don't think he's wrong about this.
>
Let's drop HHH and DD and so on, and stick to:
>
U is a universal termination analysis program, taking two tapes, P and
D. If P(D) would halt, U(P,D) returns true; else false. No matter what
program P is, U always reports either true or false, and never makes a
mistake.
>
P is an arbitrary (but syntactically correct) program.
>
If we can write U, it's easy enough to write V, which differs from U only
in that instead of reporting, V reacts to an unending program by halting
and to a halting program by looping forever.
>
Then we make two copies of the V tape and ask V about itself. What would
U(V, V) tell us?
>
U (my universal analogue of Mr Olcott's H^3) doesn't get V(V) as its input,
but V and V. U(V(V)) would suggest that V(V) is executed and the result
passed to U, but in fact there is no need to execute V if the analysis can
be performed statically.
>
Whether it's executed or not, however, the answer is that V(V) halts only
if it doesn't and loops forever only if it doesn't.

You've added a problem that should not be there. Your U is a two-tape TM
and so therefore is V.  U(P,D) reports on the halting of P(D) but U(V,V)
is ill-defined because V(V) is not a two-tape computation.  Even P(D) is
not well-formed because what does it mean to apply a tape to a tape?
(Yes, I know P(D) means the execution of the TM encoded on the tape P
when run on tape D but this should be spelled out.)

The proof is simpler to get right if all the models are the same: U is a
one-tape TM decider of one-tape computations.  And we should clearly
distinguish between TMs, encodings of TMs and encodings of TM/data
pairs.  Many years ago I urged PO is use a notation such as:

  P     A Turing machine with some alphabet Sigma.
  P(i)  The computation that results from P running with initial tape i.
  [P]   the encoding of a TM in the alphabet Sigma.
  <x,y> the encoding of a pair of strings over Sigma using only symbols
        in Sigma.

A halt decider, H, would then be a TM (over Sigma) that accepts all
inputs of the form <[P],d> where P(d) halts and that rejects all other
inputs.

But then PO never really understood TMs and soon ditched them altogether
in favour of a model of computation that, ironically, has decidable
halting!  Mind you, despite his IO-free x86 model having decidable
halting, he has not demonstrated halt decider for it.  (Aside: I don't
mean that a halt decider is possible in the model, just that halting in
his model is TM-decidable.)

--
Ben.