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


Groups > comp.software-eng > #2705

Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)

From Kaz Kylheku <563-365-8930@kylheku.com>
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng, sci.math.symbolic
Subject Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)
Followup-To comp.theory
Date 2021-05-20 06:16 +0000
Organization A noiseless patient Spider
Message-ID <20210519230945.845@kylheku.com> (permalink)
References <Fr2dnaHj2JTVTjj9nZ2dnUU7-RPNnZ2d@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-20, olcott <NoOne@NoWhere.com> wrote:
> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qy  ∞
> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qn
>
> The above is adapted from (Linz:1990:319).
> It shows that Turing machine Ĥ copies its input at (q0) and begins 
> executing an embedded copy of the original halt decider with this input 
> at (qx).
>
> The (qy) state indicates that the halt decider decides that its input 
> would halt. The ((qn)) state indicates the input would not halt. The 
> appended (qa) and (qb) states cause Ĥ to infinitely loop if the halt 
> decider decides that its input would halt.
>
> Linz, Peter 1990. An Introduction to Formal Languages and Automata. 
> Lexington/Toronto: D. C. Heath and Company.
>
> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>
>
>
> *Three irrefutable truisms lead to one conclusion*
>
> Truism(1a)
> The simulation of [Ĥ] by its simulating halt decider Ĥ would never halt 
> unless this simulation is aborted.

Corrections.

Firstly, you made a typo: the halt decider is H, not H-hat.

Secondly, the truth is more general:

"The simulation of [Ĥ] by *ANY* simulating halt decider would never
halt unless this simulation is aborted."

When the simulating decider is H, then ... the simulation is NOT
aborted. So this truism specifically does not apply to H in any useful
way.

When we apply the truism specifically to H, we get a VACUOUS TRUTH.

> Truism(1b)
> (1a) is another way of saying that when the copy of H at Ĥ.qx only 
> simulates its input [Ĥ] its input never halts.

That "when" is always. H only simulates its input.

If you want to talk about some other thing that simulates its input
with abort checks ... you must not call it H.

> This [simulating halt decider] is not decider in the technical sense, 
> because it never halts. The fact that it never halts proves that its 
> input is not halting.

(Not really; a really broken decider could fail to halt on a halting
input.)

> Truism(3)
> Ĥ([Ĥ]) Halts because it aborted the simulation of its input.

False; Ĥ([Ĥ]) does not halt. Ĥ embeds H, and H is a non-aborting,
simulate-only, run-to-completion machine.

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


Thread

Halting theorem refutation (Three irrefutable truisms lead to one conclusion) olcott <NoOne@NoWhere.com> - 2021-05-19 22:11 -0500
  Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-20 06:16 +0000

csiph-web