Turing Machines and the Universal Machine
A model with finite states, transition rules, a read-write head and an unbounded tape. A universal Turing machine takes an encoded machine description and input, then simulates that machine. Real computers have finite resources.
What a learner can do afterwards
- Run a small Turing machine on a starting tape and give the tape when it halts
- Say what the tape adds that a fixed set of states alone cannot provide
- Explain how a universal Turing machine simulates another machine from its description and input, and relate this to stored-program computers with finite resources
1 · Read
A finite state machine remembers its current state. A Turing machine also has a read-write tape, a head over one cell, and transition rules. Its states and symbol alphabet are finite, but the tape has no fixed size limit. A rule uses the current state and symbol to choose what to write, which way to move, and the next state. The next state may be the same state.
Here is a machine with working state A and halt state H. In A reading 1: write 0, move right, stay in A. In A reading 0: write 0, move right, stay in A. In A reading blank: enter H without writing or moving. Start in A over the first cell of 0 1 1. All other cells are blank. Track the tape, head and state after each rule.
The first step keeps the initial 0 and moves to the next cell. The next two steps replace each 1 with 0 and move right. The head then reads blank and enters H. The three original cells now read 0 0 0; the other cells remain blank. A run may halt or continue forever, depending on its rules and input.
The tape provides memory beyond a fixed set of states. At any finite step, only finitely many cells have been visited, but there is no fixed limit on how many a longer run may use. This permits computations that finite states alone cannot perform. The rules still matter: a machine that only erases symbols is not able to run every algorithm.
A universal Turing machine takes an encoded description of another Turing machine and an input for that machine. It follows the described rules to simulate the run. If the simulated machine halts, the simulation can finish with its result. If that run continues forever, the simulation continues too. A universal machine is itself a Turing machine, not a stronger model.
A stored-program computer uses the same hardware for different tasks by loading different instructions. This resembles universal simulation, but a laptop has finite memory and runs supported programs. The Turing model can simulate ordinary digital algorithms without a fixed memory bound. This concerns what an algorithm can compute, not how quickly it runs.
An unbounded tape does not make every problem solvable. For an undecidable yes/no problem, no algorithm both finishes and answers correctly on every input. Some individual cases may still be settled. The halting problem asks whether a supplied program will finish on a supplied input; it is undecidable in general. Faster hardware does not remove this limit.
Trace the state, tape and head. Universal machines simulate described machines; real computers have finite resources, and some problems remain undecidable.
Turing-machine lesson, questions and flashcards written for this dataset.
Additional Turing-machine readings and flashcards written for this dataset.
More to read
Recording a machine run
A tape snapshot is only part of a Turing-machine configuration. Record the current state and the head position as well. Identical tape contents can lead to different next actions when either of those changes.
Before starting, state the input placement, the initial state and the cell under the head. Mark nearby blanks. A blank is a tape symbol, not another spelling of zero.
For each step, find the rule matching the state and the symbol being read. Apply its write instruction, head movement and next-state instruction. Record the result before applying another rule. Keeping a symbol or state unchanged still follows the rule.
Use the machine's stated halting convention. In the lesson, reading a blank in A enters H without a write or movement. Other machines can use other rules. A completed trace establishes what happened on this input, not what happens on every input.
Descriptions that select a computation
A universal Turing machine has a fixed rule set that interprets descriptions of other Turing machines. Its input includes both a machine description and the data for the described machine.
During simulation, it maintains a representation of the other machine's configuration. It updates the represented state, tape and head according to the encoded rules. Supplying a different description selects a different computation without changing the universal machine's own rules.
A universal machine belongs to the same Turing-machine model as the machines it simulates. It is not a new model with a greater set of computable functions. Its useful property is that one fixed simulator can handle all the descriptions.
A stored-program computer also changes tasks when its instructions change. The comparison has a limit: physical memory is finite, and a device runs programs supported by its system. The mathematical tape has no fixed capacity.
Storage beyond finite control
The finite-state recogniser you met earlier can retain useful categories of input histories. It cannot retain a different state for every possible nesting depth of parentheses, because its state set is fixed.
Tape gives a Turing machine another place to keep records. Suitable rules can write a count or a record of unmatched openings, revisit it and update it as more input is processed. The control still has finitely many states.
No completed finite portion of a run visits infinitely many cells. Unbounded tape means there is no fixed capacity that all runs must stay within. A longer computation can use more storage.
Capacity and behaviour are separate questions. A machine that repeatedly erases symbols may have unbounded tape available, yet its rules never interpret an arbitrary program. Universal simulation requires a suitable interpreter rule set.
When waiting is not a decision procedure
A deciding algorithm for a yes/no problem must terminate and give the correct answer for every allowed input. Some problems have no algorithm meeting both requirements. These are undecidable problems.
For the halting problem, the input specifies a program and data for that program. The question is whether that particular run eventually finishes. Some cases are easy to settle, such as a program that stops immediately. No deciding algorithm handles every program and input correctly.
Running a simulation can establish halting when the simulated program stops. If the program is still running, the observation does not distinguish a run that stops later from one that continues forever. Waiting longer may resolve a particular example, but does not produce a general halting decider.
Faster hardware changes how quickly instructions execute. It does not turn an undecidable problem into a decidable one.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.