Turing Machines and the Universal Machine
A machine with a fixed set of states plus an unlimited tape it can read, write and move along. Adding the tape is enough to compute anything any computer can, and one such machine can read another's description and run it.
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 what a universal machine does, and why that is what a computer is
1 · Read
A Turing machine pairs a small set of states with a tape stretching as far as needed. In one step it reads the current symbol, writes a symbol, moves left or right, and changes state. That combination can compute anything any computer can.
Watch a tiny machine at work. Its tape reads 1 0 1 with the head on the first cell, in state A. Its rule says: 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 a blank, halt. It sweeps right turning every 1 into 0, then meets the blank and halts. The tape now reads 0 0 0. Running one by hand means tracking the tape, the head position, and the current state after every step.
The tape is what fixed states alone lack: memory without bound. Models of computation form a ladder, and the Turing machine sits at the top, because bolting on an endless tape removes the ceiling. Your hand run just showed it: the tape held every intermediate result the states could not.
The universal machine climbs one rung higher. It reads the description of another machine plus its input, then behaves exactly like it. Your laptop is that idea in silicon: one machine running any program, from stored apps to the operating system itself.
States plus an endless tape compute anything, and one universal machine can imitate them all.
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.