0
$\begingroup$

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

$\endgroup$
  • 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$ – Raphael Jun 14 '17 at 6:00
  • 1
    $\begingroup$ Hint: There are infinitely many machines for which the halting problem is trivial. $\endgroup$ – Raphael Jun 14 '17 at 6:00
  • $\begingroup$ $L=\{\langle M, w\rangle|M$ halts on $w$ in less than 10 steps$\}$. $\endgroup$ – Sid Caroline Jun 14 '17 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 N Feb 7 at 16:56
1
$\begingroup$

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.

$\endgroup$

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.