2
$\begingroup$

$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$
1
  • $\begingroup$ Use dove-tailing. $\endgroup$
    – Raphael
    Jan 14, 2017 at 18:59

1 Answer 1

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.