TM Languages

TM Languages

The concept of Turing Machine (TM) languages is crucial in theoretical computer science. A language is defined as a set of strings over a given alphabet. TMs can accept or reject these strings based on their design. In this topic, we will explore the definition of recursively enumerable languages, their properties, and how TMs interact with them.

Definition of Recursively Enumerable Languages

A language L over an alphabet Σ is called recursively enumerable if there exists a Turing Machine T that accepts every string in L. For strings not in L, T either rejects or loops forever. This can be expressed as:

accept(T) = L

reject(T) + loop(T) = L'

Here, L' is the complement of L, meaning it contains all strings not in L. This definition indicates that while T can confirm membership in L, it may not be able to decide non-membership.

Example of Recursively Enumerable Languages

Consider the language L defined as:

L = { w ∈ (a + b)* | w contains the substring "aa" }

In this case, a TM can be designed to accept any string containing "aa". If a string does not contain "aa", the TM may either crash (reject) or loop indefinitely. Thus, L is recursively enumerable.

Definition of Recursive Languages

A stricter requirement is for a language to be recursive. A language L is recursive if there exists a TM T that accepts every string in L and rejects every string in L'. This can be expressed as:

accept(D) = L

reject(D) = L'

loop(D) = ∅

This means that for every string, the TM must halt, either by accepting or rejecting.

Example of Recursive Languages

For instance, consider the language:

L = { w ∈ (a + b)* | w starts with "a" }

A TM can be designed to accept any string starting with "a" and reject all others. This TM halts on all inputs, making L a recursive language.

Properties of Recursively Enumerable Languages

• Every recursive language is recursively enumerable.
• There exist recursively enumerable languages that are not recursive.
• Recursively enumerable languages can be recognized by TMs that may not halt for all inputs.

Properties of Recursive Languages

• All recursive languages are decidable.
• They have TMs that halt on all inputs.
• Recursive languages are closed under union, intersection, and complement.

Examples of Non-Recursive Languages

Consider the language:

L = { w ∈ (a + b)* | w does not equal the encoding of a Turing machine that halts on input w }

This language is recursively enumerable but not recursive. A TM can enumerate all strings that do not equal the encoding of a halting TM, but it cannot decide membership for all strings without looping indefinitely.

Constructing TMs for Recursively Enumerable Languages

To construct a TM for a recursively enumerable language, follow these steps:

1. Define the alphabet Σ for the language.
2. Specify the set of states, including the start and accept states.
3. Outline the transition functions based on the input strings.
4. Ensure the TM accepts strings in the language and either rejects or loops for strings not in the language.

Example: Constructing a TM

Let us construct a TM for the language L = { w ∈ (a + b)* | w contains "aa" }.

1. Alphabet: Σ = {a, b}
2. States: Q = {q0, q1, q_accept, q_reject}
3. Start state: q0
4. Accept state: q_accept
5. Reject state: q_reject

The transitions can be defined as follows:

1. (q0, a) → (q1, a, R)  // Move to q1 on reading 'a' and move right
2. (q0, b) → (q0, b, R)  // Stay in q0 on reading 'b'
3. (q1, a) → (q_accept, a, R)  // Accept if 'a' is read after 'a'
4. (q1, b) → (q0, b, R)  // Go back to q0 on reading 'b'
5. (q0, $) → (q_reject, $, R)  // Reject on end of input without accepting

This TM will accept strings containing "aa" and reject or loop for others.

Conclusion

Recursively enumerable languages play a vital role in the study of computation. Understanding their properties helps in recognizing the limitations of Turing Machines. While all recursive languages are recursively enumerable, the reverse is not always true. This distinction is crucial in theoretical computer science.

Check your understanding

1. Define recursively enumerable languages and provide an example.
2. What is the difference between recursive and recursively enumerable languages?
3. Can a language be recursively enumerable but not recursive? Explain with an example.
4. Outline the steps to construct a TM for a given recursively enumerable language.