Turing Machine

You probably heard about it if you're the kind of person who appreciates this, but a man named Mike Davey has built an actual Turing Machine, moving tape and all. This is amazingly cool, at least as good as the lava lamp centrifuge I posted a few weeks ago.

A Turing Machine is a theoretical model of computation, an idealized, maximally simplified computer. The Turing machine can theoretically do anything any computer can do. Specifically, you can show that there is a Turing machine that can take a description of any other Turing machine - or any computer - and emulate its operation. So any results you prove about the Turing machine is also true about any real-world computing device. Anything the Turing machine can do, a normal computer can do too. ANything shown to be impossible for a Turing machine (not just slow, but impossible), is also impossible with a real computer, no matter how big and powerful.

For instance, through the Turing machine we know that it is impossible to create a program that will take any program as input and find out whether that program will ever finish or if it will just loop forever (the Halting problem). Why is that important? It's the same thing as saying you can't make an automated test to verify that any real-world program is bug-free or that it does what it's supposed to do. Any testing or verification has to be specific to a program. That has some pretty important real-world consequences for the quality of important software systems and the cost of developing them.

A more fundamental consequence is that it sets important limits on what functions a Turing machine can actually compute. There are a classes of functions that you can express, but that you can't resolve - you can't get an answer - using a Turing machine. And as a Turing machine is exactly as powerful as any real-world computer (speed is immaterial), it means the same restrictions apply to them as well. Before you start gloating too much about the superiority of humans to computers, remember that it's quite probable that we are the same kind of computing devices and are just as unable to resolve this class of functions.

The Turing machine is an abstract tool for people working on theory of computation and algorithms. Building a real-world machine that looks and operates like Alan Turings imaginary machine is perhaps not the most useful thing in the world, but it's hugely, amazingly cool.