What Any Computer Can Compute
Build a Turing machine by hand, see why one computer can run every program, and learn which questions about programs no tool can always answer.
Cheatsheet for Lesson 11.8
A one-page summary of “What Any Computer Can Compute” you can keep beside your notes. Plain Markdown.
Lesson 11.8 — What Any Computer Can Compute: cheatsheet
- Remember: A small computing model separates the essential steps of calculation from the hardware used to perform them.
- Also useful: A program can be input to another program. An interpreter reads that input and performs the operations it describes.
Key terms
- Turing machine: That mechanism is a Turing machine.
- halting: The usual word for stopping is halting.
- stored-program computer: This arrangement is called a stored-program computer.
- Turing complete: A system is Turing complete when it can carry out anything a Turing machine can, given enough time and memory.
- halting problem: This is the halting problem: no program can correctly decide, for every program and every input, whether that program halts.
- undecidable: 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.
Formulas and patterns
carry 1 -> 0 L carry # 1 plus a carry is 0, and the carry moves left;carry 0 -> 1 S done # 0 plus a carry is 1, and the carry is used up;carry _ -> 1 S done # ran off the left end: write a new leading 1
Review
- Q: A game's Lua host runs scripts from downloaded mods. Why does it stop any script after a fixed number of steps instead of first checking whether the script will ever finish? A: No program can decide whether all scripts halt
- Q: Which list names the four parts of a Turing machine? A: A tape, a head, a current state, and a table of rules
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.
A machine small enough to hold in your head
Section titled “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
carryordone; - 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:
| State | Symbol under the head | Write | Move | Next state |
|---|---|---|---|---|
carry |
1 |
0 |
left | carry |
carry |
0 |
1 |
stay | done |
carry |
blank | 1 |
stay | done |
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:
carry. The head reads 1, so it writes 0 and moves left.carry. Another 1: write 0 and move left again.carry. The head reads 0, so it writes 1, stays put, and switches to done.done has no matching row, so the machine halts.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.
Carry one through a binary tape. This step-by-step trace needs JavaScript. Here is the code and where the run ends.
state = carry; head = rightmost digit
read the current symbol
if symbol == 1: write 0; move left
if symbol == 0: write 1; state = done
if symbol is blank: write 1; state = done
halt in done; read the resulting numberResult: 11 becomes 12, represented by 1100. Done has no further transition.
Final values: number = 11; state = done; head = 2; tape = _1100; result = 12.
Read every step of the lesson’s example
Step 1, line 1. Start with the selected inputs. Follow the highlighted operation and the changing state below.
number = 11.
Step 2, line 1. Start in carry at the rightmost digit.
number = 11; state = carry; head = 4; tape = _1011.
Memory: 0 = _; 1 = 1; 2 = 0; 3 = 1; 4 = 1 (head).
Step 3, line 2. The head reads 1, so this carry is not finished.
number = 11; state = carry; head = 4; tape = _1011.
Memory: 0 = _; 1 = 1; 2 = 0; 3 = 1; 4 = 1 (head).
Step 4, line 3. Write 0 and move one cell left with the carry still active.
number = 11; state = carry; head = 3; tape = _1010.
Memory: 0 = _; 1 = 1; 2 = 0; 3 = 1 (head); 4 = 0.
Step 5, line 2. The head reads 1, so this carry is not finished.
number = 11; state = carry; head = 3; tape = _1010.
Memory: 0 = _; 1 = 1; 2 = 0; 3 = 1 (head); 4 = 0.
Step 6, line 3. Write 0 and move one cell left with the carry still active.
number = 11; state = carry; head = 2; tape = _1000.
Memory: 0 = _; 1 = 1; 2 = 0 (head); 3 = 0; 4 = 0.
Step 7, line 4. The head found 0; write 1 and consume the carry.
number = 11; state = done; head = 2; tape = _1100.
Memory: 0 = _; 1 = 1; 2 = 1 (head); 3 = 0; 4 = 0.
Step 8, line 6. Result: 11 becomes 12, represented by 1100. Done has no further transition.
number = 11; state = done; head = 2; tape = _1100; result = 12.
Memory: 0 = _; 1 = 1; 2 = 1 (head); 3 = 0; 4 = 0.
How the model relates to a computer
Section titled “How the model relates to a computer”Line the parts up with the computer you are using now:
| Turing machine | Your computer |
|---|---|
| the tape | memory |
| where the head is | an address |
| the current state | the CPU’s registers, including the instruction pointer |
| the transition table | the program, carried out through the CPU’s instruction set |
| one step | one instruction |
These are analogies, not identical parts. Two differences matter:
A real CPU 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.
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.
The universal machine: programs are data
Section titled “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.
1 Row 1 matches: write 0, move left
carry, 1 → write 0, leftrule row 1 · next state carry101▲0carry with a 1 under the head matches row 1: 1011 becomes 1010.
2 Row 1 matches again
carry, 1 → write 0, leftrule row 1 · next state carry10▲00The next symbol is also 1, so the same row applies: 1010 becomes 1000.
3 Row 2 matches: write 1, done
carry, 0 → write 1, stayrule row 2 · next state done11▲00carry meets 0: write 1 and stop. 1100 is 1011 plus one. Different rule data would make the same interpreter compute something else.
The three rule rows in the table above are data. The tape starts as 1011 in state carry; each step the interpreter finds the row for its state and the symbol under the head, then does what that row says. ▲ marks the cell under the head.
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:
mov eax, [ebp+8]add ecx, eaxu32 100That 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,
0xCC, 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:
int3, then two leftover bytesint3 and stops for the debugger instead of loading eax.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 CPU 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.
Turing complete: when a system can compute anything
Section titled “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.
Some questions no program can answer
Section titled “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:
contrary(program): if halts(program, program): ask what program does when fed itself loop forever else: stopNow 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.
What that means for the tools in this book
Section titled “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.
Run the machine yourself
Section titled “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.
turing_machine_lab.rs
Show the codeHide the code
//! Turing machine lab for Lesson 1.11.
//!
//! The simulator's "program" is a plain-text rule table, read at run time.
//! That makes the simulator a small universal machine: one fixed program
//! that carries out whatever machine its input describes. It runs a binary
//! incrementer, then a machine that never halts, under a step budget.
use std::collections::{BTreeMap, HashMap};
use std::error::Error;
use std::fmt;
const BLANK: char = '_';
/// Adds one to a binary number. Start on the rightmost digit in `carry`.
const INCREMENTER: &str = "\
carry 1 -> 0 L carry # 1 plus a carry is 0, and the carry moves left
carry 0 -> 1 S done # 0 plus a carry is 1, and the carry is used up
carry _ -> 1 S done # ran off the left end: write a new leading 1
";
/// Writes 1s to the right forever. This machine never halts.
const FILLER: &str = "\
fill _ -> 1 R fill
";
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Move {
Left,
Right,
Stay,
}
impl Move {
fn delta(self) -> i64 {
match self {
Move::Left => -1,
Move::Right => 1,
Move::Stay => 0,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Rule {
write: char,
movement: Move,
next: usize,
}
/// A machine is nothing but a rule table. States are stored as numbers;
/// their names exist only so people can read the table and the output.
#[derive(Debug)]
struct Machine {
state_names: Vec<String>,
rules: HashMap<(usize, char), Rule>,
}
#[derive(Debug, PartialEq, Eq)]
enum ParseError {
WrongFieldCount { line: usize },
BadSymbol { line: usize },
BadMove { line: usize },
DuplicateRule { line: usize },
}
impl fmt::Display for ParseError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
ParseError::WrongFieldCount { line } => {
write!(
formatter,
"line {line}: expected `state read -> write move next`"
)
}
ParseError::BadSymbol { line } => {
write!(
formatter,
"line {line}: a symbol must be exactly one character"
)
}
ParseError::BadMove { line } => {
write!(formatter, "line {line}: the move must be L, R, or S")
}
ParseError::DuplicateRule { line } => {
write!(
formatter,
"line {line}: a rule for this state and symbol already exists"
)
}
}
}
}
impl Error for ParseError {}
impl Machine {
/// Parses lines of the form `state read -> write move next`, where `move`
/// is `L`, `R`, or `S` (stay). Text after `#` is a comment.
fn parse(source: &str) -> Result<Self, ParseError> {
let mut machine = Machine {
state_names: Vec::new(),
rules: HashMap::new(),
};
for (index, raw_line) in source.lines().enumerate() {
let line = index + 1;
let text = raw_line.split('#').next().unwrap_or_default().trim();
if text.is_empty() {
continue;
}
let fields: Vec<&str> = text.split_whitespace().collect();
let [state, read, arrow, write, movement, next] = fields.as_slice() else {
return Err(ParseError::WrongFieldCount { line });
};
if *arrow != "->" {
return Err(ParseError::WrongFieldCount { line });
}
let read = single_symbol(read).ok_or(ParseError::BadSymbol { line })?;
let write = single_symbol(write).ok_or(ParseError::BadSymbol { line })?;
let movement = match *movement {
"L" => Move::Left,
"R" => Move::Right,
"S" => Move::Stay,
_ => return Err(ParseError::BadMove { line }),
};
let state = machine.state_id(state);
let next = machine.state_id(next);
let rule = Rule {
write,
movement,
next,
};
if machine.rules.insert((state, read), rule).is_some() {
return Err(ParseError::DuplicateRule { line });
}
}
Ok(machine)
}
fn state_id(&mut self, name: &str) -> usize {
if let Some(id) = self.find_state(name) {
return id;
}
self.state_names.push(name.to_owned());
self.state_names.len() - 1
}
fn find_state(&self, name: &str) -> Option<usize> {
self.state_names.iter().position(|known| known == name)
}
fn name(&self, state: usize) -> &str {
&self.state_names[state]
}
}
fn single_symbol(text: &str) -> Option<char> {
let mut symbols = text.chars();
let symbol = symbols.next()?;
symbols.next().is_none().then_some(symbol)
}
/// An unbounded tape. Only non-blank cells are stored, so the tape can grow
/// in either direction without shifting anything.
#[derive(Debug, Default)]
struct Tape {
cells: BTreeMap<i64, char>,
}
impl Tape {
fn with_contents(text: &str) -> Self {
let mut tape = Tape::default();
for (position, symbol) in (0_i64..).zip(text.chars()) {
tape.write(position, symbol);
}
tape
}
fn read(&self, position: i64) -> char {
self.cells.get(&position).copied().unwrap_or(BLANK)
}
fn write(&mut self, position: i64, symbol: char) {
if symbol == BLANK {
self.cells.remove(&position);
} else {
self.cells.insert(position, symbol);
}
}
/// The stretch of tape from the first to the last non-blank cell.
fn contents(&self) -> String {
let (Some((&first, _)), Some((&last, _))) =
(self.cells.first_key_value(), self.cells.last_key_value())
else {
return String::new();
};
(first..=last).map(|position| self.read(position)).collect()
}
}
#[derive(Debug, PartialEq, Eq)]
enum Outcome {
Halted { state: usize, steps: u64 },
OutOfBudget { steps: u64 },
}
/// Runs until no rule matches (the machine halts) or the budget is spent.
///
/// The budget is not optional. No simulator can know in advance whether an
/// arbitrary machine will ever halt, so all it can decide is how long it is
/// willing to wait.
fn run(machine: &Machine, tape: &mut Tape, head: i64, state: usize, budget: u64) -> Outcome {
let mut head = head;
let mut state = state;
let mut steps = 0;
loop {
let Some(rule) = machine.rules.get(&(state, tape.read(head))) else {
return Outcome::Halted { state, steps };
};
if steps == budget {
return Outcome::OutOfBudget { steps };
}
tape.write(head, rule.write);
head += rule.movement.delta();
state = rule.next;
steps += 1;
}
}
fn describe(machine: &Machine, outcome: &Outcome) -> String {
match outcome {
Outcome::Halted { state, steps } => {
format!("halted in `{}` after {steps} steps", machine.name(*state))
}
Outcome::OutOfBudget { steps } => format!("still running after {steps} steps, gave up"),
}
}
fn main() -> Result<(), Box<dyn Error>> {
println!("1. A three-rule program that adds one to a binary number");
let incrementer = Machine::parse(INCREMENTER)?;
let carry = incrementer
.find_state("carry")
.ok_or("the incrementer has no `carry` state")?;
for number in ["1011", "111", "0"] {
let mut tape = Tape::with_contents(number);
let rightmost = i64::try_from(number.len())? - 1;
let outcome = run(&incrementer, &mut tape, rightmost, carry, 100);
let result = tape.contents();
let before = u64::from_str_radix(number, 2)?;
let after = u64::from_str_radix(&result, 2)?;
println!(
" {number:>4} ({before:>2}) -> {result:>4} ({after:>2}) {}",
describe(&incrementer, &outcome)
);
}
println!("\n2. A machine that never halts, stopped by a budget");
let filler = Machine::parse(FILLER)?;
let fill = filler
.find_state("fill")
.ok_or("the filler has no `fill` state")?;
let mut tape = Tape::default();
let outcome = run(&filler, &mut tape, 0, fill, 1_000);
println!(
" {}; the tape now holds {} symbols",
describe(&filler, &outcome),
tape.contents().len()
);
println!("\n3. The program is data: a malformed table is rejected, not run");
match Machine::parse("carry 1 -> 0 X carry") {
Ok(_) => println!(" unexpectedly accepted"),
Err(error) => println!(" rejected: {error}"),
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
fn increment(number: &str, budget: u64) -> (String, Outcome) {
let machine = Machine::parse(INCREMENTER).unwrap();
let carry = machine.find_state("carry").unwrap();
let mut tape = Tape::with_contents(number);
let rightmost = i64::try_from(number.len()).unwrap() - 1;
let outcome = run(&machine, &mut tape, rightmost, carry, budget);
(tape.contents(), outcome)
}
#[test]
fn incrementer_adds_one_to_every_small_number() {
for value in 0_u64..=64 {
let (result, outcome) = increment(&format!("{value:b}"), 100);
assert!(
matches!(outcome, Outcome::Halted { .. }),
"{value}: {outcome:?}"
);
assert_eq!(u64::from_str_radix(&result, 2).unwrap(), value + 1);
}
}
#[test]
fn carry_can_run_off_the_left_end() {
let (result, outcome) = increment("111", 100);
assert_eq!(result, "1000");
assert!(matches!(outcome, Outcome::Halted { steps: 4, .. }));
}
#[test]
fn halting_on_the_last_budgeted_step_still_counts_as_halting() {
let (result, outcome) = increment("1011", 3);
assert_eq!(result, "1100");
assert!(matches!(outcome, Outcome::Halted { steps: 3, .. }));
}
#[test]
fn a_machine_that_never_halts_runs_out_of_budget() {
let machine = Machine::parse(FILLER).unwrap();
let fill = machine.find_state("fill").unwrap();
let mut tape = Tape::default();
assert_eq!(
run(&machine, &mut tape, 0, fill, 50),
Outcome::OutOfBudget { steps: 50 }
);
assert_eq!(tape.contents(), "1".repeat(50));
}
#[test]
fn malformed_rules_are_rejected_with_their_line() {
assert_eq!(
Machine::parse("a 1 0 L b").unwrap_err(),
ParseError::WrongFieldCount { line: 1 }
);
assert_eq!(
Machine::parse("a 1 -> 0 X b").unwrap_err(),
ParseError::BadMove { line: 1 }
);
assert_eq!(
Machine::parse("a 10 -> 0 L b").unwrap_err(),
ParseError::BadSymbol { line: 1 }
);
assert_eq!(
Machine::parse("a 1 -> 0 L b\na 1 -> 1 R b").unwrap_err(),
ParseError::DuplicateRule { line: 2 }
);
}
}carry 1 -> 0 L carry # 1 plus a carry is 0, and the carry moves leftcarry 0 -> 1 S done # 0 plus a carry is 1, and the carry is used upcarry _ -> 1 S done # ran off the left end: write a new leading 1The 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:
fn run(machine: &Machine, tape: &mut Tape, head: i64, state: usize, budget: u64) -> Outcome { let mut head = head; let mut state = state; let mut steps = 0; loop { let Some(rule) = machine.rules.get(&(state, tape.read(head))) else { return Outcome::Halted { state, steps }; }; if steps == budget { return Outcome::OutOfBudget { steps }; } tape.write(head, rule.write); head += rule.movement.delta(); state = rule.next; steps += 1; }}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:
cargo run --bin turing_machine_labThe 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.
Optional reference: Rice’s theorem and a second machine
Section titled “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.
Optional reference: Rice's theorem and a second machine
Rice’s theorem: questions about what a program does
Section titled “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.
A second machine: flip every digit
Section titled “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.
What the model explains
Section titled “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.
Why a budget, not a prediction?
A game's Lua host runs scripts from downloaded mods. Why does it stop any script after a fixed number of steps instead of first checking whether the script will ever finish?
This is the halting problem in practice. A checker that always correctly predicts whether a program halts cannot exist, because a program built to do the opposite of the checker's answer makes every answer wrong. So a host does not try to predict. It counts steps inside the execution loop and stops a script that runs past its budget, exactly as the small Lua virtual machine's loop does.
Finished Lesson 11.8?
Mark it done and the lesson list shows a beside it. A chapter whose lessons are all done is marked done too. Progress is saved in this browser only.
Plain Markdown, saved in this browser.
This book grew out of the original Game Hacking Academy by attilathedud and has been rewritten as a beginner-first course. Like the original repository, its source is published under the Apache License 2.0.