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

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. U(V,V) cannot correctly resolve this paradox to give a correct report. It is this contradiction that demonstrates that some functions are incomputable. Note the nature of the contradiction. We assumed the existence of a perfect U and deduced from it a program that U cannot correctly decide upon. That is, no universal decider can exist.
To overturn the proof would require the construction of a perfect U. (Don't hold your breath.)
<snip>
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within