You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
A Turing machine is a theoretical model of computation invented by Alan Turing in 1936. Despite being remarkably simple in its design, a Turing machine can simulate any algorithm that any modern computer can execute. It is the most powerful computational model in the Chomsky hierarchy and defines the boundary of what is computable.
A Turing machine consists of:
| Component | Description |
|---|---|
| Infinite tape | Divided into cells, each containing a symbol from the tape alphabet. The tape extends infinitely in both directions. |
| Read/write head | Points to one cell at a time. Can read the symbol, write a new symbol, and move left or right. |
| State register | Stores the current state of the machine (from a finite set of states). |
| Transition function | A set of rules: given the current state and the symbol under the head, specify the symbol to write, the direction to move, and the next state. |
A Turing machine is defined as a 7-tuple (Q, Σ, Γ, δ, q₀, qₐ, qᵣ):
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.