Tag: Open Source Software

Own it in Paper!

Models of Computation: The Church-Turing Thesis and Geometric Construction

The Church-Turing Thesis posits that the equivalence class that includes the Turing machine, and is also the basis for modern digital computing, is the most powerful model of computation. And it hasn't been proven, but when people have checked out other models of computation, every one has turned out to either be equivalent to the Turing machine, or become lesser.

Quite probably it may be impossible to construct some useful computer by this model; quite possibly for that matter its greatest usefulness may come through simulations by digital computer, in which case its simulations will automatically not exceed Turing machines or digital computer by its power. However, even if is a failure at scaling some of the highest peaks, it seems an interesting and provoking possibility to explore.

Standard Euclidean geometric construction is a model of computation. It is not usually presented as such, but you start with a diagram and all that may be inferred from it, and you have two tools, a compass and straightedge, as well as a pen or other implement to draw with. And the solution to a construction is to come back with an algorithm that will go through computational steps that start with its initial state represented in a diagram, and use your three tools to create the desired end result.

Both models figure into the model of computation discussed here, but the model of computation is different.

The model of computation described here is like a blacksmith's forge. I have read that one of the first things a blacksmith makes, is a pair of real tongs. And a blacksmith is not just turning out nails and other things for other people, but tools used in the forge. The core insight here is that a blacksmith can create tools, much as a computer programmer may make customized tools for their own work. This is at its core a geometric model of computation, with a more obvious debt to geometry, although the tools should be sufficient to implement a Turing machine. One person made the interesting suggestion that it is applying recursion to geometric construction.

The blacksmith's forge

The main tools the blacksmith's forge works with are as follows; the first three are taken from geometric computation:

1. A compass, that can be used to draw circles.
2. A straightedge.
3. A marking implement.
4. A jigsaw. The geometric plane is conceived not to be one point thin, but a uniform distance thick. When the blacksmith's forge has constructed the closed outline of the shape, the shape can be cut out.
5. Pins, equal in length to two or more (whole) times the thickness of the plane. If one pin goes between two shapes one on top of the other, and the shapes are not otherwise constrained, they will be able to pivot around the pin with respect to each other. If two or more pins go through, then the two positions will be rigid in how they are joined.
6. Pieces cut out with the jigsaw, possibly joined by pins.

Idealized Physics in the Blacksmith's Forge

The blacksmith's forge has an idealized physics. The pin and jigsaw are parts of this idealized physics, but another part of the physics is that pieces do not tip over: any number of stackings that would immediately fall over in the real world are assumed to simply stand upright, the pieces resting on top of any other piece immediately beneath them for some positive areas. There is friction, and pieces pushed to where one entity crosses another, for instance, will immediately stop moving if they are no longer being pushed. Items touching each other can be pushed past each other, but only so far as they are pushed. This does not exhaust the physics, but if you think of the physics of ordinary geometric construction, you should be close to the mark.

Three Classic Problems

Trisecting an Angle

Consider the following diagram:

That is half of it. Take another one, rotate it by one notch and pin it to the bottom one, and you have forced equality for the angles between adjacent arms:

Take this constructed device, rotate it so point A is at an angle's vertex, B is in the angle's clockwise side, and expand or contract the accordion-like device so that C is at the angle's other side. Angle DAB is now one-third of the (trisected) original angle.

Doubling the Cube

Consider the following modification of the previous diagram:

Take a circle, and draw a concentric circle at twice the radius. Then place the constructive device so point A is at the center, and expand out or collapse in so that B is on the initial circle. Then collapse or expand the device so that it is on the the new "double radius" circle. Point E will have a distance to the center equal to the original radius times the cube root of two.

Squaring the Circle

Cut out two circles, and a tall, thin rectangle. Put the circles snugly and squarely so that the line between them and the rectangles is perpendicular to the rectangles' long dimension. Put pegs through the circles' centers through the perpendicular rectangle, and mark (A) both the first circle and the rectangle where they meet. While holding the first circle squarely, push on the outer circle until it wraps the long rectangle around the first circle, and mark on the tall rectangle where it touched the circle's mark.

You now have a distance marked out on the tall rectangle that is 2π times the radius of your circle. Getting the square root of π is not terribly difficult; you can draw two subsegments of a line segment, one equal to the original circle's diameter in length and one equal to circle's circumference, and then draw a long line segment perpendicular to the first segment starting where the two meet. Take one of the corner-like squares above, place it so that it touches both endpoints of the line segment, and while continuing to hold it tight to the ends of the segment, move it so its inner corner lies on the perpendicular line segment. The distance from that point along the line segment to the center is equal to the square root of π times the length of the original circle's diameter:

(And though this would be laborious, I see no reason why such calculations could not emulate a Turing Machine.)

Foul!
You're Using Extra Privilege!

I am indeed using extra privilege, but may I point something out?

There is a bit of a historical difference between now and ancient Greece. We now have a number of branches of mathematics, and though there may be likes and dislikes, it is something of an outsider's question to ask, "Which is right: real analysis or modern algebra?" There is a general sense that as with board games, if you want to play chess you play by the rules of chess and if you want to play go you play by the rules of go.

The three questions neatly and easily answered are the standard three famous problems which it was subsequently proven to be impossible to construct with Euclidean geometry. And these were not simply mathematical chess problems; I don't know the stories for all of them, but legend has it that there was a plague killing many people and an oracle stated that the plague would be stopped if a cubic altar were built that was twice the volume of an original cubic altar. This was not one where people only used Euclidean construction because they decided they could only play by the rules of Euclidean geometry. This was a "by any means necessary" matter, and it should be understood as much. The attitude of "This is the set of rules for this particular game" is anachronous; people would be very glad to have an extension to Euclidean construction that would allow solution of at least one of these problems.

And it is not clear to me whether this is any sense of useful model of computation. (I personally think, out of my second master's thesis, that the human brain can do things no Turing-approximant style of computers can do. Some people have said, "A year spent in artificial vision is enough to make one believe in God," and there are some basic things, like making sense of an I can read book, that most humans do well but are so far insurmountable to computers; one writer wrote of an embodied AI robot "Cog," "The weakness of Cog at present seems to be that it cannot actually do very much. Even its insect-like computer forebears do not seem to have had the intelligence of insects, and Cog is clearly nowhere near having human intelligence."

But I think this model of computation is interesting, whether or not it proves useful.