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; andAll 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?)
Program synthesis, decidability and the halting problem
turing machines;undecidability;halting problem
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$.