Computers are everywhere today: in the office, on our smartphones, or even in cars. They work using increasingly powerful algorithms that can perform a huge variety of tasks, from adding two numbers to finding the best route to an unknown destination or automatically detecting fraudulent financial transactions. The ubiquity and potential of computers are so great that it is easy to believe that, sooner or later, they could solve any problem. However, thanks to the so-called theory of computation, we know that computers – and algorithms – have fundamental limits. The British mathematician Alan Turing (1912-1954) was one of the great promoters of the field, to the point of being considered by many the father of modern computing.
The use of algorithms dates back to the beginning of our civilization. Algorithms are, in their simplest form, a way of solving a given problem by following, step by step, a finite sequence of instructions. These instructions use a finite number of symbols and are executed, in order to obtain the desired result, in a “mechanical” way, without depending on any special form of intelligence – for example, the use of mathematical “intuition” is not required. or other type-.
A simple algorithm is, for example, the one we use to multiply – by hand – two numbers, as we are taught in school, to obtain their product. Other examples of algorithms are the so-called Euclid’s algorithm, to obtain the greatest common divisor of two numbers, or the gauss method, to solve a system of linear equations. In essence, we can see algorithms as automatic procedures that offer solutions to mathematical problems.
A few years before the birth of digital computers, mathematicians and logicians wondered what kind of problems are computable, that is, they can be solved using algorithms. This question became the initial engine of the so-called theory of computation
For centuries, these algorithms had to be done by hand, in a slow and tedious process, which, in practice, limited their use. However, with the appearance of computing devices that automated their implementation, the applications of the algorithms began to grow rapidly, mainly to perform calculations – more or less complicated -. A few years before the birth of digital computers, mathematicians and logicians asked themselves the following question: what kinds of problems are computable, that is, that can be solved by algorithms? This question became the initial engine of the call computation theory.
While it is (relatively) easy to verify that a given problem is computable – it is only necessary to prove that a certain algorithm solves it -, to show that, given a problem, there is no algorithm that can solve it, is a much more delicate matter. . Even if we can’t find an algorithm to solve the problem, how can we rule out that we simply haven’t found the right algorithm yet?
Part of the difficulty of this question was due to the fact that, until recently, there was no precise notion of what an algorithm is. In this fundamental task, the work of Alan Turing is remarkable, who, by the way, appears in the new £ 50 note and also lends his name to new student exchange program, which will replace the Erasmus program in the UK.
During the 1930s, Turing, along with other mathematicians such as Alonzo Church, proposed precise mathematical definitions of computability.
During the 1930s, Turing, along with other mathematicians such as Alonzo Church, proposed precise mathematical definitions about computability. Specifically, he defined what it means that the value of a function can be calculated using an algorithm – or, using its terms, that a function be computable about natural numbers–.
This resulted in the call Church-Turing thesis, which establishes that any function on natural numbers is computable, with the aforementioned notion of algorithm, if it can be calculated by a turing machine. The Turing machine is a computer model introduced by the mathematician, which can be seen simply as a computer program.
Turing also showed that there are non-computable problems, such as the so-called stop problem. This problem seeks to determine whether, given some Turing machine and input data for it, the machine will stop or, conversely, continue in an infinite loop. If we think of our smartphones, the problem of stopping would consist of knowing if, when using an application, it will “lock” –that is, it will remain forever in a loop–, or if it will stop and provide a response –although be it after a long time.
We currently know that there are many other non-computable problems -For example, the famous Hilbert’s list problem 10-. Thanks to this, we can guarantee, for example, that there are no algorithms capable of confirming that computer programs are free of errors. This means that, although we have techniques to improve the quality of the software, we will probably have to continue to tolerate that it contains errors – hopefully, minor ones.
Beyond the problem of computability, in practice algorithms capable of providing answers are sought, in a period of time reasonable – since, if we have to wait ten million years for an answer, that software would not be useful. This question is also studied in the context of the theory of computation and, in fact, has given rise to very interesting questions such as the problem P vs NP, whose resolution is awarded a million dollars, and which will be the subject of another upcoming article.
Daniel Graça is a professor at the University of the Algarve and a researcher at the Institute of Telecommunications (Portugal)
Timon G-Longoria Agate is coordinator of the Mathematical Culture Unit of the ICMAT and editor and coordinator of this section
Coffee and theorems is a section dedicated to mathematics and the environment in which it is created, coordinated by the Institute of Mathematical Sciences (ICMAT), in which researchers and members of the center describe the latest advances in this discipline, share meeting points between the mathematics and other social and cultural expressions and remember those who marked its development and knew how to transform coffee into theorems. The name evokes the definition of the Hungarian mathematician Alfred Rényi: “A mathematician is a machine that transforms coffee into theorems.”