Languages Recognized by Turing Machines
You'll learn: How to formally define the set of strings that a Turing Machine can accept as a language.
The Core Idea
Just like DFAs and PDAs recognize certain classes of languages (regular and context-free), Turing Machines also recognize languages—but potentially much more complex ones. A Turing-recognizable language (also called recursively enumerable) is simply the set of all strings that some Turing Machine accepts.
Think of it this way: if you have a Turing Machine M, the language of M, written L(M), is the collection of every input string that causes M to eventually reach an accepting state and halt.
Formal Definition
For a Turing Machine M:
L(M) = { w | M accepts w }
This means: L(M) contains exactly those strings w where M, when started with w on its tape, transitions through states and eventually enters an accepting state.
What Makes This Different?
Unlike DFAs and PDAs, Turing Machines don't always halt. A machine might:
- Accept a string (halt in accepting state) → string is in L(M)
- Reject a string (halt in rejecting state) → string is not in L(M)
- Loop forever on a string → string is not in L(M)
The language only includes strings the machine accepts. If M loops forever on input w, then w ∉ L(M), even though M never explicitly rejected it.
Key Takeaway: A Turing-recognizable language is the set of all strings accepted by some Turing Machine; these languages represent the outer boundary of what can be computationally recognized, though not necessarily decided.