What does a universal Turing machine U take as input and do?

It takes an encoding of a TM together with w and behaves as M would on w

It takes only the input w and decides whether any TM accepts it

It takes a TM and rewrites it into a faster TM

It takes and decides whether M halts on every input

In the unary encoding used in the answer, how is a move delta(qi, Xj) = (qk, Xl, D) written and how are moves separated?

As 0^i 1 0^j 1 0^k 1 0^l 1 0^m, with moves separated by 11

As 0^i 0^j 0^k 0^l 0^m with no separators, moves separated by 1

As 1^i 0 1^j 0 1^k 0, with moves separated by 00

As 0^i 1 0^j 1 0^k, with moves separated by 111

In the three-tape organisation of U, what do T1, T2 and T3 hold respectively?

The encoding (program), M's current tape, and M's current state

The current state, the encoding , and M's tape

M's tape, the list of halting states, and the encoding

For the example M flipping bits, U runs on w = 01. What is the fetch-execute step and the final content of T2?

It matches the first two fields (state, symbol) against T1, then writes, moves and updates T3; T2 ends as 10

It matches only the symbol, ignoring the state; T2 ends as 01

It matches the state and symbol, then erases T1; T2 ends as 11

It matches the first two fields, then halts after one move; T2 ends as 11

2072 Chaitra

How a universal Turing machine works

Short answer

A Universal Turing Machine U simulates any TM M on input w given encoded ⟨M⟩ and w. U uses three tapes: program tape, M's tape, and M's state. For a simple bit-flipping machine M, U encodes each transition, then repeatedly fetches and executes the matching move, terminating when M halts. This shows a single fixed machine can execute arbitrary programs.

With the help of a suitable example, explain how a Universal Turing machine works.

Universal Turing machine (UTM)

A universal Turing machine U is a TM that can simulate any other TM M on any input w. It takes as input an encoding ⟨M⟩ of M together with w, and behaves as M would on w. It is the theoretical model of a stored-program computer: the program (⟨M⟩) is just data on the tape.

Encoding a TM

Use unary codes (Hopcroft, Ullman): states q1, q2 as 0, 00 …; symbols 0, 1, ⊔ as 0, 00, 000; directions L = 0, R = 00. A move δ(qi, Xj) = (qk, Xl, D) is written 0ⁱ1 0ʲ1 0ᵏ1 0ˡ1 0ᵐ, and moves are separated by 11. The whole input to U is ⟨M⟩ 111 w.

Example machine M (flips every bit; q1 start, q2 halting)

δ(q1, 0) = (q1, 1, R), δ(q1, 1) = (q1, 0, R), δ(q1, ⊔) = (q2, ⊔, L).

Codes: 01010100100, 01001010100, 01000100100010. So

⟨M⟩ = 01010100100 11 01001010100 11 01000100100010

Organisation of U (3 tapes)

 T1: <M>  (the program; read only)
 T2: current tape of M  (here: 0 1)
 T3: current state of M (here: 0 = q1)

How U runs M on w = 01

U copies w onto T2 and writes the start state q1 (code 0) on T3.
Fetch: U reads the symbol under the T2 head (0) and the state on T3 (q1), then scans T1 for the move whose first two fields match (0 for q1, 0 for symbol 0).
Execute: it finds 0 1 0 1 0 1 00 1 00, which says "go to q1, write 1, move right". U writes 1 on T2, moves the T2 head right, and puts q1 on T3.
Repeat. Next symbol 1 with q1 matches the second code: write 0, move R. T2 now holds 10.
The head reads ⊔ with q1: the third code says go to q2, write ⊔, move L. T3 holds q2 (00), which is a halting state, so U halts and accepts.

T2 finally contains 10, exactly M's result. If at some step no move matches, U halts as M would; if M loops, U loops.

The existence of U shows that one fixed machine is enough to run all programs, and it is the starting point of the proof that the halting problem is undecidable.

✓ Answer checked by Claude Opus 5.5 (high effort)

Define multitape Turing machine · Theory of Computation, chapter 4
What is a Turing machine; its operation · Theory of Computation, chapter 4
Multitape TM as copying machine · Theory of Computation, chapter 4
AI, Turing test, CSP examples · Artificial Intelligence, chapter 1
Universal motor and why so called · Electrical Machine, chapter 7
Short note: Universal motor · Electrical Machine, chapter 7
End bar and universal measuring machines · Metrology, chapter 14

All Theory of Computation chapter 5 questions →