14
$\begingroup$

I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that it's just too early for me to read this site. Now, with the disclaimer out of the way...

It is a well-known result it computability theory that the halting problem cannot be decided for TMs. However, this doesn't exclude the possibility that there exist machines that can solve the halting problem for certain classes of machines (just not all of them).

Consider the set of all decidable problems. For each problem, there exist infinitely many TMs which decide that language. Could the following be possible

  • There is a TM that decides the halting problem for a subset $S$ of Turing machines; and
  • All decidable problems are decided by at least one Turing machine in $S$?

Of course, finding the Turing machine in $S$ may not be computable itself; but we ignore that problem.

EDIT: Based on Shaull's answer below, it seems that either (a) this idea is too ill-specified to be meaningful or (b) my previous attempt wasn't quite on the mark. As I try to elaborate in the comments to Shaull's answer, my intent isn't that we're guaranteed that the input TM is in $S$. What I really meant by my question is whether there could exist such an $S$, such that membership in $S$ is a decidable problem. The program to solve the halting problem for $S$ would, presumably, write "invalid input" on the tape or something when given an input that it recognizes as not being in $S$. When I formulate it like that, I'm not sure whether this allows us to solve the halting problem or not, or whether Rice's theorem applies (is decidability a semantic property of a language w.r.t. Rice's theorem?)

$\endgroup$
2
  • $\begingroup$ think there is a legit/significant question at boundaries of theory lurking in here somewhere but not in the current form, nevertheless +1 for trying [and that disclaimer at the beginning is surprising considering your rep/moderator status]... maybe this is the question you were reading? algorithm to solve turings halting problem $\endgroup$
    – vzn
    Apr 5, 2013 at 17:03
  • $\begingroup$ possibly another way to phrase the question, dont know if this was the intent (which makes it very advanced). consider all possible "quasialgorithms" and their associated recognized sets $S_n$. [see other question for defns]. does the union of all such recognized sets $S_n$ equal the set of all recursive/decidable TMs? $\endgroup$
    – vzn
    Apr 6, 2013 at 1:14

1 Answer 1

Reset to default
8
$\begingroup$

I think there may be a problem with the formulation of the problem.

Consider the set $S=\{M: M $ is a decider of its language $\}$. The halting problem is decidable for this set (that is, if we are promised that the input is in this set). In fact, it is trivial (the machines in $S$ always halt).

Also, clearly every decidable language is in $S$.

EDIT: Based on the changes in the question - indeed, membership in $S$ would be undecidable: if $S$ contains a machine for each decidable language, then $S\neq \emptyset$. Thus, by Rice's theorem, if $S$ is decidable then $S$ contains every machine, but then the halting problem is undecidable on $S$.

$\endgroup$
6
  • $\begingroup$ In other words, $S = \{\langle A \rangle \mid \forall x. A(x) \downarrow, L(A) \in \mathrm{R}\}$ trivially answers the question positively. $\endgroup$
    – Raphael ♦
    Apr 5, 2013 at 14:30
  • 1
    $\begingroup$ @Raphael - no, because while $L(A)\in R$, it does not imply that $A$ is a decider. That's why we explicitly take deciders. $\endgroup$
    – Shaull
    Apr 5, 2013 at 14:35
  • 1
    $\begingroup$ Ah, right. Fixed the comment. $\endgroup$
    – Raphael ♦
    Apr 5, 2013 at 14:43
  • $\begingroup$ +1 I'm not sure I clearly communicated my meaning. What I really meant to ask was whether it's possible that such an $S$ exists, and we can check an arbitrary TM to see whether it is in $S$. We don't know a priori that it is in $S$; just that $S$ is formulated in such a way that we can check. In other words, is it possible that there exists an $S$ such that membership in $S$ is decidable? Also, your last sentence is somewhat confusing; $S$ is a set of Turing Machines (well, their representations); not of the languages the TMs decide... but I think I know what you mean to say. $\endgroup$
    – Patrick87
    Apr 5, 2013 at 15:09
  • 1
    $\begingroup$ (p.s. Sorry about getting your name wrong in my edits. Its being too early for me to do CS.SE is beginning to appear more and more likely) $\endgroup$
    – Patrick87
    Apr 5, 2013 at 15:20

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.