So far in the Tech Tuesday series on the theory of computation we have learned about Finite State Machines and their limitations, as well as the more general relationship between automata and languages. As a reminder, an automaton is a model of computation and the reason to have such models is so we can apply formal reasoning to them. Today I will introduce an automaton known as a Turing machine after the amazing Alan Turing who dreamed up this model of computation in the 1930s.
The easiest way to think of a Turing machine is as a slightly modified Finite State Machine connected to a infinitely long one-dimensional read/write tape. The tape consists of discrete cells and the machine can read from a cell and write to it using symbols from an alphabet. The machine can move left or right along the tape (which is all it takes to get to any cell, even if that involves a lot of traversing of the tape).
Execution of the machine is straightforward: it starts on a specific cell on the tape and in a specific state. From there on it transitions to a new state based on (a) the current state and (b) the symbol found in the current cell. During the transition to the new state, the machine can write a new symbol into the current cell (or leave it unchanged) and move the tape either left or right. That’s it.
If all of this sounds a bit too abstract for you, check out this simulator of a Turing Machine in Javascript or for kicks look at this video where someone built a hardware Turing Machine. It is important to note here that there are a finite number of states and a finite number of symbols (in fact we could reduce those to just 0 and 1). The only thing that is infinite about the Turing machine is the potential length of the tape.
So what’s the big deal here? It turns out that to date we have not found a model of computation that is more powerful than a Turing Machine. Given the extreme simplicity of a Turing Machine this is quite a stunning outcome. We have found other formalisms, such as the lambda calculus by Alonzo Church and recursive functions by Kurt Gödel that are as powerful but not more so than the Turing Machine. This has given rise to the so-called Church-Turing thesis, which states that something is algorithmically computable if and only if it is computable by a Turing machine.
Note that this includes known approaches to Quantum Computers because while these might provide huge performance improvements they can be simulated by a classical computer (which in turn can be modeled by a Turing Machine). It is, however, not known whether there are physical processes that exist in our universe that are more powerful and hence can *not* be simulated by a Turing Machine. That also leaves open the possibility that such processes could be harnessed for what some people are calling hypercomputation.
Next Tuesday we will look at how the Turing machine can be used to think about some of the fundamental problems of computability. We will find that there are some important limitations that are highly relevant for practical computing applications.
