One tape to compute anything

Computing · Algorithms & Data Structures · ages 17-18

Name ______________________ Date ____________

What happens in one Turing machine step?
- It deletes its own states
- It reads, writes, moves, and changes state
- It unplugs the tape
What are the parts of a Turing machine?
- Fixed states plus an unlimited tape
- A screen plus a keyboard
- A battery plus a charger
A Turing machine can compute anything any computer can.
Circle one: True False
What does the tape add that fixed states alone lack?
- Memory without bound
- Brighter colours for the states
- Louder clicking sounds
Run the lesson machine on the tape 1 0 1. What does the tape read when it halts?
- 1 0 1, unchanged forever
- 1 1 1, all ones
- 0 0 0, all zeroes
A universal machine reads the description of another machine and imitates it.
Circle one: True False
Mara says her new laptop computes things no Turing machine can. What is wrong with her claim?
- Laptops are slower than chalk
- Any computer is matched by some Turing machine
- New laptops lack tapes
Why is a laptop best described as a universal machine in silicon?
- It is rectangular and grey
- It never runs out of battery
- One machine runs any program you load

Answer key

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

It reads, writes, moves, and changes state · Read, write, move, and change state: that is the full step.
Fixed states plus an unlimited tape · States steer, and the tape remembers without bound.
True · States plus an endless tape reach every computation.
Memory without bound · States are fixed and finite, while the tape stretches as far as needed.
0 0 0, all zeroes · The sweep turns every 1 into 0, then halts at the blank.
True · Description plus input in, imitation out.
Any computer is matched by some Turing machine · The Turing machine sits at the top of the ladder, covering all computers.
One machine runs any program you load · Stored programs turn one device into every device.