COMPSCI110 · Introduction to Computer Systems
Turing Machines & Computability
Module 10 of University of Auckland COMPSCI110 is the theory of what can be computed at all. You meet the Turing machine — a minimal model of any computing agent — its tape, states and 5-tuple instructions (i, j, k, s, direction), the rules that make an instruction set valid (deterministic), the distinction between halting and non-halting machines, and the Church–Turing thesis. It carries 6 marks on the final exam, and the reliable points come from tracing a small machine and judging whether an instruction set is valid or halts.
What this chapter covers
- 01What a model is (captures the essence, omits detail) and what any computing agent must do: read input, store/retrieve memory, act on instructions, output results
- 02The Turing machine (Alan Turing, 1936): a tape infinite in both directions, a finite set of states 1…k, and a set of instructions
- 03The 5-tuple instruction (i, j, k, s, direction): in state i reading symbol j, write k, change to state s, move left or right one cell
- 04Operating rules: begin in state 1, start on the leftmost non-blank symbol, no two rules share the same (state, symbol) pair, and if no rule applies the machine HALTS
- 05Halting vs non-halting: a machine halts at a (state, symbol) with no matching rule; it can loop forever if a rule always applies
- 06Valid (deterministic) instruction set: no duplicate (state, symbol) left-hand sides
- 07The Church–Turing thesis: anything computable can be computed by a Turing machine
Trace a bit-complementing Turing machine and decide if it halts
- +1Read the rules: (1, 0, 1, 1, R) means 'in state 1 reading 0, write 1, stay in state 1, move right'; (1, 1, 0, 1, R) means 'in state 1 reading 1, write 0, stay in state 1, move right'. Start in state 1 on the first 1. If ever no rule matches the current (state, symbol), the machine halts.
- +1Step 1: state 1, reading 1 → rule (1,1,0,1,R): write 0, stay in state 1, move right. Tape becomes 0 [0] 1 (head now on the middle cell).
- +1Step 2: state 1, reading 0 → write 1, move right → tape 0 1 [1]. Step 3: state 1, reading 1 → write 0, move right → tape 0 1 0, head now over a blank cell.
- +1State 1 reading a blank: there is no rule with left-hand side (1, b), so the machine HALTS. Final tape = 0 1 0 — the bitwise complement of the input 1 0 1.
Key terms
- Turing machine
- Alan Turing's 1936 model of a computing agent: a tape infinite in both directions (holding input, output and working memory), a finite set of states, and a set of instructions. Despite its simplicity it can, by the Church–Turing thesis, compute anything that is computable at all.
- Tape
- The Turing machine's storage: an unbounded strip of cells, each holding one symbol from a finite alphabet (including a blank). A read/write head sits over one cell at a time, reading its symbol and possibly overwriting it before moving one cell left or right. The tape serves as input, output and memory all at once.
- 5-tuple instruction (i, j, k, s, dir)
- One rule of a Turing machine: 'if in state i reading symbol j, write symbol k, change to state s, and move one cell in direction dir (left or right)'. The whole machine is just a finite list of these rules; the third field is what to write and the fourth is the next state.
- Halting vs non-halting
- A Turing machine halts when it reaches a (state, symbol) combination for which no rule exists. It runs forever (non-halting) if some rule always applies — for example rules that keep moving right over blanks without ever reaching a dead end. Deciding halting in general is itself a famous uncomputable problem.
- Deterministic (valid) instruction set
- An instruction set is valid/deterministic if no two rules share the same (state, symbol) left-hand side — so at every step at most one rule can apply and the machine's behaviour is unambiguous. Duplicate left-hand sides make the set invalid.
- Church–Turing thesis
- The claim that any function that can be computed by any effective procedure can be computed by a Turing machine — i.e. the Turing machine captures the whole of what 'computable' means. It is a thesis (a definition-like claim), not a theorem, but it underpins the theory of computability.
Turing Machines & Computability FAQ
What are the parts of a Turing machine?
Three things: a tape that is infinite in both directions (each cell holds one symbol and the tape doubles as input, output and memory), a finite set of states numbered 1…k, and a finite set of instructions written as 5-tuples. A read/write head sits over one cell; the instructions tell it what to write, which state to move to, and whether to step left or right. That minimal setup is enough to model any computation.
How do I know whether a Turing machine halts?
Trace it step by step, tracking the state and the symbol under the head. At each step, find the rule whose left-hand side matches the current (state, symbol). If a matching rule exists, apply it and continue; if no rule matches, the machine halts there. A machine loops forever when, from some configuration, a rule always applies and never leads to a dead end — so watch for cycles that keep finding a matching rule.
Can AI help me with Turing machines in COMPSCI110?
Yes, as a study aid. Sia can trace a machine on a given tape with you, check whether an instruction set is valid (deterministic), and reason about whether a machine halts. Use it to understand the model and rehearse on fresh instruction sets — it explains and checks your reasoning but does not do graded assignments or the exam for you, and the University of Auckland's academic-integrity rules apply to controlled assessments.
What does the 5-tuple (i, j, k, s, dir) mean?
It's one instruction read as a condition-and-action: the condition is 'in state i reading symbol j', and the action is 'write symbol k, change to state s, move one cell in direction dir (left or right)'. The order matters — field 3 (k) is what you write and field 4 (s) is the next state, so don't swap them. A whole machine is just a finite list of these tuples, and it must be deterministic (no two share the same i and j).
What is the Church–Turing thesis?
It's the claim that the Turing machine captures everything that can be computed — any function computable by some effective, mechanical procedure can be computed by a Turing machine. It means all reasonable models of computation are equivalent in power, which is why a device this simple is taken as the definition of 'computable'. It's called a thesis rather than a theorem because it links an informal idea (effective procedure) to a formal model, so it can't be strictly proved.
Exam move
Turing machines is 6 marks, and the dependable points come from careful tracing, so practise it as a mechanical drill. For a trace, keep a running record of the state, the symbol under the head, and the matching rule at each step; apply the 5-tuple exactly (write field 3, go to state field 4, move field 5) and remember the machine halts the moment no rule matches the current (state, symbol). Learn the operating rules cold — start in state 1 on the leftmost non-blank symbol, no two rules may share a (state, symbol) left-hand side — because 'is this a valid/deterministic instruction set?' is a favourite MCQ. Be able to argue whether a small machine halts or loops (a rule that always applies means it never halts). For the conceptual marks, state clearly what a Turing machine is, why it models any computing agent, and what the Church–Turing thesis asserts (and that it's a thesis, not a theorem). A few traced machines and one halting/validity question in timed conditions cover the module well.
Working through Turing Machines & Computability in COMPSCI 110? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI 110 Turing Machines & Computability question and get a clear, step-by-step explanation grounded in how COMPSCI 110 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
