2
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by D.W. Apr 3 at 16:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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.
$\endgroup$

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