4.6.16 · D5Theory of Computation
Question bank — Universal Turing machine
Setup you need for these traps
Before the questions, we pin down the vocabulary they lean on, so this page stands on its own.
The simulation is one fetch–execute cycle repeated forever: read from Tapes 3 and 2, scan Tape 1 for the matching rule, then write, move, and update state. That cycle is drawn here.
True or false — justify
A UTM is more computationally powerful than an ordinary Turing machine.
False — a UTM is an ordinary Turing Machine, same computable class; "universal" means it can imitate all of them, not that it can compute something none of them can.
A UTM can solve the Halting Problem.
False — since a UTM is just a TM, it inherits every limit of TMs; if it could detect all loops it would decide halting, which is proven impossible by Diagonalization.
The encoding must be unique for each machine .
False — infinitely many valid encoding schemes exist; we only fix one so the parser is predictable. Any finite, decodable scheme yields an equivalent UTM.
A UTM needs infinitely many states because there are infinitely many machines to simulate.
False — has a fixed finite control; the unbounded complexity lives on the tape inside , which is exactly the Stored-Program Computer idea.
means and always take the same number of steps.
False — the result (accept/reject/loop) matches, but spends many of its own steps per single step of (scanning Tape 1 to fetch each rule), giving an -style slowdown; equality is of outcome, not runtime.
If halts on , then on is guaranteed to halt.
True — faithfully mirrors , so it reaches or after finitely many simulated steps exactly when does.
Because a program is data, can be fed its own description .
True — code and data share one alphabet, so is a legal input string; this self-reference seeds Diagonalization.
A single-tape UTM is impossible; universality requires multiple tapes.
False — the multi-tape design is just for clarity; Multi-tape vs Single-tape TM equivalence lets you compress onto one tape at a polynomial slowdown.
The existence of the UTM is what the Church-Turing Thesis proves.
False — the UTM is a theorem Turing constructed; the thesis is an unprovable claim that "effectively computable" equals "TM-computable". They support each other but are different kinds of statement.
The language of encodings that accepts is recursively enumerable.
True — accepts exactly when accepts , and it may loop otherwise, which is the defining behaviour of a recursively enumerable set.
Spot the error
" reads once, memorises all rules in its states, then runs ."
The error is "memorises in its states" — has a fixed finite state set, so it cannot store an arbitrarily large rule table internally; it re-scans on Tape 1 each fetch.
"To simulate , hard-wires into its own transition function."
Hard-wiring would make a different per machine, defeating universality. treats as data on Tape 1 it looks up, never as part of its own control.
"Since loops on , a well-designed prints 'infinite loop' and stops."
Detecting looping in general is the undecidable Halting Problem; the correct behaviour is for to loop right along with . Stopping with a verdict would be a fantasy machine, not a real TM.
" can accept even when rejects , if 's simulation is smart."
No — faithfulness forbids this. accepts iff accepts; any deviation would mean is not simulating but computing something else.
"The tape alphabet of must contain every symbol used by every possible ."
Impossible, since that set is unbounded. uses a fixed alphabet and encodes 's symbols as blocks (e.g. unary numbers) on Tape 2, so a finite alphabet represents infinitely many.
"Because can run , it can decide whether it will halt on that input."
Running itself is legal, but predicting the result before running is exactly the self-referential trap Diagonalization uses to prove halting is undecidable — so no, it cannot decide it.
Why questions
Why must the encoding be finite?
Because (states) and (tape alphabet) are finite, the rule table has finitely many rows, so the whole machine fits in a finite string — a tape holding an infinite description could never be fully read.
Why does the exact encoding scheme not matter?
All reasonable schemes are inter-convertible by a TM, so a UTM built for one can be adapted to another; only finiteness and decodability are essential.
Why does the UTM prove computation is a "universal phenomenon" rather than special hardware?
One fixed machine reproduces the behaviour of every other, showing computation is a portable property of rules on data, not of any particular physical device — the root of von Neumann Architecture.
Why is "fixed CPU + variable program" the same idea as a UTM?
's finite control is the CPU, on Tape 1 is the program, and is the input data — the Stored-Program Computer literally instantiates the UTM separation.
Why can 's state count stay fixed while the machines it runs grow unboundedly complex?
All the growing complexity is stored as symbols on the tape; only needs enough states to parse and apply rules, an operation of bounded difficulty regardless of how many rules there are.
Why is treating a program as input data (self-reference) not a paradox by itself?
Feeding to just runs a simulation; the paradox only appears when you additionally demand a machine that decides halting and then feed it a description that contradicts its own verdict.
Edge cases
What does do when immediately halts in with no moves?
reads state on Tape 3 at the very first check and accepts at once — zero simulated transitions is a valid, correctly-mirrored run.
What if is a syntactically malformed string that describes no valid machine?
can be designed to detect the malformation and reject (or by convention treat it as a trivial machine that rejects everything); either way its behaviour on invalid code is fixed and well-defined.
What if is the empty string?
Empty input is fine — starts 's simulated Tape 2 blank and runs the fetch–execute loop normally; many machines are defined precisely for the empty-input case.
What if has no rule matching the current ?
This depends on 's definition: most conventions treat a missing transition as an immediate reject (halt), but some formulations use implicit accept, or an explicit "stuck" halt. scans Tape 1, finds no match, and reproduces whichever convention was defined with — it never invents a move.
What happens when 's head moves left off the start of its simulated tape?
This is only a question if uses a one-way-infinite tape (a left edge); many definitions use a two-way-infinite tape where "off the start" never occurs. must reproduce 's own convention — e.g. the head stays put on the leftmost cell — not impose its own.
What if the machine being simulated is itself running on some other machine's description?
Perfectly legal nesting — just simulates a simulation; the outcome still equals , only with layered polynomial overhead per level.
Recall One trap to remember above all
Which single misconception, once fixed, dissolves most UTM confusion? Answer: "The UTM is stronger than a TM." Once you see it is just a TM whose program lives on the tape, universality (flexibility) and its limits (still can't solve halting) both fall out naturally.