We already know that $H:=\{\langle M,w\rangle | M$ halts on $w\}$ is undecidable, then how can there possibly be a machine that decides any infinite subset of $H$?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$– RaphaelCommented Jun 14, 2017 at 6:00
-
1$\begingroup$ Hint: There are infinitely many machines for which the halting problem is trivial. $\endgroup$– RaphaelCommented Jun 14, 2017 at 6:00
-
$\begingroup$ $L=\{\langle M, w\rangle|M$ halts on $w$ in less than 10 steps$\}$. $\endgroup$– Sid CarolineCommented Jun 14, 2017 at 7:43
-
$\begingroup$ It's probably easiest to visualize this in terms of some code in your favorite programming language. Is there a simple algorithm you can write that can correctly diagnose that a (say) Python script is of a particular never-halting form? Sure. Consider any valid program that starts with the string "while True: x=1;", of which there are infinitely many (e.g the next line could be "a=1", or "a=2", or "a=3", etc.). Such a program never halts and is easy to identify. $\endgroup$– Yonatan NCommented Feb 7, 2019 at 16:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $M$ be a TM which accepts all inputs. Then $\{ \langle M, w \rangle \mid w \in \{ 0, 1 \}^\ast \}$ is an infinite subset of $H$ and (easily) decidable.
Going further, let $M_w$ be a TM which halts if and only if its input is not equal to $w \in \{ 0, 1 \}^\ast$ and let it be such that $\langle M_w \rangle$ is computable from any $w$ (e.g., $w$ is a substring of the description of $M_w$). Then the set $\{ \langle M_w, w' \rangle \mid w, w' \in \{ 0, 1 \}^\ast \}$ is another infinite subset of $H$ which is decidable. The description for a decider could be, for example: Given $\langle M_w, w' \rangle$, compute $\langle M_{w'} \rangle$ and accept if and only if it is equal to $\langle M_w \rangle$.
A warning: in the question text you referred to "a machine that decides any infinite subset of $H$". Indeed, no such machine exists (since $H$ is an infinite subset of itself); however, this is not what the question title (presumably the intended question) is implying.
