The halting problem is decidable on a set of asymptotic probability one (Q2372684): Difference between revisions

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.