Thread by @JuanpaMF

Alan Turing is surely one of the brightest minds of the past century. His main discovery, Turing Machines, is too often linked to modern computers and Enigma. This description misses the depth of his research and genius. Let's talk about a quest for truth, his quest. #Thread

In 1936, when he was 24 years old (!!), Turing wrote the foundational scientific article "On computable numbers, with an application to the Entscheidungsproblem" . The results in this paper gave a massive blow to Mathematical Logic as a discipline. Wait...Logic and not Computing?

At the time computers don't exist, nor their theory, computer science. Yet though, Turing is already planting the seeds for what will become computer science.
What is his motivation? The Entscheidungsproblem. No worries I also don't know how to pronounce that.

The decision problem is relevant for many reasons, but a very straightforward one is because the problem was formulated by the boss himself: David Hilbert. If you don't know him let me metaphorically describe him as "one of the last Mozart's of science". Check his wikipage plz.

The Entscheidungsproblem translates to "the decision problem" in english. This problem was one of the greatest challenges for mathematicians of the first half of the 20th century.

David Hilbert announced at the turn of the XIX century, 23 problems that he considered were the most important for the field of mathematics to solve. Among these problems 3 are of a special kind: they have not only scientific value, but also major philosophical implications.

The 3 problems concern Logic. Remember we said Turing's paper, and thus Turing Machines, deal with Logic? Let's see the formulation of these problems (don't worry too much about the precise meaning, I will dwelve into details):

- Show that Arithmetic is consistent (Hilbert's 2nd problem)
- Prove that there is no infinity between the natural numbers and the real numbers (Hilbert's 1st problem)
- Find an effective procedure that decides if a formula is true or false (Hilbert's 10th problem)

The latter is the Entscheidungsproblem! (10th). You might say: I don't see anything philosophical in these questions. Well, you have to consider how they were born: a few troublemakers had shown paradoxes that shook mathematician's blind faith to the bone.

Mathematics is one of the purest forms of research of universal truths. Would you ever accept a theorem that is contradictory? Of course not. This is pretty different from our daily life where we have to live with opposed realities.

The topic of "the crisis of mathematics" deserves many threads by itself, so just to give you context/spoilers let me tell you that many examples, like the one in the image below, arose in beautiful theories such as Cantor's -naive- set theory.

So with the existence of paradoxes, mathematicians had to worry about giving solid foundations to their work. They refined the definition of their most basic working tools: the theories, such as arithmetics (see the link with the 2nd problem!).

OK, so now that they had new theories, were they so sure that paradoxes wouldn't arise again? This is the 2nd problem formulated by hilbert: show that arithmetic is consistent, i.e that there is no contradiction that you can conclude using arithmetic theory and deduction.

Hilbert's first problem also comes from a similar background. At the time of paradoxes, also some pretty weird objects that defied all intuition arose from the study of infinity. Did you know many, many different infinities exist? Infinitely many actually.

The study of infinity, also called theory of cardinal numbers, came from Cantor -again- in the late 1800s. The mathematical beasts that were born from this (see @science4all's bit.ly/2On3mvL) motivated a better understanding of the structure of infinity.

The 1st problem, called the continuum hypothesis, is the first brick to this structure.

And now comes the third one in my list, the decision problem!

Hilbert is a firm optimist about the power of mathematics. Opposing other darker philosophic views, he stands against "ignorabimus", the belief that there are things in science that we will never understand. His program's maxim is "We must know - We will know".

Hilbert is also a formalist, which means he doesn't give a transcendental meaning to mathematical objects, and he sees mathematics as a "game of syntax with symbols".

Every problem should be solvable, no contradictions should arise, the game in some way has to find a finite way to confirm or infirm if a statement is true.

This is the idea of the decision problem. If mathematics is a game of syntaxis (a "mechanical" game), an algorithm -effective procedure in the definition tweet - must find a way to tell if a mathematical statement is true or false.

So that was the context of the time of Turing's discovery: a time when mathematics itself had to justify or prove that it was just as perfect as we all had imagined it to be.
And thus a young Austrian came and dropped the bomb...

Kurt Godel demonstrates in 1931 that:

1) There exist a mathematical statement that can not be proved, nor disproved. Its truthfulness is unachievable to us.

2) A theory that contains the natural numbers and is consistent can not prove its own consistency.

Hilbert's program over logic is completely denied by Godel. Arithmetics can't prove its consistency, ciao Hilbert's 2nd problem. Just a few years later (1940) Godel disproves also the 1st problem. Godel's theorem are a cold shower for the optimists.

This opens the way and hints mathematicians that they might also disprove the decision problem. And a very freshly graduated Alan Turing (22 years old) is on the starting blocks to win the race.

This is the first part of a very long thread on the deep meaning of Turing's Machines. I will continue on the following thread with a deep dive into Godel's theorem's, and then continue with the genesis of Turing's 1936 paper. Keep you posted!

@threadreaderapp unroll