Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2717 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-05-21 11:33 -0500 |
| Last post | 2021-05-21 16:54 +0000 |
| Articles | 3 — 3 participants |
Back to article view | Back to comp.software-eng
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
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-21 11:33 -0500 |
| Subject | Eliminating 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]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-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]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-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