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.

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

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

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

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

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.

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.

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.