The halting problem is decidable on a set of asymptotic probability one (Q2372684): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1963569554 / rank | |||
Normal rank |
Revision as of 21:29, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The halting problem is decidable on a set of asymptotic probability one |
scientific article |
Statements
The halting problem is decidable on a set of asymptotic probability one (English)
0 references
1 August 2007
0 references
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.
0 references
Turing machine
0 references
halting problem
0 references
asymptotic density
0 references
asymptotic probability
0 references
polynomial time decidability
0 references