When Can a Language Be Accepted by a Turing Machine?

This section resolves the multiple-choice statement:

A language $L$ may not be accepted by a Turing machine if:

1. it is recursively enumerable;
2. it is recursive;
3. $L$ can be enumerated by some Turing machine;
4. None of the above.

The correct answer is:

(iv) None of the above.

A language is accepted, or recognized, by a Turing machine precisely when it is recursively enumerable. Every recursive language is also recursively enumerable, and a language that can be enumerated by a Turing machine is recursively enumerable as well.2

Key terms: Language; Recognizer; Recursive language; Enumerator

Footnotes

1. Recursively enumerable language - Definitions of recursively enumerable, recognizable, and the distinction from recursive languages. ↩

2. Recognition and Enumeration, CSE 105 lecture notes - States and explains the theorem that a language is Turing-recognizable if and only if some enumerator enumerates it. ↩

1. Acceptance, Recognition, and Decision

Let $M$ be a Turing machine and $L$ a language. The language accepted by $M$ is

$$L(M)=\{w\mid M\text{ accepts }w\}.$$

A Turing machine accepts or recognizes $L$ if:

• for every $w\in L$, $M$ eventually halts and accepts;
• for every $w\notin L$, $M$ may reject or run forever.

Thus, acceptance does not necessarily require the machine to halt on every input. This distinction is essential.

A machine that always halts and gives the correct answer is called a Decider. The language decided by such a machine is called recursive or decidable.

The relationship is:

The first two classes in the diagram are equal in meaning:

$$\text{Turing-recognizable} = \text{Recursively enumerable} = \text{Turing-acceptable}.$$

However,

$$\text{Recursive}\subsetneq\text{Recursively enumerable}.$$

The inclusion is proper because some languages are recognizable but not decidable, such as the acceptance problem.

Footnotes

1. Recursively enumerable language - Definitions of recursively enumerable, recognizable, and the distinction from recursive languages. ↩

2. Recursively Enumerable Languages, Turing Machines, and Decidability - Course notes on recognizable languages, undecidability, and the acceptance problem. ↩

2. Recursively Enumerable Languages

A language $L$ is recursively enumerable, abbreviated RE, if there exists a Turing machine $M$ such that:

$$w\in L \implies M\text{ accepts }w,$$

and

$$w\notin L \implies M\text{ may reject }w\text{ or run forever}.$$

Therefore, every recursively enumerable language is accepted by some Turing machine.

The word “enumerable” means that the strings in $L$ can be generated or listed by a Turing machine. The machine is not required to determine when all strings have been printed, especially when $L$ is infinite.

For example, consider

$$L=\{a^n b^n\mid n\geq 0\}.$$

A Turing machine can compare the number of $a$ symbols with the number of $b$ symbols and accept exactly the strings in $L$. Since this machine can also halt on inputs not in $L$, the language is not merely recursively enumerable; it is recursive.

By contrast, a language such as the halting problem language

$$A_{TM}=\{\langle M,w\rangle\mid M\text{ accepts }w\}$$

is recursively enumerable but not recursive. A universal Turing machine can simulate $M$ on $w$ and accept if $M$ accepts. However, if $M$ never accepts, the simulation may continue forever.

Footnotes

1. Recursively Enumerable Languages, Turing Machines, and Decidability - Course notes on recognizable languages, undecidability, and the acceptance problem. ↩

3. Recursive Languages

A language $L$ is recursive if there exists a Turing machine $D$ such that, for every input $w$:

• if $w\in L$, $D$ halts and accepts;
• if $w\notin L$, $D$ halts and rejects.

The machine must halt in both cases. Consequently, every recursive language is accepted by a Turing machine.

Formally,

$$L\text{ recursive} \implies L\text{ recursively enumerable}.$$

A decider is automatically a recognizer: whenever $w\in L$, the decider accepts. The additional guarantee is that the decider also halts and rejects whenever $w\notin L$.2

Thus, option (ii) cannot be correct. A recursive language is always accepted by some Turing machine.

Footnotes

1. Recursively enumerable language - Definitions of recursively enumerable, recognizable, and the distinction from recursive languages. ↩

2. Recursive and Recursively Enumerable Languages - Comparison of recognizers, deciders, recursive languages, and recursively enumerable languages. ↩

4. Enumeration and Acceptance

An Enumerator is a Turing machine with an output device that prints strings. It enumerates $L$ if it prints every string in $L$ and never prints a string outside $L$.

A fundamental theorem states:

$$L\text{ is recursively enumerable} \iff \text{some enumerator enumerates }L.$$

From an enumerator to a recognizer

Suppose an enumerator $E$ prints exactly the strings in $L$. Construct a recognizer $M$:

1. Run $E$.
2. Whenever $E$ prints a string, compare it with the input $w$.
3. If the printed string equals $w$, accept.

If $w\in L$, the enumerator eventually prints $w$, so $M$ accepts. If $w\notin L$, $E$ never prints $w$, so $M$ may run forever. Therefore, $M$ recognizes $L$.

From a recognizer to an enumerator

Suppose $M$ recognizes $L$. List all strings over the alphabet in an effective order:

$$w_1,w_2,w_3,\ldots$$

The enumerator simulates $M$ on these strings in a dovetailed manner:

• simulate $M$ on $w_1$ for one step;
• simulate $M$ on $w_1,w_2$ for one step each;
• simulate $M$ on $w_1,w_2,w_3$ for one step each;
• continue indefinitely;
• print $w_i$ whenever the simulation of $M$ accepts it.

Dovetailing prevents one nonterminating computation from blocking all later computations. Every accepted string is eventually printed.

Therefore, option (iii) also describes a language that can be accepted by a Turing machine.

Footnotes

1. Recognition and Enumeration, CSE 105 lecture notes - States and explains the theorem that a language is Turing-recognizable if and only if some enumerator enumerates it. ↩ ↩²

5. Evaluating the Options

Option (i): $L$ is recursively enumerable

This statement means that some Turing machine recognizes $L$. By definition, every string in $L$ is eventually accepted.

Therefore, option (i) is not the answer.

Option (ii): $L$ is recursive

A recursive language has a decider. A decider is also a recognizer because it accepts every member of the language.

Therefore, option (ii) is not the answer.

Option (iii): $L$ can be enumerated by some Turing machine

The enumeration theorem states:

$$L\text{ can be enumerated} \iff L\text{ is recursively enumerable} \iff L\text{ is accepted by a Turing machine}.$$

Therefore, option (iii) is not the answer.

Option (iv): None of the above

Since each of options (i), (ii), and (iii) describes a language accepted by a Turing machine, the correct answer is:

$$\boxed{\text{(iv) None of the above}}$$

More precisely, a language may fail to be accepted by any Turing machine only when it is not recursively enumerable.2

Footnotes

1. Recursively enumerable language - Definitions of recursively enumerable, recognizable, and the distinction from recursive languages. ↩

2. Recognition and Enumeration, CSE 105 lecture notes - States and explains the theorem that a language is Turing-recognizable if and only if some enumerator enumerates it. ↩

6. Final Answer

The statement asks when a language may not be accepted by a Turing machine.

• If $L$ is recursively enumerable, it is accepted.
• If $L$ is recursive, it is accepted.
• If $L$ can be enumerated by a Turing machine, it is accepted because enumerability is equivalent to recursive enumerability.
• Therefore, none of options (i), (ii), or (iii) identifies a language that cannot be accepted.

$$\boxed{\text{Correct answer: (iv) None of the above}}$$

A more exact formulation is:

A language $L$ cannot be accepted by any Turing machine if and only if $L$ is not recursively enumerable.