Language is non-empty is recursively enumerable (intuitive way) [duplicate]

Question

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

Answer 1

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.