Horseshoe map

(1)     ,

(2)     ,

This map has a fractal attractor.

Stephen Smale's work

You could make a backyard horseshoe generator using a few mirrors and two pieces of convex glass. So it is a physically feasible map. What makes this map interesting is that you could use it to generate a backyard universal Turing Machine. The chaotic behavior of this map is closely related to Alan Turing`s Halting Problem theorem, and hence with Kurt Gödel`s celebrated undecidability theorems. A Universal Turing Machine can be written using just a 22 states expressed in the action table. In each state, the machine can either:

Move left

Move right

Write 0

Write 1

Conditionally move to another state.

Now the tape (which is the machines input) is just a line of binary digits. To each integer number corresponds a binary digit. The zero place corresponding to the cell being currently read. The digits to the right of the head (including the cell being currently read) can be thought of as the binary representation of a real number belonging to [0,1]. Let us denote this number by x. The digits to the right (excluding the cell being currently read) would similarly represent y. Notice that (x,y) is a point on the square [0,1]×[0,1]. Now, the writing of a 0 or a 1 is represented by moving the point (x,y) respectively either to the left or to the right half of the square [0,1]². Moving the entire tape one step to the left is represented by (x,y) → H(x,y). Moving to the right is just doing the opposite map. Conditionally moving to another place in the action table can be thought of as moving to another block on the square. Hence, essentailly, the code for a Universal Turing Machine is just a piecewise linear map on [0,1]². So a single step made by the turing machine is the action UTM: [0,1]² → [0,1]², taking a point on the rectangle to another point on the rectangle. The machine halts for a given input if the iterations of UTM stablize.

Mark is that piecewise linear maps on [0,1]², can be achieved in your backyard using mirrors. With just couple of hundreds of mirrors, one can build a Universal Turing Machine at home. Take a large rectangle. Every point on the rectangle is a point on [0,1]² and represents a given input for your Universal Turing Machine. Surround the rectangle with mirrors to represent the machine code, so if you use a laser pointer to light a specific spot (x,y) on the square [0,1]², the mirrors will make a second dot appear at the point UTM(x,y), and then a third one at UTM(UTM(x,y)), etc.. Mapping [0,1]² for points stable under the action of UTM, and analyzing which dots of light yeild an eventually stable optical dynamics, is equivalent to solving the halting problem for Turing machines.

But the halting problem is undecidable. So the map UTM: [0,1]² → [0,1]² must be chaotic, with a fractal attractor. Note that the chaotic nature of our UTM map can only emerge from the chaotic nature of the horseshoe map embedded within UTM.

Referenced By