Wednesday, June 6, 2007

More Powerful Than a Turing Machine

Turing Machines (along with Lambda Calculus and other formalisms) are the standard upon which computability is defined. Anything effectively computable can be computed by a Turing Machine (TM).

From one point of view, the computer I am using right now is less powerful than a TM since my computer does not have infinite memory. However, it has enough memory for any practical purpose so for the most part this is not a concern.

From a more interesting perspective, my computer is much more powerful than a TM. By more powerful I do not mean it is faster (by virtue of using electronics instead of paper tape). Rather, I mean it can "compute" things no mere TM can compute. What things ? I am glad you asked!

There is nothing in the formal specification of a TM (or Lambda Calculus) that would lead you to believe a TM can tell you the time of day or keep time if you primed it with the current time of day on its input tape. My computer has no problem with this because it is equipped with a real time hardware clock. The specifications that went into the construction of this clock rely on some sort of fixed frequency reference (like a quartz crystal). Clearly there is no such fixed frequency specification in the definition of a TM.

I could hook a GPS unit to my laptop as many people have. If I did my laptop would be able to "compute" where it was at any time. Togetehr with its real time clock my laptop would be able to orient itself in both time and space. No mere TM could do that.

If I purchased a true hardware random number generator like this one I could also add even more power to my computer because the best a TM could do is implement a pseudo random number generator. Hence my computer could presumably perform much better Monte Carlo simulations.

By further adding all sorts of other devices like cameras, odor detectors, robotic arms, gyroscopes and the like my computer would be able to do so much more than a TM.

There is nothing really deep here. Turing was only interested in modeling computation so it would have been silly if he accounted for all the peripherals one might attach to a TM or computer in his mathematical model.

However, when you are reading some critique of AI that tries to set limits on what a computer can or can't do based on either Turings or Godel's findings it helps to remember that computers can be augmented. Clearly humans have some built in capacity to keep time (not as well as a clock but not as bad as a TM). Humans have a capacity to orient themselves in space. It is also likely that our brains generate real randomness. We should begin to think of how these extra-TM capabilities are harnessed to make us intelligent. We can then teach our computers to follow suit.

No comments: