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$ Commented 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$ Commented 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$ Commented Jul 20, 2017 at 11:03
  • 2
    $\begingroup$ I've made such a post at mathoverflow.net/a/58074/1946. $\endgroup$ Commented 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
    Commented 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$ Commented 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
    Commented Aug 2, 2017 at 4:02
  • $\begingroup$ It is a variant of halting problem, just being asked in other way. Interesting. $\endgroup$ Commented Oct 2, 2017 at 11:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .