The key mistake of the Peter Linz HP proof

[olcott]

In computability theory, the halting problem is the
problem of determining, from a description of an arbitrary
computer program and an input,

whether the simulation of this program must be aborted to
prevent it from running forever.

The above criteria is valid on the basis of the known equivalence
between the direct execution of a computation and its simulation
by a UTM. The same criteria universally works on all inputs allowing
their halting status to be correctly decided.

The Peter Linz H is defined to be a simulating halt decider that applies
the above criteria and the halt decider at Ĥ.qx is an exact copy of H.

Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ halts, and

Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

The mistake of the Linz proof is forming a conclusion
based on Ĥ applied to its own Turing machine description ⟨Ĥ⟩.

This is only answering the question:
Can changes be made to an otherwise correct halt decider
such that this halt decider is no longer correct?

The required question is:
Does the original H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decide the halt status
of its input?

Yes the original H does correctly decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩

This is proved in section V3 of my paper by the analogous example of:
int main() { H1(P,P); } // analogous to H applied to ⟨Ĥ⟩ ⟨Ĥ⟩

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

The full Linz Proof:
https://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

[olcott]

On 9/4/2021 5:50 AM, Richard Damon wrote:
> On 9/3/21 10:13 PM, olcott wrote:
>> On 9/3/2021 8:53 PM, Richard Damon wrote:
>>> On 9/3/21 9:18 PM, olcott wrote:
>>>> On 9/3/2021 8:05 PM, Richard Damon wrote:

>>>>> So, do you claim H1 is the SAME computation as H, and thus neither is
>>>>> actually a computation as the same computation can't give two different
>>>>> answers to the same input.
>>>>>
>>>>
>>>> I claim that H1 has identical machine code as H.
>>>> Their execution order makes them distinctly different computations.
>>>>
>>>> H1 can see that H(P,P) aborts the simulation of its input.
>>>> H(P,P) cannot see anything that aborts the simulation of its input.
>>>>
>>>> This execution sequence order makes them distinctly different
>>>> computations.
>>>>
>>>> This is exactly the same as the when the original Linz H is applied to
>>>> ⟨Ĥ⟩ ⟨Ĥ⟩.
>>>
>>> IF H1 is a different computation than H, then the fact that it can get
>>> the answer right doesn't matter, as it wasn't the computation that H^
>>> was built on.
>>>
>>
>> The Linz Ĥ is only required to have an exact copy of the Linz H at Ĥ.qx.
>> It turns out that using my simulating halt decider criteria H would
>> correctly report that its input ⟨Ĥ⟩ ⟨Ĥ⟩ halts.
>
> Not quite, you are missing the meaning of words here. H was supposed to
> be a Turing Machine, an exact copy of a Turing Machine will behave
> identically to the original. This is a fundamental property of being a
> Computation, if you make an exact copy of the algorithm, you will get
> the identical behavior.
I have empirically proved that this is merely a false assumption.
int main() { H1(P,P); } sees a different execution trace than H(P,P).

In the first case we have a halt decider that sees another halt decider
abort the simulation of its input.

In the second case we have a halt decider that does not see another halt
decider abort the simulation of its input.

The execution order of with H1 before H derives a different execution
trace for H1 than for H.

H1 is an identical copy of H and has different behavior than H because
its execution trace input is different than H.

[olcott]

On 9/4/2021 9:18 AM, Richard Damon wrote:

> Since Execution Trace is NOT defined as an input to that Computation
> (the only inputs are the representation of the machine and its input),
> the dependency of the result on that just proves that H and H1 are not
> properly Computation, and thus not eligable to be a Decider.
>
> PERIOD. DEFINITION.

The input to the halt deciders is their different execution trace thus
the halt deciders are a pure function of their input.

> H is NOT the Computational Equivalent of the Turing Machine it is
> claimed to be, as that machine would be Computation (as Turing Machines,
> but structure HAVE to be), so you argument fails at line 1 when you make
> that claim.
>
> You clearly do not understand the meaning of Computation as used in the
> field you are trying to muddle in.

[olcott]

On 9/5/2021 4:37 AM, Alan Mackenzie wrote:
> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>> Richard Damon <Ric...@Damon-Family.org> writes:
>
>>> On 9/4/21 2:13 PM, olcott wrote:
>>>> On 9/4/2021 1:04 PM, Alan Mackenzie wrote:
>>>>> [ Malicious cross posting snipped. ]
>
>>>>> In comp.theory olcott <No...@nowhere.com> wrote:
>
>>>>>> .... valid on the basis of the known equivalence between the direct

>>>>>> execution of a computation and its simulation by a UTM.
>

>>>>> Not really.  There might well not be a simulation of the program.
>
>>>> I am stopping here. If it is impossible to simulate the TM description
>>>> of a TM then it is not a proper TM.
>
>> I am pretty sure he is referring to the unwarranted assumption that any
>> simulation at all is involved.
>
> Thanks, Ben, that's exactly what I was trying to say. Apologies to PO
> for being unclear, here.

Yet the point that I am making is that when a simulating halt decider
applies this criteria to its input:

whether the simulation of this program must be aborted to
prevent it from running forever.

Then the Peter Linz H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decides that its
input halts and transitions to H.qy on the basis of Ĥ.qx applied to ⟨Ĥ⟩
⟨Ĥ⟩ correctly decides that its input does not halt and transitions to Ĥ.qn.


>
>> The context has been lost, including the key part that Alan was
>> objecting to:

>
>> || In computability theory, the halting problem is the
>> || problem of determining, from a description of an arbitrary
>> || computer program and an input,
>> || whether the simulation of this program must be aborted to
>> || prevent it from running forever.
>

>> The phrase "the simulation" implies there is simulation involved. Had
>> PO written "whether /a/ simulation of this program runs forever" the
>> reference to simulation would be silly and superfluous, but not wrong.
>
>> --
>> Ben.