Notes

Chapter 12: The Principle of Computational Equivalence

Section 4: The Validity of the Principle


Constructible reals

Instead of finding successive digits using systems like Turing machines, one can imagine constructing complete real numbers using idealizations of mechanical processes. An example studied since antiquity involves finding lengths or angles using a ruler and compass (i.e. as intersections between lines and circles). However, as was shown in the 1800s, this method can yield only numbers formed by operating on rationals with combinations of Plus, Times and Sqrt. (Thus it is impossible with ruler and compass to construct Pi and "square the circle" but it is possible to construct 17-gons or other n-gons for which FunctionExpand[Sin[Pi/n]] contains only Plus, Times and Sqrt.) Linkages consisting of rods of integer lengths always trace out algebraic curves (or algebraic surfaces in 3D) and in general allow any algebraic number (as represented by Root) to be constructed. (Linkages were used by the late 1800s not only in machines such as steam engines, but also in devices for analog computation. More recently they have appeared in robotics.) Note that above degree 4, algebraic numbers cannot in general be expressed in radicals involving only Plus, Times and Power (see page 945).


From Stephen Wolfram: A New Kind of Science [citation]