Strolling through informatics #7 – Can we always find an algorithm?

previous #6 ––– next #8

by Enrico Nardelli

(versione italiana qua)

The question we left off with in the previous post (Understanding algorithms isn't hard) was whether it's always possible to find the algorithm to perform the processing we have in mind.

For this purpose, we first need to clarify that the situations to which we can apply algorithms require that it be possible to describe precisely both the set of possible input data to the algorithm itself and the set of acceptable output results, expressed as a function of the inputs. But even for problems that can be formulated in this way, we'll see below that the answer is negative. We should add that the description is sometimes done, for algorithms that never terminate because the processing they must perform should not stop, with reference to a specific time interval.

Let's now consider four problems that present different characteristics in terms of computability (the names that denote the field of informatics concerned with these aspects), which will be discussed in this and the next post.

1. A first example of a problem (called "sorting") that can be approached algorithmically takes as input a list of N integers and requires as output the list of numbers ordered by increasing value.
2. A second example of a problem (called "shortest paths") takes as input a list of N cities, for each of which a list of cities (belonging to the list itself) is specified to which they are directly connected by a road segment whose length is given. The output requires, for each pair of cities P and Q in the list, the sequence of road segments that leads from P to Q with minimum total length.
3. A third example (called "traveling salesman") has the same input as the second, but the output requires obtaining a sequence of road segments that passes through all the cities in the list exactly once and has minimum total length.
4. A fourth problem (called "halting") takes as input a specific program written in a particular programming language and any of the possible input data to the program. The required output is "TRUE" if that program processing this data stops after a finite time, "FALSE" otherwise.

We observe that the algorithm, to be such, must "work," that is, produce the correct output, for all possible inputs. This means, for the first problem, for all possible lists of N numbers; for the second and third problems, for all possible lists of N cities with all possible connections to adjacent cities; for the fourth problem, for all possible programs written in the chosen language and all their possible input data.

For the first three problems described above, solving algorithms exist, so these problems are said to be computable, while the fourth problem, the halting problem, admits no solving algorithm, and is therefore an incomputable problem. At this point someone might think, given that an algorithm must anyway be expressed in a particular programming language through a program that must be executed by a particular automaton, that it would suffice to have a more modern language or a more powerful automaton.

This is not the case. It was Alan Turing himself who demonstrated, in the 1936 scientific article that is considered the birth of informatics as an autonomous scientific discipline, that the fourth problem is not intrinsically solvable, regardless of what the programming language or automaton used might be. In other words, no algorithm exists for the halting problem.

I emphasize that this result remains true even considering "quantum" type automata (which are the theoretical model of the so-called "quantum computers" much talked about in recent years). This is an extremely important result, not only from a cultural standpoint but also on a philosophical level, because it defines very precise limits to what can be achieved through computers and, therefore, also to our possibility of "knowing" something through algorithmic procedures. This cannot but please us, given that as human beings we have at our disposal other ways of "knowing," which go beyond the absolute mechanical rationality of an automaton and which the latter do not possess.

In the next post we will deal with the time necessary for executing algorithms and how this can vary from acceptable situations to others that are completely unsustainable.

[[The posts in this series are based on the Author's book (in Italian) La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, (= The Informatics Revolution: Knowledge, Awareness and Power in the Digital Society) to which readers are referred for further reading]].

--
The original version (in italian) has been published by "Osservatorio sullo Stato digitale" (= Observatory on Digital State) of IRPA - Istituto di Ricerche sulla Pubblica Amministrazione (= Research Institute on Public Administration) on 6 November 2024.