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


Groups > comp.software-eng > #2720

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

From Kaz Kylheku <563-365-8930@kylheku.com>
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng, sci.math.symbolic
Subject Re: Eliminating the pathological self-reference error of the halting theorem (V6)
Followup-To comp.theory
Date 2021-05-21 16:54 +0000
Organization A noiseless patient Spider
Message-ID <20210521094531.937@kylheku.com> (permalink)
References <LJqdnefVIoI5fTr9nZ2dnUU7-K_NnZ2d@giganews.com>

Cross-posted to 4 groups.

Followups directed to: comp.theory

Show all headers | View raw


["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>.

Back to comp.software-eng | Previous | Next — Previous in thread | Find similar | Unroll thread


Thread

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

csiph-web