Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.software-eng > #3121 > unrolled thread

Re: Halting Problem proofs appear to be bogus!

Back to article view | Back to comp.software-eng

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:13 -0500
    Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-19 10:10 -0500
      Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-20 09:24 -0500

#3121 — Re: Halting Problem proofs appear to be bogus!

On 7/16/2021 8:34 AM, Ben Bacarisse wrote:
> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
>> All extant halting problem proofs appear to be predicated on a
>> misunderstanding of the following contradiction:
> 
> I don't think you've read any actual proofs, let along all of them.  Why
> you would even say such a thing?
> 
>> 	Suppose T[R] is a Boolean function taking a routine
>> 	(or program) R with no formal or free variables as its
>> 	argument and that for all R, T[R] — True if R terminates
>> 	if run and that T[R] = False if R does not terminate. Consider
>> 	the routine P defined as follows
>>
>> 		rec routine P
>> 			§L :if T[P] goto L
>> 		Return §
>>
>> 	If T[P] = True the routine P will loop, and it will
>> 	only terminate if T[P] = False. In each case T[P] has
>> 	exactly the wrong value, and this contradiction shows
>> 	that the function T cannot exist.
>>
>> 	[Strachey 1965]
>>
>> T is indeed unable to decide P but for the wrong reason: T[P] is
>> recursive
> 
> T[P] is not recursive.  Maybe you don't understand what the CPL means?
> 
> Further, this argument must fail for any of the actual proofs that are
> based on Turing machine because TMs have not functions, not calls and no
> recursion.
> 
Peter Linz Ĥ applied to the Turing machine description of itself: ⟨Ĥ⟩

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

When we hypothesize that the halt decider embedded in Ĥ is simply a UTM 
then it seems that when the Peter Linz Ĥ is applied to its own Turing 
machine description ⟨Ĥ⟩ this specifies a computation that never halts.

Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥx⟩ then Ĥ0.qx simulates this input with 
the copy then
Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥy⟩ then Ĥ1.qx simulates this input with 
the copy then
Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥz⟩ then Ĥ2.qx simulates this input with 
the copy then ...

This is expressed in figure 12.4 as a cycle from qx to q0 to qx.

Within the hypothesis that the internal halt decider embedded within Ĥ 
simulates its input Ĥ applied to its own Turing machine description ⟨Ĥ⟩ 
derives infinitely nested simulation, unless this simulation is aborted.

Self-Evident-Truth (premise[1])
When the pure simulation of a machine on its input never halts we know 
that the execution of this machine on its input never halts.

Self-Evident-Truth (premise[2])
The ⟨Ĥ⟩ ⟨Ĥ⟩ input to the embedded simulating halt decider at Ĥ.qx is 
pure simulation that never halts.

∴ Sound Deductive Conclusion
The embedded simulating halt decider at Ĥ.qx correctly decides its 
input: ⟨Ĥ⟩ ⟨Ĥ⟩ is a computation that never halts.

Ĥ.q0 ⟨Ĥ⟩ specifies an infinite chain of invocations that is terminated 
at its third invocation. The first invocation of Ĥ.qx ⟨Ĥ⟩, ⟨Ĥ⟩ is the 
first element of an infinite chain of invocations.

It is common knowledge that when any invocation of an infinite chain of 
invocations is terminated that the whole chain terminates. That the 
first element of this infinite chain terminates after its third element 
has been terminated does not entail that this first element is an actual 
terminating computation.

The above is more clear when you can see the cycle in the state 
transition diagram of Ĥ(⟨Ĥ⟩) provided in this paper:

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


-- 
Copyright 2021 Pete Olcott

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

[toc] | [next] | [standalone]

#3184

On 7/17/2021 8:32 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> ...
>> I only skimmed the above, I skipped most of the words.
> 
> Good plan.  You really don't want to know what I said!  I've cut it
> since you don't care about details.  Let's stick with the big picture.
> 
>> int main() { P(P); } is computationally equivalent to Ĥ(⟨Ĥ⟩).
> 
> Yes.  P(P) halts (according to you).  H(P,P) == 0 (according to you).
> That is wrong (according to everyone but you).
> 

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

Unless the simulating halt decider embedded at state Ĥ.qx aborts the 
simulation of its input at some point its input never halts thus proving 
beyond all possible doubt that the input that was aborted is correctly 
decided as never halting.

When a computation only stops running because its simulation was aborted 
this counts as a computation that never halts.


-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#3195

On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> When a computation only stops running because its simulation was
>> aborted this counts as a computation that never halts.
> 
> Me: Every computation that halts, for whatever reason, is a halting
>      computation.
> 
> You: OK
> 

A computation having its simulation aborted never halts even though it 
stops running. Only computation that stop running without having their 
simulation aborted are halting computations.

> P(P) halts (according to you).  H(P,P) == 0 (according to you).
> That is wrong -- even according to you.
> 


-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.software-eng

csiph-web