Language Relating to Turing Machines

Recursively Enumerable Languages

• Language of a Machine: The collection of strings a machine accepts is its language, denoted as ( L(M) ).
• Turing-Recognisable (Recursively Enumerable) Language: A language is called Turing-recognisable if there exists a Turing machine that recognises it.

Enumerators

• Enumerator: A special type of Turing machine that outputs a set of strings it accepts, akin to having a printer attached for accepted strings.
• Theorem 15: A language is Turing-recognisable if and only if some enumerator enumerates it.
  • Proof:
    • Direction 1: If an enumerator ( E ) enumerates a language ( L ), then a Turing machine ( M ) can be constructed to recognise ( L ).
      • Operation: On input ( w ):
        1. Run ( E ).
        2. Compare output strings with ( w ).
        3. If ( w ) matches, ( M ) outputs accept.
    • Direction 2: If a Turing machine ( M ) recognises a language ( L ), an enumerator ( E ) can be constructed.
      • Operation:
        1. Run ( M ) for a set number of steps on each input string from the alphabet.
        2. If ( M ) accepts, ( E ) outputs the corresponding string.
• Recursively Enumerable: A language is recursively enumerable if an enumerator exists for it.

Recursive Languages

• Decider: A Turing machine that always terminates either in an accepting or a rejecting state, thus deciding a language ( L ).
• Turing-Decidable (Recursive) Language: A language is Turing-decidable if there exists a Turing machine that decides it.

Lemmas and Theorems

• Lemma 4: If ( L ) is Turing-decidable, then ( L ) is Turing-recognisable.
• Lemma 5: If ( L ) is Turing-decidable, then its complement ( \overline{L} ) is Turing-decidable.
• Theorem 16: A language ( L ) is Turing-decidable if and only if both ( L ) and ( \overline{L} ) are Turing-recognisable.
  • Note: Proofs for Lemma 4, Lemma 5, and Theorem 16 are given as exercises.