--- title: "How a universal Turing machine works" subject: "Theory of Computation" chapter: 5 key: "semester_3/theory_of_computation:universal-tm-example" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/universal-tm-example site: BCT Engineering --- # How a universal Turing machine works Theory of Computation · Chapter 5: Undecidability - Asked in: 2072 Chaitra - Video: [Universal Turing Machine](https://www.youtube.com/watch?v=eKCX-4_jzck) — Neso Academy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/universal-tm-example - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-5 ## Question With the help of a suitable example, explain 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. ## Answer #### 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) ```text T1: (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 1. U copies w onto T2 and writes the start state q1 (code 0) on T3. 2. **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). 3. **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. 4. Repeat. Next symbol 1 with q1 matches the second code: write 0, move R. T2 now holds 10. 5. 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does a universal Turing machine U take as input and do? A. It takes only the input w and decides whether any TM accepts it B. It takes an encoding of a TM together with w and behaves as M would on w C. It takes a TM and rewrites it into a faster TM D. It takes and decides whether M halts on every input Answer: B. U receives and w and simulates M on w, so the program is just data on the tape, like a stored-program computer. (Key point: What a UTM does) 2. In the unary encoding used in the answer, how is a move delta(qi, Xj) = (qk, Xl, D) written and how are moves separated? A. As 0^i 1 0^j 1 0^k 1 0^l 1 0^m, with moves separated by 11 B. As 0^i 0^j 0^k 0^l 0^m with no separators, moves separated by 1 C. As 1^i 0 1^j 0 1^k 0, with moves separated by 00 D. As 0^i 1 0^j 1 0^k, with moves separated by 111 Answer: A. Fields of a move are separated by single 1s and different moves by 11; 111 separates from w. (Key point: Encoding of a move) 3. In the three-tape organisation of U, what do T1, T2 and T3 hold respectively? A. Input w, output, and the state B. The current state, the encoding , and M's tape C. The encoding (program), M's current tape, and M's current state D. M's tape, the list of halting states, and the encoding Answer: C. T1 holds (read only), T2 simulates M's tape and T3 stores M's current state code. (Key point: Three-tape organisation) 4. For the example M flipping bits, U runs on w = 01. What is the fetch-execute step and the final content of T2? A. It matches the first two fields (state, symbol) against T1, then writes, moves and updates T3; T2 ends as 10 B. It matches only the symbol, ignoring the state; T2 ends as 01 C. It matches the state and symbol, then erases T1; T2 ends as 11 D. It matches the first two fields, then halts after one move; T2 ends as 11 Answer: A. U finds the move whose state and symbol fields match, writes the new symbol, moves the head and updates the state. Flipping 0 and 1 in 01 gives 10, and U halts in q2. (Key point: Fetch-execute cycle and result) ## Related in Theory of Computation - [Define multitape Turing machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-define) — Theory of Computation, chapter 4 - [What is a Turing machine; its operation](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-define-operation) — Theory of Computation, chapter 4 - [Multitape TM as copying machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-copy) — Theory of Computation, chapter 4 ## Related in other subjects - [AI, Turing test, CSP examples](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aturing-test-pass-csp-examples) — Artificial Intelligence, chapter 1 - [Universal motor and why so called](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machine%3Auniversal-motor-construction-operation) — Electrical Machine, chapter 7 - [Short note: Universal motor](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machine%3Ashort-note-universal-motor) — Electrical Machine, chapter 7 - [End bar and universal measuring machines](https://www.bctengineer.com/question.md?key=semester_3%2Fmetrology%3Aend-bar-and-universal-measuring-machines) — Metrology, chapter 14