Are we aware of using one every day?
Every computer we deal with on a daily basis is essentially a Turing machine
CAPTCHAs
Who is not persecuted by CAPTCHA when should he connect to some vaguely sensitive website?
And who doesn't remember Deckard-Harrison Ford in Blade Runner do those weird interrogations to spot the androids?
Well, CAPTCHA stands for “Completely Autometed public Turing test to tell Computers and Humans Apart, i.e. Turing test to distinguish computers from humans.
And even Deckard's interrogations with those seemingly abstruse questions have the same purpose of understand if the questioned is a human or a machine
THE TURING TEST
In both cases these are specific versions of the famous Turing test invented in 1950 and exhibited in one of the most cited essays in the history of information technology, Computing Machinery and Intelligence, appeared in the magazine All.
The basic thesis put forward in that article is that a machine can be said to be thinking only if an observer by asking questions cannot distinguish it from a human.
The test is still valid today, in the sense that no machine has passed it -even if the questions are simple- because of the Moravec paradox, according to which machines can do things that are difficult for us relatively well, while they cannot do things that are very easy (always for us).
For example and simplifying, if a CAPTCHA asks to identify poorly written letters, the task is (relatively) simple for us while it is very complicated for a program.
ALAN MATHISON TURING (1912-1954) AND MODERN COMPUTER SCIENCE
By the time he writes this article on the basis of artificial intelligence, Turing is actually already a famous mathematician, logician and cryptographer.
In fact it is from 1936 his studio On Computable Numbers, with an Application to the Entscheidungsproblem.
In this paper Turing lays the foundations of modern computing inventing the Turing machines in order to provide an answer to one of the problems posed by the great mathematician Hilbert.
david hilbert argued that mathematics was a formal system, that is, an algorithmic system based on self-evident logical axioms from which it is possible to deduce automatically and without resorting to phantom entities such as intuition, all theorems and true statements within that system. Such a formal system must have had three characteristics. First of all it had to be coherent, that is, not to generate contradictions between its statements. Therefore to be complete, that is to allow to derive all the true sentences starting from the axioms. And finally to be decidable, that is to have procedures that allow you to decide the truth of each sentence.
in 1930 Kurt Godel with his two incompleteness theorems he had already torn apart the idea that a formal system of this type is complete and coherent, in the sense that if it is coherent it is not complete and vice versa if it is complete it is not coherent.
THE TURING MACHINES
Turing is also concerned with refuting decidability.
To do this he invents the Turing machine, the real one prototype of modern computers and computability model.
Turing machines consist of a tape where gods are written 0 and to the 1, and a "head" that can move along the tape and read, write or erase the symbols it finds according to the instructions that the "head" contains (its internal state).
Each Turing machine is programmed to solve a task (such as multiplying or adding and so on), but you can simulate various Turing machines with a single machine by entering the instructions of the other machines in the form of programs (of 0 di 1, ultimately).
It is the concept behind programmable or general purpose computers, of which Turing is therefore the forerunner and the inventor at a theoretical level: every computer we deal with on a daily basis is essentially a Turing machine..
THE THEME OF DECIDIBILITY
It is important to underline that the Turing machine is a theoretical model of computability still valid today, indeed of the most powerful computability model, able to compute any problem.
Any? Not exactly.
And here we return to the decidability theme proposed by Hilbert.
Turing proceeds as follows.
Let us suppose that there exists a Turing machine (therefore a formal computability procedure, a program) capable of deciding the truth of any mathematical statement, that is, of saying if there is a program that can decide whether a problem can be solved in a finite number of step or the program runs indefinitely (for example able to tell if Goldbach's conjecture, according to which every even number greater than 2 is the sum of two prime numbers, is true).
We call this program Hal.
Now let's imagine another program we call C1P8, which just does the exact opposite of what Hal does.
If we impute a program in Hal, Hal can tell us if that program stops because it achieves a result or runs forever.
But now let's imagine we input C1P8 in Hal. If C1P8 turns forever Hal will tell us that C1P8 turns forever and therefore C1P8 will stop, while if C1P8 stops Hal will tell us that C1P8 stops and therefore C1P8 will turn forever: in short, if C1P8 turns forever then it stops and vice versa if it stops then it turns forever.
This refutes the possibility of having a formal logical system that contains an automatic procedure for proving all the true statements of the system itself, without running into contradictions like that of Hal and C1P8.
The third principle of Hilbert, the computability of all statements falls, just as the principle of completeness and coherence had fallen by the hand of Goedel.
It should be noted that at the heart of Goedel's and Turing's tests there is always the impossibility of a system to speak about itself without incurring insurmountable paradoxes.
The result?
In mathematics as a formal system there are statements that are undecidable following the rules of the system itself, and there are problems that no computer can solve.
WE THANK PAOLO RICCARDO FELICIOLI FOR THE CONTRIBUTION