2012 : WHAT IS YOUR FAVORITE DEEP, ELEGANT, OR BEAUTIFUL EXPLANATION? [1]

gloria_origgi's picture [5]
Philosopher and Researcher, Centre National de la Recherche Scientifique, Paris; Author, Reputation: What it is and Why it Matters

The Turing Machine

«There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy» says Hamlet to his friend Horatio. An elegant way to point to all the unsolvable, untreatable questions that haunt our lives… One of the most wonderful demonstrations of all times ends up with the same sad conclusion: There are mathematical problems that are simply unsolvable.

In 1936, the British mathematician Alan Turing conceived the simplest and most elegant possible computer ever: A device, as he described it, "with an infinite memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behaviour of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine".

An abstract machine, conceived by the mind of a genius, to solve an unsolvable problem, the decision problem, that is: for each logical formula in a theory, is it possible to decide in a finite number of steps, if the formula is valid in that theory? Well, Turing shows that it is not possible. The decision, or Entscheidungs problem was well-known by mathematicians: it was the number 10 of a list of unsolved problems that David Hilbert presented in 1900 to the community of mathematicians, thus setting most of the agenda for the 20th century of mathematical research.

The decision problem asks whether there is a mechanical process — that can be realizable in a finite number of steps — to decide whether a formula is valid or not, or whether a function is computable or not. Turing started asking himself: "What does a mechanical process mean?" and his answer was that a mechanical process is a process that can be realized by a machine. Obvious, isn't it?

He then designed a Turing machine for each possible formula in a first-order logic system, or, for each possible recursive function within the natural numbers, given the logical equivalence proven by Gödel between the two sets. And indeed with his simple definition, we can write down a string of 0 and 1 for each tape to describe the function, then give to the machine a list of simple instructions (move to left, move to right, stop) so that it writes down the demonstration of each function and then stops.

Turing was able to design a Universal Turing Machine, that is, a machine that can take as input any possible string of symbols that describe a function and give as output its demonstration. But, if you feed the Universal Turing Machine with a description of itself, it doesn't stop, and goes on infinitely generating 0s and 1s. That's it. The mother of all the computers, the soul of the Digital Age, was designed to show that not everything can be reduced to a Turing machine. There are more things in heaven and earth.