The halting problem is decidable on a set of asymptotic probability one

DOI10.1305/NDJFL/1168352664MaRDI QIDQ2372684zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Joel David Hamkins, Alexei Myasnikov

Publication date 1 August 2007

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0504351

asymptotic density asymptotic probability halting problem polynomial time decidability Turing machine

Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (i) B has asymptotic probability one, so that as the number of states n increases, the proportion of all n-state programs that are in B goes to one; (ii) B is polynomial time decidable; and (iii) the halting problem H intersect B is polynomial time decidable. The proof is sensitive to the particular computational model.

Review text

Let \(P_{n}\) be the set of all \(n\)-state Turing programs. The authors define the asymptotic density (or asymptotic probability) of a set \(B\) of Turing machines as follows: \(\mu (B) = \lim_{n\to\infty}{{| B\cap P_{n}| }\over {| P_{n}| }}\) provided that the limit exists. Let \(H\) (``halting problem) denote the set of programs that eventually reach the (\textit{halt}) state from any initially empty tape. The Main Theorem proved by the authors states that there exists a set \(B\) of Turing machine programs such that: {\parindent=6mm \begin{itemize}\item[(1)]\(B\) has asymptotic probability one, \item[(2)]\(B\) is polynomial time decidable, and \item[(3)]the halting problem \(H\cap B\) is polynomial time decidable. \end{itemize}} The authors first prove this theorem for a standard model of TM computation that assumes semi-infinite tape and single halt state. Moreover, if the machine head attempts to move over the end cell then the head falls off the tape and all computation ceases. Later the result is extended to several other (but not all) models. For all the models the following result is obtained (Theorem 9): For any model of Turing machine, including those with two-way infinite tape, there exists a set \(B\) of Turing machine programs such that: {\parindent=6mm \begin{itemize}\item[(1)]\(B\) has nonzero asymptotic probability, \item[(2)]\(B\) is polynomial time decidable, \item[(3)]the halting problem \(H\cap B\) is polynomial time decidable. \end{itemize}} Assuming unary representation of natural numbers the authors denote by FIN (COF) the set of the programs on \(N\) having finite (respectively, cofinite) domains. The authors show, as a corollary to the main theorem, that there exists a set \(B\) of Turing machine programs such that the claim (3) of the Main Theorem can be replaced with the following two ones: {\parindent=6mm \begin{itemize}\item[(3)]\(\text{FIN}\cap B\) is polynomial time decidable, \item[(4)]\(\text{COF}\cap B\) is polynomial time decidable. \end{itemize}} The paper contains also other results and general observations.

Recommendations

Cited in

(31)

This page was built for publication: The halting problem is decidable on a set of asymptotic probability one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372684)