An interactive visual environment to understand the fundamental model of computation — step by step, transition by transition.
| From | Read | Write | Move | To |
|---|
state, read → next, write, L|R|Sq0, a → q1, X, R | Use B for blank | S = stay | Lines starting with // are comments
A Turing Machine is a 7-tuple M = (Q, Σ, Γ, δ, q₀, q_acc, q_rej) where:
The machine begins with its input written on the tape and the read/write head at the leftmost cell. At each step, it reads the current cell, writes a symbol, moves the head left or right, and transitions to a new state.
Computation halts when the machine enters the accept or reject state. If it loops forever, the input is said to not be decided by that machine.
A language is Turing-decidable if some TM halts on every input. A language is Turing-recognizable if some TM accepts every member, but may loop on non-members.
The Church-Turing thesis states that every effectively computable function can be computed by a Turing Machine. This is not a provable theorem but an empirical hypothesis supported by many decades of research.
Key theoretical results include the Halting Problem (undecidable), Rice's Theorem (every non-trivial semantic property of TMs is undecidable), and the existence of Universal Turing Machines which can simulate any other TM.
The study of Turing Machines underpins modern complexity theory: the classes P, NP, PSPACE, and others are defined in terms of resource-bounded Turing Machines.
This Turing Machine Simulator is a project for the Theory of Automata & Formal Languages course. It provides a fully interactive, visual environment to construct, run, and study Turing Machines step by step.
Sipser, M. — Introduction to the Theory of Computation
Use B in the transition table to represent the blank tape symbol (□).