patternMinor
Is the language of TMs that halt on some string recognizable?
Viewed 0 times
thetmsrecognizablelanguagethatsomehaltstring
Problem
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:$
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 t
$$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:$
- Construct $N = $ "On input $x:$
- Run $M$ in parallel on all inputs $y\in \Sigma^*$.
- If $M$ halts on any $y$ then accept, otherwise loop."
- Query the oracle to determine whether $\langle N \rangle \in HALT_\epsilon$.
- 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 t
Solution
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}$):
$\quad\vdots$
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.
An important technique you can use here is called dovetailing (expressed with inputs from $\mathbb{N}$):
- Simulate one step of $M$ on $1$.
- Simulate two steps of $M$ on $1$ and $2$ each.
- 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.
Context
StackExchange Computer Science Q#22929, answer score: 6
Revisions (0)
No revisions yet.