Halting problem undecidability and infinitely nested simulation

Abstract

The halting theorem counter-examples present infinitely nested simulation (non-halting) behavior to every simulating halt decider. The pathological self-reference of the conventional halting problem proof counter-examples is overcome. The halt status of these examples is correctly determined. A simulating halt decider remains in pure simulation mode until after it determines that its input will never reach its final state. This eliminates the conventional feedback loop where the behavior of the halt decider effects the behavior of its input.

Categories

Keywords

Reprint years

Links

PhilArchive

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

My notes

Similar books and articles

Halting Problem Proof from Finite Strings to Final States.Pete Olcott - manuscript
Defining a Halting Decidability Decider.Pete Olcott - manuscript
Defining a Decidability Decider for the Halting Problem.Pete Olcott - manuscript
A mechanical proof of the unsolvability of the halting problem.Robert Boyer - unknown
A brief critique of pure hypercomputation.Paolo Cotogno - 2009 - Minds and Machines 19 (3):391-405.
The Halting Problem Is Decidable on a Set of Asymptotic Probability One.Joel David Hamkins & Alexei Miasnikov - 2006 - Notre Dame Journal of Formal Logic 47 (4):515-524.
Equivalence of the Frame and Halting Problems.Eric Dietrich & Chris Fields - 2020 - Algorithms 13 (175):1-9.
Kleene's proof of g¨odel's theorem.Peter Smith - unknown
Busy beaver competition and Collatz-like problems.Pascal Michel - 1993 - Archive for Mathematical Logic 32 (5):351-367.
Effective inseparability in a topological setting.Dieter Spreen - 1996 - Annals of Pure and Applied Logic 80 (3):257-275.
Accelerating Turing machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Quantum hypercomputability?Amit Hagar & Alexandre Korolev - 2006 - Minds and Machines 16 (1):87-93.
Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
A Reducibility Related To Being Hyperimmune-free.Frank Stephan & Liang Yu - 2014 - Annals of Pure and Applied Logic 165 (7-8):1291-1300.
Approximation to a Decision Procedure for the Halting Problem.Michael Anderson - 1970 - Journal of Symbolic Logic 35 (3):480-480.

Analytics

Added to PP
2021-05-29

Downloads
1,239 (#9,248)

6 months
421 (#4,003)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references