Decidability and Recognisability in Turing Machines
Decidability and Recognisability are key concepts in the theory of computation. They describe the ability of Turing Machines (TMs) to solve problems and recognise languages. These properties define the boundaries of what is computable and help classify problems based on their solvability and complexity.
Decidability
A language is decidable (or recursive) if there exists a Turing Machine that can determine whether any given string belongs to the language and halts on all inputs.
Definition
A language L is decidable if there exists a Turing Machine M such that:
1. M accepts w if w ∈ L.
2. M rejects w if w ∉ L.
3. M halts on all inputs.This guarantees that M always provides a definitive answer (accept or reject) for any input string.
Example
The language L = {w | w is a valid arithmetic expression} is decidable because a Turing Machine can systematically parse and verify arithmetic expressions, halting with an accept or reject decision.
Key Characteristics
- A decidable language always has a halting Turing Machine.
- All decidable languages are also recognizable (see below).
Recognizability
A language is recognizable (or recursively enumerable) if there exists a Turing Machine that can confirm membership in the language for strings in the language. However, the machine may loop indefinitely for strings not in the language.
Definition
A language L is recognizable if there exists a Turing Machine M such that:
1. M accepts w if w ∈ L.
2. M may loop indefinitely if w ∉ L.This means the Turing Machine can recognize strings in the language but may fail to halt for strings outside the language.
Example
The language L = {w | w describes a halting Turing Machine} is recognizable because a Turing Machine can simulate another machine and accept if it halts. However, it cannot guarantee to halt if the machine being simulated does not halt.
Key Characteristics
- Recognizability does not guarantee halting for non-members.
- All decidable languages are recognizable, but not all recognizable languages are decidable.
Comparison of Decidability and Recognizability
| Aspect | Decidability | Recognizability |
|---|---|---|
| Definition | Machine halts and gives a definitive accept/reject for all inputs. | Machine halts and accepts for strings in the language but may not halt for strings outside. |
| Halting | Guaranteed to halt for all inputs. | Guaranteed to halt only for strings in the language. |
| Subset Relation | All decidable languages are recognizable. | Not all recognizable languages are decidable. |
| Example | Valid arithmetic expressions. | Halting problem (halting strings are recognized). |
Key Takeaways
- Decidability: A language is decidable if a Turing Machine can determine membership for all inputs and halts in all cases.
- Recognizability: A language is recognizable if a Turing Machine can confirm membership for inputs in the language but may not halt for non-members.
- All decidable languages are recognizable, but the reverse is not true.
- Recognizability and decidability are essential for understanding the limits of computation and unsolvable problems.