1
$\begingroup$

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

$\endgroup$
10
  • 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$ Jul 20, 2017 at 4:20
  • 1
    $\begingroup$ @AndreasBlass And of course we can even enlarge it by infinitely many Turing machines, via the padding lemma. $\endgroup$ Jul 20, 2017 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$ Jul 20, 2017 at 11:03
  • 2
    $\begingroup$ I've made such a post at mathoverflow.net/a/58074/1946. $\endgroup$ Jul 20, 2017 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, 2017 at 0:56

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
3
  • $\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$ Aug 1, 2017 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, 2017 at 4:02
  • $\begingroup$ It is a variant of halting problem, just being asked in other way. Interesting. $\endgroup$ Oct 2, 2017 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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