$\text{LOOP-EVEN}_{TM}$ = {M is a TM that won't halt for every EVEN input} why is $\text{LOOP-EVEN}^\complement$ recognisable?

Question

Given the language

$\text{LOOP-EVEN}_{TM}$ = {M is a TM that won't halt for every even input}

Show that $\text{LOOP-EVEN}^\complement$ is recognizable.

This is the what i think is the proof:

Let's build a TM that will recognize $\text{LOOP-EVEN}^\complement$, This machine will contain all TMs M' that have at least one even input that halts. Let's run in parallel all even words on M' and if one halts then accept M'.

If i am correct in my proof then what i do not understand is how running in parallel can work on a language in case it is infinite? how would a round robin algorithm work in this case.

Answer 1

Yes, your proof sketch works.

There are two classical ways to run infinitely many Turing machine instances in parallel, looking for one that terminates.

The first way is often known as "dovetailing". Interlace the steps of all the machines you simulate as follows:

• At times $1, 3, 5, 7, 9, \ldots$ do a step of computation number $0$.

• At times $2, 6, 10, 14, 18, \ldots$ do a step of computation number $1$.

• At times $4, 12, 20, 28, 36, \ldots$ do a step of computation number $2$.

• And so forth. In general when the time is an odd multiple of $2^n$, do a step of computation number $n$.

At each finite step in this process, you will only have made the first step of finitely many of the computations, so you can remember the configurations of all of those for when you get to one of them the next time. On the other hand, if one of the computations eventually terminates, you will get to the step where it terminates sooner or later (unless you find another terminating computation first).

The second way.

• Let $g$ be your favorite computable surjection $\mathbb N\to \mathbb N\times \mathbb N$.

• For $n=1, 2, 3, \ldots$, do:

  • Let $(a,b) = g(n)$.

  • Simulate computation number $a$ for $b$ steps (or $2^b$ steps, or some other unbounded function of $b$), starting from the beginning. If it terminates within this time limit, you're done. Otherwise continue with the next $n$.

This is somewhat easier to program, and has better space behavior, but wastes a lot of time redoing steps it has already done once.

On the other hand, neither of these "efficiency" considerations matter any as long as we're only interested in computability. So authors tend to pick one of the strategies purely based on which they think will be easiest to explain to their audience.