$M$ is some Turing machine, $\left<M\right>$ is the code of the Turing machine.

$L =\{\left<T\right> | L(T) \ne \emptyset\}$

How to see intuitively that $L$ is partially decidable?

We can try running a given $M$ on all strings and accept if $M$ accepts. However, what if the simulated $M$ gets into an infinite loop?

  • $\begingroup$ Use dove-tailing. $\endgroup$ – Raphael Jan 14 '17 at 18:59

A language $L$ is partially computable if there is a machine $M$ that on input $x$:

  1. If $x \in L$ then $M$ halts.

  2. If $x \notin L$ then $M$ doesn't halt.

This is equivalent to the other definitions.

To answer your question, what we do is to run the input machine $M$ on all inputs in parallel. If it never accepts on any input, then we never halt, but that's ok.

In order to run $M$ on all inputs in parallel, we use the technique of dovetailing:

  • We run $M$ for one step on the first input.
  • We run $M$ for one step on the first two inputs.
  • We run $M$ for one step on the first three inputs.
  • And so on.
| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.