next up previous
Next: Making experiments Up: ROOFS AND BOXES Previous: Introduction

The Roofs and Boxes example


Consider the problem of extrapolating a sequence formed in the following way.

A billiard ball rolls frictionlessly in a rectangular arena and is frictionlessly reflected when it hits the wall with angle of reflection equal to angle of incidence. Inside the arena there are also some rectangular boxes that reflect the ball when it hits their sides. There are also some rectangular roofs that have no effect on the ball but hide it from observation.

A sequence of zeroes and ones is generated by a mechanism that observes the arena from above once per second (or nanosecond if you are impatient). If the ball is under a roof, it is invisible and a zero is generated. Otherwise a one is generated.

Now consider extrapolating this sequence from an initial segment not knowing about the roofs and boxes. None of the techniques of sequence extrapolation studied by the above-mentioned authors is applicable.

If you know that the sequence is generated by roofs and boxes you can try to fit models of the locations of the roofs and boxes. With enough data and computation, you will succeed.

If you don't have the idea of roofs and boxes, you will have to invent it. Donald Michie opined that a good cryptanalyst might come up with the idea. Looking for and analyzing repeated subsequences might help.

John McCarthy
Wed Sep 9 13:00:51 PDT 1998