Your computer can run a game, a web browser, and a program that pretends to be a console from 1985. Nobody built it separately for each job. Why can one machine run all of them? And why can no checker always decide whether an arbitrary program will eventually stop on a given input?
We have seen a host run scripts and limit the work they can do. Before opening the virtual machine that executes them, consider why one program can run another at all—and why a host needs a step budget instead of a perfect test for whether a script will finish.
Both answers come from a model of computing published in 1936, years before anyone built an electronic computer. We will build the model by hand, then connect it to code bytes, program analysis, and bounded interpreters.
Section: A machine small enough to hold in your head.
The mathematician Alan Turing wanted to pin down exactly what “following a procedure” means. He imagined the simplest mechanism that could still carry out any step-by-step method a person could follow with pencil and paper:
a tape divided into cells, each holding one symbol, as long as it needs to be;
a head that sits over one cell at a time and can read or overwrite it;
a state, which is a single named setting the machine is in, such as carry or done;
a transition table, often called a rule table, that says, for every combination of current state and symbol under the head, what to write, which way to move, and which state comes next.
That mechanism is a Turing machine. It runs by repeating one step: look up the table row for the current state and the symbol under the head, write, move one cell left or right or stay put, and switch state. When no row matches, the machine stops. The usual word for stopping is halting.
Here is a complete machine that adds one to a binary number. It starts in state carry with the head on the rightmost digit:
The state done has no matching table rows, so reaching it halts the machine. Put 1011 (eleven) on the tape, with blank cells, drawn _, on either side. The highlighted cell is the one under the head:
This is ordinary school addition. Adding one to a 1 gives 0 and carries one to the left; adding the carry to a 0 gives 1 and the carry is used up. The third row handles 111: the carry runs past the leftmost digit into a blank cell, and the machine writes a new leading 1, giving 1000.
Three rows are the whole program, yet they handle a number of any length. Notice also what the machine does not know. Nothing in the table mentions “eleven” or “twelve”. The machine moves symbols around, and the meaning — binary numbers — comes from us. Lesson 1.2 said the same thing about bytes in memory: meaning comes from the code that reads them, not from the bytes.
Section: How the model relates to a computer.
Line the parts up with the computer you are using now:
These are analogies, not identical parts. Two differences matter:
A real C P U, central processing unit, can jump straight to an address, while the head walks one cell at a time. In the idealized model, that changes speed rather than the set of computations: the head could eventually walk to a reachable cell.
In brief: A small computing model separates the essential steps of calculation from the hardware used to perform them.
A real computer also has a fixed amount of memory, while the tape never runs out. That difference does matter to a literal claim about what can be computed: a finite machine eventually runs out of states or memory. The Turing machine tells us what a procedure could compute if it had as much time and storage as it needed. Real computers approximate that model for tasks that fit their resource limits.
Section: The universal machine: programs are data.
Turing’s most important idea came next. A transition table is itself only a list of symbols, so it can be written onto a tape like anything else. He then described a single machine, the universal Turing machine, that reads another machine’s transition table from its tape and carries out that machine’s steps one by one. One fixed machine can therefore imitate every other machine. To change what it does, you change what is on the tape, not the machine.
Alternative: A program can be input to another program. An interpreter reads that input and performs the operations it describes.
The computers and game processes in this book use stored programs: instructions and data are represented as bytes in addressable memory. This arrangement is called a stored-program computer. It lets the tools in this book inspect code bytes as well as game data, subject to memory protections. Here are a few bytes of a running game, part code and part data:
That has three consequences you will use constantly:
Code can be read like data. A disassembler reads code bytes and names the instructions they encode. That is how Chapter 2 turned a game’s machine code into readable assembly.
Code can be written like data. A software breakpoint is a single byte, hexadecimal C C, written over the first byte of an instruction ( Lesson 2.4 ). A code cave is new instructions written into memory, and a patch is old ones overwritten ( Lesson 2.9 ).
Code can run other code. Lua’s virtual machine in Lesson 11.9 is a program whose data is another program. An emulator, in Lesson 13.9, is a program whose data is the software of an entire other computer.
Here is the second point in bytes. A debugger sets a breakpoint on the first instruction above:
If code is just bytes, what stops a program from overwriting its own instructions? Nothing in the model does. The protection comes from outside it: the operating system marks each page of memory as readable, writable, executable, or some combination, and the C P U refuses any access the marks forbid. That is why Lesson 6.5 treats a page that is both writable and executable as worth a second look. It is a place where data can become code.
Section: Turing complete: when a system can compute anything.
A system is Turing complete when it can carry out anything a Turing machine can, given enough time and memory. In their idealized forms, general-purpose languages such as Rust, C++, Lua, and assembly qualify. So do some systems nobody designed as computers. Conway’s Game of Life, a grid of cells that live or die according to neighboring live-cell counts, can be arranged to compute anything in this sense. Players have also built working processors inside Minecraft out of redstone circuits; any one build is still limited by the game’s actual resources.
The useful consequence for you concerns what a game loads. A texture or a sound file is data: the game reads it in one fixed way, so the most a strange one can usually do is trip over a bug in the code that reads it. A script is different. A Wesnoth add-on can contain Lua, and a mod that ships a script is shipping a program. A Turing-complete script can compute anything within the resources available to it, and what it is allowed to touch is limited by what its host exposes. That is why the Lua lessons separate the script’s behavior from the game objects and operations its host permits.
Section: Some questions no program can answer.
The universal machine raises an obvious hope. If one program can run any other program, perhaps one program could also examine any other program and tell you what it will do. Turing showed in the same 1936 paper that this is impossible. The version below is the standard modern form of his argument, and it is short enough to follow in full.
Take the simplest question you could ask: will this program eventually stop, or run forever? Suppose someone hands you a checker, halts(program, input), that always answers that question correctly. Now write this program and call it contrary:
Code example. The surrounding prose explains this example; the full lesson contains the exact code.
Now feed contrary to itself:
If the checker says contrary(contrary) halts, contrary loops forever. If the checker says it runs forever, contrary stops at once. Whatever the checker answers, it is wrong, so a checker that is always right cannot exist. This is the halting problem: no program can correctly decide, for every program and every input, whether that program halts.
The same limit reaches other questions about what a program does, such as “Does it ever write to this address?” A question that no single method answers correctly for every possible program is called undecidable. The optional reference below gives the general result.
Section: What that means for the tools in this book.
Undecidable does not mean hopeless. It means no tool can be right about every program. Real tools cope by approximating, and every approximation has a known way to be wrong:
A disassembler has to decide which bytes are instructions and which are data. On x86, instructions have different lengths, so starting one byte too early or too late produces a listing that looks plausible and is completely wrong. Disassemblers use good heuristics and usually get it right. When a listing looks odd, check it against what the program actually executes in a debugger.
A decompiler rebuilds loops, variables, and types that the compiler threw away. Its output is a well-informed guess, so treat it as one.
A signature scanner, whether antivirus or anti-cheat, cannot decide what arbitrary code does. It looks for known byte patterns and known behavior instead, so it can miss what it has never seen and occasionally flag something harmless.
A step budget exists because a host cannot know in advance whether a script will ever finish. All it can decide is how long it is willing to wait: the budget guarantees that the host stops waiting, not that the script would never have finished. Lesson 11.7 sets such a budget for Lua scripts, and the virtual machine in Lesson 11.9 checks one in its loop.
The practical distinction follows directly. Reading code tells you what might happen. Running it under control, on a specific input, tells you what did happen on that input. That is why the lessons pair reading code with running it.
Section: Run the machine yourself.
The portable lab turing_machine_lab.rs is a short Turing machine simulator. Its transition tables are plain text that the simulator reads when it starts. One fixed program can therefore run different machines described by its input, within the lab’s finite memory and step budget. In the Rust source, machine.rules names the map of transition-table rows. That demonstrates the universal-machine idea without claiming that the lab itself has an unbounded tape.
Code example. The surrounding prose explains this example; the full lesson contains the exact code.
The heart of the simulator is the step loop. It looks up a matching transition row, gives up if the budget is spent, and otherwise writes, moves, and switches state:
Code example. The surrounding prose explains this example; the full lesson contains the exact code.
The order of the two checks matters. A machine that reaches done on its very last budgeted step has halted, and the loop reports it that way rather than calling it a timeout.
Build it, then run it from the rust-labs folder:
Terminal window
Code example. The surrounding prose explains this example; the full lesson contains the exact code.
The lab adds one to three numbers, including 111 so you can watch the carry run off the end. Then it runs a machine with one repeating transition that writes 1s forever and stops it with a budget. Finally, it feeds the simulator a malformed transition table to show that a program which is only data still has to be validated before it runs. The tests beside it check every number from 0 to 64 and the budget edge case.
Section: Optional reference: Rice’s theorem and a second machine.
Nothing later in the book depends on this reference. It extends the halting result to other questions and gives a second machine to trace by hand.
Additional detail: Optional reference: Rice's theorem and a second machine.
Section: Rice’s theorem: questions about what a program does.
The damage does not stay with halting. A later result, Rice’s theorem, extends it to essentially every question about what a program does, as opposed to how its text is written. “Does it ever write to this address?” “Does it ever send a network message?” “Is this instruction ever executed?” For each one, no single method answers correctly for every possible program, so each is undecidable.
Section: A second machine: flip every digit.
Another small machine could flip every digit of a binary number, turning 1011 into 0100. It needs only two transition rows, because the machine halts when it reaches a blank with no matching table row. Starting at the leftmost digit, it applies four transitions to flip four digits and then stops when the head reaches the blank.
Section: What the model explains.
A Turing machine has a tape, a head, a state, and a transition table. Its three-row incrementer carries left until it can turn a 0 into a 1; if the carry runs off the left end, a new 1 is needed. Computer memory, addresses, registers, and instructions play roles analogous to tape, head position, state, and transitions. Stored programs let a debugger place a breakpoint by replacing an instruction byte. A mod with a script is executable behavior, and no general tool can decide whether every possible program halts. Disassemblers, decompilers, scanners, and step budgets therefore provide bounded observations rather than universal answers.
From Lua Source to a Tiny Virtual Machine now follows a short expression from text into executable operations. Its interpreter uses the same practical limit as the simulator here: execute a bounded number of steps and report what happened, without claiming to decide the behavior of every possible program.