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

Op 01.mei.2025 om 05:38 schreef olcott:

On 4/30/2025 7:53 PM, Ben Bacarisse wrote:

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

 It never has been my misunderstanding.
It  is that everyone else was not acutely
aware that inputs my bed transformed into output
by a specific set of transformation rules.
 When Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
 (a) Ĥ copies its input ⟨Ĥ⟩
(b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
(c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
(d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩
(e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
(f) simulated embedded_H simulates ⟨Ĥ⟩
(g) goto (d) with one more level of simulation
 There is no way that ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated
by embedded_H can possibly get to ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.
THEREFORE THE INPUT TO embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ DOES NOT HALT.
Linz is using the wrong measure.
 

For a simulator that does not abort, your analysis is correct.
But that simulator exists only in your dreams. Your simulator contains Halt7.c, which shows that it does abort.
What happens when we use another simulator, that aborts?
Then we need to forget about the simulator that does not abort.
(That seems very difficult for Olcott. He keeps dreaming of the simulator that does not abort.)
We can then forget about the above analysis, because now we can construct another program, containing another embedded_H, that also aborts.
That completely changes the analysis, because now the embedded_H will abort at (c) and therefore the 'goto' in (g) happens only a finite (0-N) number of times.
THEREFORE THE INPUT TO embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ DOES HALT.
Linz is using the correct measure.
But Olcott is using the wrong measure, because when he changes the simulator to have an abort, he forgets to use the embedded_H that also aborts. In this way he misses the point of Linz.