I’ve recently been reading Janna Levin’s latest book about Turing, Godel, and the men and women in their lives. Though it’s fiction, it paints an excellent portrait of just what geniuses these men were. Oh, and how really really weird they were too. Maybe weird is cutting them a little too much slack. Godel was an obsessive-compulsive solipsist. Turing was slightly deranged. These are not people you would want to, say, be roomies with. Nonetheless, their contributions, I’m sure you know, are historic.
So I’m a mathematician, and I don’t really know much about computing theory. I know how to use a computer, and I know basically how the thing works, but other than that I’m what the modern generation calls an “omgwtf n00b”.. or something. So, being the incredible researcher I am… I went on Wikipedia. My main questions: What is a Turing Machine? What is the Halting Problem? How does it link to mathematics?
So here goes.
What is a Turing machine?
A Turing machine is a machine (physicial or abstract) that utilizes the most basic possible computing framework. In other words, Turing machines are those which can be extended to “mimic” any computational process imaginable, ignoring things like the amount of time it might take to finish. In some ways, Turing machines are analogous to propositional logic. Propositional logic can be extended into first-order logic, which in turn can be extended into second-order logic, and so on.
But it gets more interesting. A Turing machine may also have the ability to simulate any other Turing machine. Such a Turing machine is called a Universal Turing Machine. Any machine that is, at heart, a Universal Turing Machine is called Turing complete. The basic idea here is that you don’t need separate machines for separate tasks. You can have one machine that simulates all of the tasks you would possibly want to accomplish.
For example, let’s consider a microwave, an oven, and a toaster. Each of these accomplishes its goals in different ways. A microwave heats something by speeding up its water molecules. A toaster heats something with radiation via its coils. An oven is similar to a toaster, but is closed, so that the air around whatever’s cooking also heats up. If each of these represent a Turing machine, then can a combination microwave-toaster-oven can be considered a Universal Turing Machine? Can these three separate machines even be considered Turing machines in the first place?
This metaphor is not exactly correct. First, combining three separate machines, even n separate machines, into one, does not make that one a Universal Turing Machine. Universal Turing Machines simulate other Turing machines. In other words, one process can simulate all other processes; those other processes are simply manifestations of the parent process, the UTM. Secondly, each of the three, the microwave, oven, and toaster, cannot be repurposed into one of the others, nor are they made from the same “stuff”. The definition of a Turing machine is that it can be extended or transformed to accomplish any task. Certainly, the microwave could be broken up and be made into other things. But not any old thing. It has limits.
Turing machines, of course, deal with computations, not physical interactions. The microwave et al. are not Turing machines in a physical sense because they don’t compute things, they heat them, so my little metaphor is a bit artificial. Of course if you think about it, all of those kitchen contraptions probably contain some circuitry. You could repurpose them into very simple computers. But still, they could not accomplish much without some sort of storage device. In a sense, real Turing machines are physically impossible for this very same reason, because to accomplish every imaginable task would require infinite storage. Nonetheless, Turing machines are excellent models for the way modern computers actually work.
So we’ve defined what a Turing machine is, but how does it work? What is this “basic computational framework”? Think about what you want in a computer program. You want to be able to interact with the program, both input and output. So a Turing machine should have a means of inputting information, and a means of displaying information.
You also want the program to actually accomplish something. So a Turing machine must be able to alter inputted data. However, something is missing. What happens to data once you input it? If you have a disconnected keyboard, and you press a key, nothing happens. You’ve inputted something, but that input hasn’t gone anywhere. Clearly you need somewhere to store that information. However, even then, you don’t have a very useful program. How does it know what the stuff you input means? It needs to be able to read the input you give it.
One final question: how does it know what to do with the data? It needs to alter it, but in what way? The answer is this: it needs an alphabet. In other words, it needs a predefined dictionary of terms which it can manipulate. It also needs a rule set for how to manipulate those terms, operators if you will. In other words, given two data symbols and (also called “operands”) and a symbol (the operator), the machine needs to be able to compute which is some other symbol in its alphabet, .
And that’s basically it. Technically, a Turing machine needs only to be able to read and alter (i.e. needs an alphabet and operators), and other devices can facilitate displaying and inputting. For our purposes, the extended definition above serves better. A machine you can’t interact with isn’t very useful.
In practice, terms like “Turing complete” refer to programming languages, the implied assumption being that if the computer had infinite storage, a Turing complete programming language would represent an abstracted UTM.
Next time . . . : the Halting Problem