Turing Machines & Computability
Learn about Turing machines, the universal Turing machine, the halting problem, and what it means for a problem to be computable.
📚 Learning Steps
💡 Study Tips
- • Read through at your own pace
- • Try the interactive simulators hands-on
- • Study the pseudocode — it appears in exams
- • Quiz yourself before moving on
Step 1: What is a Turing Machine?
📖 TheoryA Turing machine (TM) is a theoretical model of computation invented by Alan Turing in 1936. It is the most powerful standard model of computation — anything that can be computed by ANY algorithm can be computed by a Turing machine.
A Turing machine consists of:
•An infinite tape divided into cells, each holding a symbol (or blank □)
•A read/write head that can move LEFT or RIGHT along the tape, one cell at a time
•A finite set of states (including a start state and one or more halt states)
•A transition function: given (current state, symbol under head) → (new state, symbol to write, direction to move)
Unlike an FSM, a Turing machine has UNLIMITED memory (the infinite tape) and can both READ and WRITE. This is what makes it more powerful than finite state machines.
🎯 Key Points
- •Invented by Alan Turing in 1936 as a formal model of computation
- •Has an infinite tape (unlimited memory), a read/write head, and a finite set of states
- •Transition rule: (state, read) → (new state, write, move L/R)
- •MORE powerful than FSMs — the tape gives unlimited read/write memory
- •Can compute anything that any algorithm can compute (Church-Turing thesis)
0/8 steps completed