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


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

Eliminating the pathological self-reference error of the halting theorem (V6)

Started byolcott <NoOne@NoWhere.com>
First post2021-05-21 11:33 -0500
Last post2021-05-21 16:54 +0000
Articles 3 — 3 participants

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


Contents

  Eliminating the pathological self-reference error of the halting theorem (V6) olcott <NoOne@NoWhere.com> - 2021-05-21 11:33 -0500
    Re: Eliminating the pathological self-reference error of the halting theorem (V6) Mr Flibble <flibble@reddwarf.jmc> - 2021-05-21 17:38 +0100
    Re: Eliminating the pathological self-reference error of the halting theorem (V6) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-21 16:54 +0000

#2717 — Eliminating the pathological self-reference error of the halting theorem (V6)

Fromolcott <NoOne@NoWhere.com>
Date2021-05-21 11:33 -0500
SubjectEliminating the pathological self-reference error of the halting theorem (V6)
Message-ID<LJqdnefVIoI5fTr9nZ2dnUU7-K_NnZ2d@giganews.com>
(A) Every simulation of input P that never halts unless simulating halt 
decider H aborts this simulation <is> a non-halting computation. This 
remains true even after H stops simulating P.

∃H ∈ Simulating_Halt_Deciders
∀P ∈ Turing_Machine_Descriptions
∀I ∈ Finite_Strings
   (UTM(P,I) = ∞) ⊢ (H(P,I) = 0)

Because the simulation of the TM description of a TM on its input by a 
UTM is known to be equivalent to the direct execution of a TM on its 
input we know that the above mathematical logic is correct.

In English it says that whenever the input (P,I) to UTM would never halt 
then a simulating halt decider correctly decides not halting on this input.

By screening out the distinctly different behavior of a UTM from a 
simulating halt decider the pathological self-reference error of the 
halting theorem is eliminated.

The behavior of the proxy computation forms the halt deciding basis for 
  the inputs that would otherwise specify the pathological 
self-reference error.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [next] | [standalone]


#2718

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-05-21 17:38 +0100
Message-ID<20210521173811.000014a9@reddwarf.jmc>
In reply to#2717
On Fri, 21 May 2021 11:33:25 -0500
olcott <NoOne@NoWhere.com> wrote:

> (A) Every simulation of input P that never halts unless simulating
> halt decider H aborts this simulation <is> a non-halting computation.
> This remains true even after H stops simulating P.

If the simulator aborts the simulation then the simulation didn't halt,
the simulator halted the simulation.  You cannot assume P is
non-halting simply because your omnishambles cockwomble of a
"partial halt decider" aborted the simulation until you address the
issues of branching logic predicated on arbitrary program input.

> 
> ∃H ∈ Simulating_Halt_Deciders
> ∀P ∈ Turing_Machine_Descriptions
> ∀I ∈ Finite_Strings
>    (UTM(P,I) = ∞) ⊢ (H(P,I) = 0)

Please refrain from using mathematical symbols that aren't present in
most fonts; Usenet readers often don't support displaying them as they
don't support fallback fonts.

[snip]

/Flibble

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


#2720

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-05-21 16:54 +0000
Message-ID<20210521094531.937@kylheku.com>
In reply to#2717
["Followup-To:" header set to comp.theory.]
On 2021-05-21, olcott <NoOne@NoWhere.com> wrote:
> (A) Every simulation of input P that never halts unless simulating halt 
> decider H aborts this simulation <is> a non-halting computation. This 
> remains true even after H stops simulating P.
>
> ∃H ∈ Simulating_Halt_Deciders
> ∀P ∈ Turing_Machine_Descriptions
> ∀I ∈ Finite_Strings
>    (UTM(P,I) = ∞) ⊢ (H(P,I) = 0)

This seems to be saying that there exists some simulating decider H such
that H will call all non-halting Turing machines non-halting.

The halting theorem shows that the above is false; and you have
no disproof.

Among those those <P, I> inputs there is one problematic pair:

 <P, I> = <H_Hat, H_Hat>

and so on, whose calculation is such that UTM(H_Hat, H_Hat) = ∞ if,
and only if, H(H_Hat, H_Hat) /= 0. Therefore it cannot be true that

  (UTM(P,I) = ∞) ⊢ (H(P,I) = 0)

For that <P, I> pair. UTM(P, I) only calculates forever if H(P, I) is
nonzero, otherwise not.

> In English it says that whenever the input (P,I) to UTM would never halt 
> then a simulating halt decider correctly decides not halting on this input.

It says that a simulating halt decider exists whuich correctly ...

> By screening out the distinctly different behavior of a UTM from a 
> simulating halt decider the pathological self-reference error of the 
> halting theorem is eliminated.

You have not "screened out" (and must not) the fact that the set of
<P, I> pairs contains the "eviL" <H_Hat, H_Hat>.

[toc] | [prev] | [standalone]


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


csiph-web