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


Groups > comp.theory > #33993

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

Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng, sci.math.symbolic
From olcott <NoOne@NoWhere.com>
Subject Halting theorem refutation (Three irrefutable truisms lead to one conclusion)
Date 2021-05-19 22:11 -0500
Message-ID <Fr2dnaHj2JTVTjj9nZ2dnUU7-RPNnZ2d@giganews.com> (permalink)

Cross-posted to 4 groups.

Show all headers | View raw


Ĥ.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.

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

Any input running under a simulating halt decider that never aborts its 
input will have the same behavior as an input run under a simulator.

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.

Truism(2)
Every simulation of input P that would never halt unless simulating halt 
decider H stopped simulating it <is> a non-halting computation. This 
remains true even after H stops simulating P.

I am merely generalizing the the halt deciding principle that overcomes 
the pathological self-reference error of the halting theorem.

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

Conclusion:
Ĥ is a halting computation and its input is not a halting computation 
therefore Ĥ decides its input [Ĥ] as non-halting correctly.



http://www.liarparadox.org/Halting_problem_undecidability_and_infinitely_nested_simulation.pdf


-- 
Copyright 2021 Pete Olcott

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

Back to comp.theory | Previous | Next — Next 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
    Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(not a typo) olcott <NoOne@NoWhere.com> - 2021-05-20 10:53 -0500
  Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-20 12:35 +0100
    Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(pause until mutual agreement) olcott <NoOne@NoWhere.com> - 2021-05-20 10:04 -0500
      Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(pause until mutual agreement) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-21 00:44 +0100
        Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(pause until mutual agreement) olcott <NoOne@NoWhere.com> - 2021-05-20 19:08 -0500
          Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(pause until mutual agreement) Richard Damon <Richard@Damon-Family.org> - 2021-05-21 07:42 -0400
          Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(pause until mutual agreement) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-21 23:49 +0100

csiph-web