2
$\begingroup$

I would like to show that the following language is recognizable: $$L:= \{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\}.$$

How do I go about showing that this language is recognizable? I know that all recognizable languages are reducible to $HALT_\epsilon$, so I figure if I can show that this language reduces to $HALT_\epsilon$, then I am all set. I am defining $HALT_\epsilon$ as follows:

$$HALT_\epsilon:= \{ \langle M \rangle \mid M \text{ is a TM that halts on } \epsilon \},$$

where $\epsilon$ is the empty string. We can reduce $HALT$ on $x$ to $HALT_\epsilon$ by a reduction $F(\langle M, x\rangle) = \langle M' \rangle $, where $M'(y) = M(x)$. For this reduction, we just ignore the input string $y$, which we know will be $\epsilon$ and just run $M$ on $x$ instead. Here, $HALT$ is defined as

$$HALT:= \{ \langle M,x \rangle \mid M \text{ is a TM that halts on } x \}.$$

I tried leveraging a similar technique to show that $L$ is recognizable, but I could not come up with anything better than this (somewhat crazy) TM that has a $HALT_\epsilon$ oracle:

$ D^{HALT_\epsilon} =$ On input $\langle M \rangle:$

  1. Construct $N = $ "On input $x:$
    1. Run $M$ in parallel on all inputs $y\in \Sigma^*$.
    2. If $M$ halts on any $y$ then accept, otherwise loop."
  2. Query the oracle to determine whether $\langle N \rangle \in HALT_\epsilon$.
  3. If the oracle answers YES, accept; if NO, reject.

Note: My notation for TM algorithms is based on "Theory of Computation" by Sipser. Step 2 for the definition of $N$ is a bit redundant, but in this type of context, is it okay to say something like "If $M$ halts on any $y$, then halt?"

I think all I have shown here is that $L$ is decidable relative to $HALT_\epsilon$. I don't know if this implies that $L$ is recognizable. Can a Turing reduction be used in this manner to show that a language is recognizable? I'm confused as to what it means for a language to be recognizable. The task seems obvious if we go back to the definition: If some TM $R$ accepts strings in $L$, then $R$ recognizes $L$. So what if $R=D^{HALT_\epsilon}$, and in the body of $D^{HALT_\epsilon}$ we use some crazy reduction like $N$?

In general, to show recognizability, can we just come up with a reduction like $N$ that may or may not halt? Is it a problem that $N$ will never halt if $\langle M \rangle \notin L$?

$\endgroup$
6
$\begingroup$

You can construct a recognizer following the same principle used for the recognizer for HALT. The only extra bit is how you check "all" inputs without getting stuck in a non-terminating computation.

An important technique you can use here is called dovetailing (expressed with inputs from $\mathbb{N}$):

  1. Simulate one step of $M$ on $1$.
  2. Simulate two steps of $M$ on $1$ and $2$ each.
  3. Simulate three steps on $1$, $2$ and $3$ each.

$\quad\vdots$

  • Terminate and accept once any of the simulated computations terminates and accepts.

If there is a halting input of $M$, this dovetailed simulation certainly finds it after finite time. If there is none, it loops and is correct in doing so.

This is, in essence, your $N$ (with an explanation why it's actually a computable function). You don't need the rest of the reduction in order to show that $L$ is semi-decidable.

$\endgroup$
  • $\begingroup$ I added some clarification to my question, because I don't think I give a recognizer for $HALT$. What are you referring to when you say "the recognizer for $HALT$?" So, $N$ is enough to show that $L$ is semi-decidable. Does semi-decidable imply recognizable? I think it does, because $N$ is a TM that recognizes strings in $L$. I just want to double check. $\endgroup$ – baffld Mar 22 '14 at 17:12
  • 1
    $\begingroup$ @baffld: Afaik, recognisable and semi-decidable mean the same thing; I just prefer the latter notion. To be safe, check the definitions you have in hand and compare to the TM I describe. (I was assuming you know a recognizer for HALT; if not, you should be able to come up with one after reading my answer.) $\endgroup$ – Raphael Mar 22 '14 at 22:44

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.