Math Detours · Grade 5 · Around the corner · 30

Instructions a robot can follow

Write exact instructions for a tiny robot. Trace a loop, fix its bugs, and prove what every repeat does.

Name ____________________Date ____________

Tonight's idea

A person can guess what you meant by “put jam on it.” A robot follows the words you gave it. Which slice is “it”? How much jam? Which side? A useful program replaces guesses with exact instructions.

A loop repeats instructions. To check a loop without tracing it for ever, look for an invariant: a fact that is true before every repeat. Check that it is true at the start, then that one repeat keeps it true.

A trace tests some steps. An invariant explains why every step works.

This is a small taste of software verification: giving instructions a precise meaning, then proving that the program does what you intended.

Watch one: add 2, five times

PROGRAM number ← 0 REPEAT 5 TIMES: number ← number + 2 completed repeats number 012345 0246810 after r repeats: number = 2 × r
The row before the first repeat matters. It is repeat 0, and the invariant already works.

At the start, \(r=0\) and the number is \(2\times0=0\). Suppose the number is \(2\times r\) before a repeat. Adding 2 makes it \(2\times r+2=2\times(r+1)\), so the rule is still true after the next repeat. After 5 repeats, the number must be \(2\times5=10\).

Your turn

  1. A sandwich robot has a plate, a closed jam jar, a knife and two slices of bread. Its program says: “Put bread on the plate. Spread jam on it. Put the other slice on top.” Find three places where the robot needs a more exact instruction. Rewrite one of them.
  2. A floor robot starts on a grid point, facing east. It repeats FORWARD 3, RIGHT four times. FORWARD 3 means move three grid spaces; RIGHT means turn one quarter-turn clockwise. Draw its route. Where does it finish, which way does it face, and how far did it travel?
  3. This program is meant to print 1, 2, 3, 4, 5. What does it actually print? Change just one symbol to fix it.
    step ← 1
    WHILE step \(\lt 5\): PRINT step, then step ← step + 1
  4. Start with \(n=1\), then repeat n ← 2 × n six times. Make a trace including repeat 0. What invariant describes \(n\) after \(r\) repeats, and what is \(n\) after repeat 6?

Stretch: will it ever stop?

Start with \(x=10\). While \(x\ne0\), replace \(x\) by \(x\div2\). An Exact robot keeps fractions. A Whole robot keeps only whole numbers and rounds down after each division. Trace both. Which robot stops, and after how many divisions?

Answers

  1. Problems include: it does not say which slice goes on the plate; the jar is still closed; “it” could name more than one object; it does not say which side of the bread gets jam or how much; “on top” does not say that the jam sides should meet. Many rewrites work. One is: “Call the slices A and B. Put slice A flat on the plate.”
  2. The route is a square with side 3. The robot returns to its starting point facing east. It travels \(4\times3=12\) grid spaces and turns through four quarter-turns, one full turn.
  3. It prints 1, 2, 3, 4. When step becomes 5, the test \(5\lt5\) is false, so the loop stops before printing 5. Change \(\lt\) to \(\le\). Then it prints 5 and stops after step becomes 6.
  4. The trace is 1, 2, 4, 8, 16, 32, 64 for repeats 0 through 6. The invariant is: after \(r\) repeats, \(n\) is 1 doubled \(r\) times, or \(n=2^r\). Therefore \(n=2^6=64\).

Stretch. Exact gives \(10,5,2.5,1.25,0.625,\ldots\). After \(r\) divisions it has \(10/2^r\), which is positive for every finite \(r\), so it never reaches 0. Whole gives 10, 5, 2, 1, 0, so it stops after 4 divisions. A program's result can depend on its number rules. Fixed-size computer number formats can also turn a very small value into 0, called underflow.

← PreviousNext: One cut, twelve copies →