##
**The halting problem is decidable on a set of asymptotic probability one.**
*(English)*
Zbl 1137.03024

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 (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:

The Main Theorem proved by the authors states that there exists a set \(B\) of Turing machine programs such that:

- (1)
- \(B\) has asymptotic probability one,
- (2)
- \(B\) is polynomial time decidable, and
- (3)
- the halting problem \(H\cap B\) is polynomial time decidable.

- (1)
- \(B\) has nonzero asymptotic probability,
- (2)
- \(B\) is polynomial time decidable,
- (3)
- the halting problem \(H\cap B\) is polynomial time decidable.

- (3)
- \(\text{FIN}\cap B\) is polynomial time decidable,
- (4)
- \(\text{COF}\cap B\) is polynomial time decidable.

Reviewer: Hrant B. Marandjian (Erevan)

### MSC:

03D10 | Turing machines and related notions |

03B25 | Decidability of theories and sets of sentences |

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

68Q25 | Analysis of algorithms and problem complexity |