Turing Machines and the Universal Machine · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.
En anglais

Tracing a Turing machine

Computing · Algorithms & Data Structures · ages 17-18
Name ______________________   Date ____________

  1. In state A, a rule for reading 1 says: write 0, move right, stay in A. What happens to the state after this step?

    • It becomes the tape symbol 0.
    • It stays A as the head moves.
    • It halts before the head moves.

  2. Which description gives the main parts of a Turing machine?

    • Finite states, rules, a head and unbounded tape
    • Finite states, rules and a fixed read-only tape
    • Unbounded states, a head and a read-only input

  3. Every Turing machine, whatever its transition rules, can run every algorithm.

    Circle one:   True   False

  4. What does a Turing machine's tape provide beyond the memory of a finite state machine?

    • Read-write memory with no fixed size limit
    • A fixed number of extra states for each input
    • A promise that every run finishes after one pass

  5. Start in A on the first cell of 1 1 0 1; all other cells are blank. In A on 0 or 1, write 0, move right and stay in A. On blank, halt without writing or moving. What do the four original cells read at the halt?

    • 1 1 0 1
    • 0 0 0 1
    • 0 0 0 0

  6. A universal Turing machine can take an encoded machine description and an input for that machine, then simulate the run even if it never halts.

    Circle one:   True   False

  7. Mara says a faster laptop can decide an undecidable yes/no problem correctly on every input. Which reply fits the lesson?

    • Extra speed guarantees that every possible program eventually halts.
    • Speed changes runtime, not which problems algorithms can decide.
    • A physical laptop's finite memory can exceed an unbounded tape.

  8. Which statement accurately relates a laptop to the idea of a universal Turing machine?

    • Its finite memory lets it run every possible computation.
    • It needs different physical hardware for each loaded task.
    • Stored instructions change its tasks, within finite resources.
LightMySky · lightmysky.comW1-mt_vS_QC1tCSM-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Tracing a Turing machine W1-mt_vS_QC1tCSM-s1

  1. It stays A as the head moves. · The rule writes 0 and moves the head right, but its next state is still A.
  2. Finite states, rules, a head and unbounded tape · The control has finite states and transition rules. A movable head reads and writes a tape with no fixed size limit.
  3. False · A particular machine's behaviour depends on its rules. An erasing machine is a Turing machine but is not a universal simulator.
  4. Read-write memory with no fixed size limit · The machine can use more tape cells as a run proceeds. Its finite state set does not grow, and halting is not guaranteed.
  5. 0 0 0 0 · The head passes all four original cells, writing 0 in each. It then halts on the following blank.
  6. True · Universal simulation follows the described computation. It does not promise that the computation will finish.
  7. Speed changes runtime, not which problems algorithms can decide. · Undecidability means no algorithm finishes with the correct answer on every input. Increasing hardware speed does not create such an algorithm.
  8. Stored instructions change its tasks, within finite resources. · A laptop reuses its hardware for supported programs, but has finite memory. It illustrates stored-program flexibility, not an actually unbounded tape.
Worksheet · LightMySky