The beginning of modern computing

Vwe will be reporting on the paradoxical beginning of modern Computer Science. And I say paradoxical, because it came about not when one was trying to find an efficient way to do calculations, but when one was trying to show that there were uncomputable problems.

The hero of this story is a man named Alan Turing, who was already the subject of a Hollywood film, "The Imitation Game"The Game of Imitationand possesses a computer science award named after him, the Turing Award, which is awarded annually to a researcher who has excelled in the field. In 1937, he mathematically demonstrated that there are problems that cannot be computed. However, to do so, he had to define what it means to be "computable," and in the process, he created the Turing Machines. These machines are abstract mathematical concepts that formalize the notion of computation, and an important mathematical result that he discovered shows that there is a special machine, called the Universal Turing Machine, that plays a central role in the Theory of Computation. This Universal Turing Machine is the basis for the construction of computers as we know them today.

The initial article by Turing has some things that are striking and that are present in the title of the article itself, translated here in a free way:On computable numbers and an application to the decision problemSo, what do you mean by computable numbers? Do you mean that there are non-computable numbers?

Yes, and it's not that difficult to see this. But first, let's go back a little in time, because the beginnings of computation are closely linked to infinite numbers. In 1874, the German mathematician Georg Cantor published an article in which he showed that there were more than one type of infinity. In particular, he showed that the infinity of the natural numbers 0,1,2,3, … is smaller than the infinity of the real numbers. You may have already noticed this, from a simple drawing. The infinity of the real numbers corresponds to a continuous line (this set is called the Continuum), and, on this line, well spaced, we can insert the natural numbers or the integers (the size of this other infinity is called Countable). With a very innovative strategy, Cantor showed that it is not possible to align the elements of the Continuum one by one with the Countable elements, there is always some number that does not get aligned. In this way, he showed that the continuum is strictly greater than the countable numbers.

So then Turing shows that there are real numbers that are uncomputable. Uncomputable numbers are always elements of the Continuum. By his definition, a real number is computable if there exists a program or, in the original version, a Turing Machine, that prints its digits infinitely. But each program and each Turing Machine has a finite size and is stored in a file. A file is nothing more than a natural number, which can be quite large. So the maximum number of programs is a countable infinity, and there cannot be enough programs to print all real numbers. Many real numbers cannot be printed by any program, and these are the uncomputable real numbers. And we now know that most real numbers are not computable, only a small proportion of them can be printed by a program or by a Turing Machine.

There's a little gossip here. When Turing wrote his article in 1936, without his knowledge, another famous mathematician, named Alonzo Church, had already demonstrated the existence of uncomputable numbers, using very different techniques. So the editors of the journal were in doubt whether Turing's article was truly original. The article remained on a desk until someone had the idea of showing this article to Church himself, who found Turing's idea so original that he invited him to be his doctoral student in the United States. Because of this delay, the article was only published in 1937. Turing finished his doctorate in one year and was back in England when World War II broke out. That's where the story of the film begins.The Imitation Game, after Turing had already made his great contribution to the history of modern computer science.

Returning to the numbers, the first reaction of people when they learn that there are uncomputable numbers is: "Please show me an example of an uncomputable number." And I, with pleasure, respond: "I can't show you. If I show you the number, I have just computed it. And an uncomputable number cannot be computed. Obvious, right? Well, if it's not obvious, get used to the idea that you will never be able to see an uncomputable number, exactly because it is uncomputable."

But, if the number is not computable, how do we refer to it? Well, we have to use indirect ways to define the number without making any calculations. A very famous example is "the probability of a computer program stopping". This expression in quotes is the definition of the number. It is shown that this is an uncomputable number, of which we cannot know almost any property. We cannot know if this number is less than 0.5 or greater than 0.00000001. All these questions are also uncomputable questions.

And this brings us back to Alan Turing's original paper. He showed that there are uncomputable problems, i.e., problems that cannot be calculated by any Turing machine, including the famous Halting Problem (of first-order logic) that was in the title of his paper.

And this is how modern computation was born, showing that computation has limits. There are things that will never be computable, and we have to live within the limits of what can be done with a computer. Turing's Theorem does not depend on any programming language or type of computer. Therefore, uncomputable problems will remain uncomputable with any technology, even with the most modern artificial intelligence or the technologies that will be invented in more than a century.

________________
(The opinions expressed in the articles published inJornal da USPThese are entirely the responsibility of their authors and do not reflect the opinions of the publication or the institutional positions of the University of São Paulo. Access oureditorial guidelines for opinion articles here.)