# Halting problem about subclass of Turing Machines

As we know, that the halting problem of Turing machines is undecidable. given some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can be decidable?

Does there exist a subclass $TM_{max}$ halting problem of which is decidable such that any decidable subclass $TM_s\subseteq TM_{max}$?

The two questions possibly are too broad, any concrete answer is welcome.

Any reference is welcome

• If the halting problem is decidable for a subclass of $TM$, then it's also decidable for the slightly larger subclass obtained by adding one more Turing machine (or adding any finite number of Turing machines). – Andreas Blass Jul 20 '17 at 4:20
• @AndreasBlass And of course we can even enlarge it by infinitely many Turing machines, via the padding lemma. – Noah Schweber Jul 20 '17 at 4:57
• Meanwhile, the halting problem is decidable on a set of TM programs having asymptotic density one, so that as $n$ increases, the fraction of the $n$-state programs in the set goes to $1$. See jdh.hamkins.org/haltingproblemdecidable. – Joel David Hamkins Jul 20 '17 at 11:03
• I've made such a post at mathoverflow.net/a/58074/1946. – Joel David Hamkins Jul 20 '17 at 12:15
• @XL_at_China With regards to your question on black holes... I might point you to the final corollary of my paper at arxiv.org/pdf/1405.0022.pdf, which has (as a consequence) that there is an effective enumeration of the TM programs for which the halting problem is not decidable on any set of asymptotic density 1... but I can't name a specific model of computation that produces it naturally, nor do I know that you should find an intermediate measure. – Eric Astor Jul 22 '17 at 0:56

Let $K$ denote the set of halting Turing machines (TMs). You are asking (1) for what kind of sets $A$ of TMs is $A \cap K$ decidable, and (2) is there a maximal such $A$. Question 2 has been answered in the comments, I think, but to go over it again: Since $F \cap K$ is decidable for every finite $F$, any maximal such $A$ must have $A \cap K = K$, which cannot be, because $K$ is not decidable.
Question 1 can be rephrased a little more simply as: What kind of subsets $A \subseteq K$ are decidable? There are lots of such $A$, to wit: TMs that execute a primitive recursive procedure, TMs that execute as a finite automaton, TMs $M$ that halt after fewer than $f(M)$-many steps, where $f$ is a computable function that takes $M$'s program as input.
Here's a funny fact I noticed. If $f$ is a computable function, let $K_f = \{M : M\ \mathrm{halts\ in\ fewer\ than}\ f(M)\ \mathrm{steps}\}$. Clearly any such $K_f$ is a computable set; the funny fact is that if $A \subseteq K$ is computable, then $A \subseteq K_f$ for some $f$. (You can use $A$ to construct an appropriate $f$.) So to specify an infinite computable subset of $K$ is more-or-less the same as first selecting a maximum runtime $f$, then selecting any computable subset of the computable set $K_f$.
• Question 1 (about $A\cap K$) is somewhat more general than your rephrasing (about $A\subseteq K$). For example, there are some easily described sets $A$ that are disjoint from $K$, namely sets of TMs that obviously fail to halt --- those that just stay in their initial state, more generally those that enter a loop within a computably bounded number of steps, those that move to the right at every step, etc. – Andreas Blass Aug 1 '17 at 17:19