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

  • 4
    $\begingroup$ 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). $\endgroup$ – Andreas Blass Jul 20 '17 at 4:20
  • 1
    $\begingroup$ @AndreasBlass And of course we can even enlarge it by infinitely many Turing machines, via the padding lemma. $\endgroup$ – Noah Schweber Jul 20 '17 at 4:57
  • 2
    $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Jul 20 '17 at 11:03
  • 2
    $\begingroup$ I've made such a post at mathoverflow.net/a/58074/1946. $\endgroup$ – Joel David Hamkins Jul 20 '17 at 12:15
  • 2
    $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Aug 1 '17 at 17:19
  • $\begingroup$ This is true. It's more correct to say that every instance of the original problem gives rise to an instance of the new one. $\endgroup$ – anonymous Aug 2 '17 at 4:02
  • $\begingroup$ It is a variant of halting problem, just being asked in other way. Interesting. $\endgroup$ – XL _At_Here_There Oct 2 '17 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.