Question

In Theorem 3.21 we showed that a language is Turing-recognizable iff some enumerator enumerates it. Why didn’t we use the following simpler algorithm for the forward direction of the proof? As before, s₁,s₂,... is a list of all strings in ${\mathbf{\sum }}^{\mathbf{*}}$

E = “Ignore the input.

1. Repeat the following for $\mathbf{i}\mathbf{=}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}$

2. Run M on s_i.

3. If it accepts, print out s_i.”

Short answer

We need to simulate on each of the strings for a fixed length of time so that no looping can occur.

Step-by-step solution

Turing machine.

A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine.

A Turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions.

Solution.

The problem with the proof is that M on s_i might loop forever. If it loops forever, then E0 doesn’t print out s_i.

More importantly, E isn’t going to move on to test the next string. Therefore, it won’t be able to enumerate any other strings in L.

E = “Ignore the input.

1. Repeat the following for $\mathrm{i}=1,2,3,...$

2. Run M on s_i.

3. If it accepts, print out s_i.”

For this reason, we need to simulate M on each of the strings for a fixed length of time so that no looping can occur.