Exercises — Universal Turing machine

False. $U$ is itself an ordinary Turing machine — it is drawn from the exact same class. Whatever $U$ computes, some machine computes; and $U$ cannot break the ceiling of Turing computability (e.g. it still cannot solve the Halting Problem). Its gift is universality (it covers all machines with one fixed controller), not extra raw power.

• $⟨M⟩$ = the program / source code.
• $w$ = the input data.
• $U$ = the interpreter / CPU that runs the program on the data. This "code is just data fed to an interpreter" idea is the seed of the Stored-Program Computer and von Neumann Architecture.

Finite and fixed. $U$'s state count does not depend on which $M$ you feed it. All the unbounded complexity of $M$ lives on the tape (inside $⟨M⟩$), never inside $U$'s control. That separation — fixed controller, variable program on the tape — is the whole point.

Follow the parent's 3-tape layout: Tape 1 holds $⟨M⟩$, Tape 2 holds $M$'s tape, Tape 3 holds the current state.

1. Initialize: Tape 3 $=q_0$, Tape 2 head reads 0. (set up $M$'s start config)
2. Scan Tape 1 for the rule matching $(q_0,0)$: found $(q_{acc},1,R)$. (fetch)
3. Write 1 on Tape 2, move R, set Tape 3 $=q_{acc}$. (execute)
4. Tape 3 is $q_{acc}\Rightarrow U$ accepts, and the flipped cell reads 1.

Result: accept, cell $=1$. This is exactly $M(0)$: the bit got flipped from 0 to 1.

Fields in order: current state, read symbol, next state, write symbol, direction.

• $q_0\to 0^1=0$
• read 0 $\to 0$
• $q_1\to 0^2=00$
• write 1 $\to 00$
• $R\to 00$

Join with 1 between fields: $\text{rule}=010100100100$ The exact code is not sacred — any decodable finite string works — but it must be parseable by $U$'s finitely many states.

$U$ loops too. Each iteration of $U$'s simulation loop reproduces one step of $M$; if $M$ never reaches a halting mood, $U$ never reaches its own accept/reject, so $U$ runs forever. Not a bug — it is correctness. $U$ must faithfully mirror $M$. To instead print "loops forever" would require detecting non-halting for arbitrary $M$, which is the (undecidable) Halting Problem.

No. By the Multi-tape vs Single-tape TM equivalence, any $k$-tape machine can be simulated by a single-tape machine (the single tape stores the $k$ tracks with markers for each head). So a multi-tape $U$ and a single-tape $U$ recognise exactly the same languages. Multi-tape is chosen only for clarity of construction, not extra ability. (There is a polynomial time cost — roughly quadratic — but computability is unchanged.)

$L_U$ is recognisable but not decidable.

• Recognisable: run $U$ on $⟨M,w⟩$. If $M$ accepts, $U$ halts and accepts — so every "yes" instance is eventually confirmed. That is precisely the definition of a recursively enumerable language.
• Not decidable: a decider must always halt, answering yes and no. But if $M$ loops on $w$, $U$ loops, giving no answer. A total decider for $L_U$ would decide the Halting Problem, which is impossible. So $L_U\in \mathsf{RE}\setminus \mathsf{REC}$.

Because $U$ only runs $M$; it never predicts $M$'s future without running it. $U$ answers "does $M$ accept?" by simulation, and that simulation may never finish. The Halting Problem asks for a machine that always halts and tells you in advance whether $M(w)$ halts. $U$ does the former job (run and echo), not the latter (foretell). No contradiction: universality and undecidability coexist happily.

It computes the same result as $U(⟨M,w⟩)$, hence the same as $M(w)$.

• Well-formed because code and data share one alphabet, so $⟨U⟩$ is a perfectly legal input string to $U$. A program can be handed to another (or the same) interpreter as plain data.
• Reading it: the outer $U$ simulates the inner $U$, and the inner $U$ simulates $M$ on $w$. Two layers of interpretation — like running a Python interpreter written in Python. The final verdict equals $M(w)$. This self-application is the seed of Diagonalization.

• The thesis identifies the informal notion "algorithm" with the formal notion "Turing machine".
• Every algorithm is therefore some $M$, and $⟨M⟩$ is a finite string.
• $U$ can run any $⟨M⟩$. So a single fixed device ($U$) can execute every algorithm, merely by being handed its code. That is exactly the Stored-Program Computer promise: fixed hardware + swappable program = unlimited functionality. The UTM is the mathematical prototype your laptop physically realises.

Same idea, different clothes. There are infinitely many decodable finite encoding schemes; each yields a valid UTM. $U$ (using $⟨\cdot ⟩$) and $U^{\prime }$ (using $⟨\cdot {⟩}^{\prime }$) both simulate every $M$, so both recognise the universal language — modulo the encoding used to present inputs. A finite translator TM converts $⟨M{⟩}^{\prime }$ to $⟨M⟩$, so the machines are inter-simulable. The encoding is a convention, not a truth.

1. Assume a decider $H$ exists: a TM that always halts and outputs YES if $M$ halts on $w$, NO otherwise. (the hypothesis we will destroy)
2. Build a machine $D$ that takes $⟨M⟩$, runs $H$ on $⟨M,⟨M⟩⟩$ (feed $M$ its own code as data — legal because code is data), then:
   • if $H$ says "halts" → $D$ loops forever;
   • if $H$ says "not halt" → $D$ halts. (flip the answer — the "diagonal" move)
3. Ask: what does $D$ do on input $⟨D⟩$? Look at the red diagonal cell in the figure — the entry where a machine meets its own code.
   • If $D$ halts on $⟨D⟩$: by step 2, $H$ said "halts", so $D$ was built to loop — contradiction.
   • If $D$ loops on $⟨D⟩$: $H$ said "not halt", so $D$ was built to halt — contradiction.
4. Conclude: $D$ can neither halt nor loop consistently, so $H$ cannot exist. $H$ is undecidable. See Diagonalization and Halting Problem.

The UTM enabled step 2: $D$ runs other machines on encodings, which is exactly what $U$ does.

• Each $M$ has a finite $⟨M⟩$, a string over a fixed alphabet. Finite strings are countable (list them by length, then alphabetically). So TMs are countable.
• Languages are subsets of $\{0,1{\}}^{\ast }$; the set of all subsets is uncountable (Cantor).
• A countable set of machines cannot cover an uncountable set of languages, so some language has no recogniser — no TM, hence no matter which encoding, no $U$ input, describes it.
• No contradiction: $U$ only claims to run machines that exist. It never claimed to recognise languages that no machine recognises. Universality is over the countable family of TMs, exactly the family $⟨\cdot ⟩$ can encode.

$U$ keeps a fixed finite control unit and reads its instructions from the tape ($⟨M⟩$). Physically, that is a CPU with a fixed instruction-decoding circuit reading a program stored in the same memory as the data — the von Neumann Architecture and Stored-Program Computer. Because a program is just a string of the same kind as data, one device can be reprogrammed by loading a different string rather than rewiring — that is what "software" means. So the UTM is not only a theorem in the theory of computation; it is the blueprint proving that a single machine plus swappable code can do everything computable.

Cover everything and answer aloud: What single sentence captures why the UTM matters? Answer: One fixed, finite machine can run every algorithm, because a program is just data — which is exactly what makes software (and your computer) possible.