When it comes to explaining what is the Turing Machine, I feel scientific dissemination isn't always accessible to people without a specialized background. Before I studied it in university, I never really understood what it was, only that it had to do with the origins of computers, and it was not a "real" machine.
For that reason, I want to summarize the concepts behind the Turing Machine and explain how it defined what we consider computation in the way I would have liked them to be explained to me.
What is Computation?
When we talk about computation, we usually think about computers: digital information processing. Nonetheless, the actual meaning of computation is not limited to digital processing nor computers. We could say that
Computation is every process for which a given input is transformed into a determined output, or result.
Give me some examples
Some general processes of computation:
A tree computes water and carbon dioxide into chlorophyll and oxygen.
A candle computes string and wax into light and heat.
Our digestive system computes food into muscle, fat, energy and... wastes.
A pocket calculator computes two numbers and an operator pressed on the keyboard into another number.
What is a Computational Model?
To keep it simple, let us say that:
A computational model is the definition of the rules that must be followed by the computations performed by a system.
For most of the previous examples, you can't really talk about a computational model because the systems are "natural" and just follow the laws of physics and chemistry. In the case of the pocket calculator, the computational model is too complex to explain here.
Some minimalist examples
The most simple computational model could be imagined as a look-up table, where you look for the input you receive and produce the result written in the table.
A table to invert a binary string:
For the input
10100 the output is
A table to convert lower-case to upper-case:
For the input
i love you the output is
I LOVE YOU.
More complex minimalist examples
Now, computational models are usually more complex than direct equivalence tables. They usually have states, which are taken into account as part of the computation.
These states represent different parts of the process of computation and determine the output for an input.
If our model was a cooking pot full of water, we could define it like this:
|PotIsCold||raw rice||wet raw rice||PotIsCold|
|PotIsHot||raw rice||cooked rice||PotIsHot|
You see that now we don't have just an entry for each input, but for the combinations of each input in each possible state of the model.
For example, if we wanted to define a model that inverts one digit of every two alternately in a binary string, we could have:
For the input
111111 the output would be
If you have understood it to this point, congratulations! You have understood Finite State Automata!
The Turing Machine as a Computation Model
Now that we understand what computation and computation models are, we can talk about the Turing Machine. The name is misleading because it is not one machine, but a family of theoretical machines.
A Turing Machine is imagined as a machine that reads from and writes to one tape of infinite size, using a head. The computational model also has a set of possible states, which determine what the machine does when it reads a symbol from the tape: write another symbol o move the tape.
Here you have a little demonstration of a Turing Machine online simulator that converts a decimal number to its binary representation.
Try it yourself here (Examples > Binary to decimal > Compile).
A Universal Computation Model
It's been mathematically proven that any computation process can be expressed as a Turing Machine. So, the following question is... what if we use the definition of a Turing Machine as the input of another Turing Machine?
The answer is the Universal Turing Machine, which is defined in such a way that can simulate the behavior of any Turing Machine, given its definition. This is what makes it a Universal Computation Model.
Not only can it express any computing process, but a single model can simulate all others: it is a general purpose computer.
So this is why the Turing Machine was the precursor of the computers we know today. The concept of the Universal Machine behind it is exactly the same as that on which digital computers operate.
A digital computer is a machine (processor, memory, etc) that can execute any computation given its definition (program). This is the reason why computers have meant a bigger revolution than any other kind of technology because they don't have any specific purpose; they are able to automate everything that can be defined by an algorithm.
- Are digital computers really equivalent to the theoretical Turing Machine? No. The memory of the Turing Machine (the tape) is infinite and computers have limited memory. However, with the huge amounts of memory that modern disks can handle and the possibility to distribute it over the Internet, that limitation is hardly a problem.
As a Turing Machine can express and simulate any possible computation, studying its properties, limits and possibilities allows us to better understand which kinds of problems are solvable by computers and which are not. The questions raised by this model are still being studied and many are still unanswered.
Turing invented his machine in 1936, and since then we haven't come up with a more powerful computation model. So as surprising as it may sound, even the latest artificial intelligence innovation could be performed by this simple model created almost a century ago.