Strolling through informatics #6 – Understanding algorithms isn't hard

previous #5 ––– next #7

by Enrico Nardelli

(versione italiana qua)

Many people use the word algorithm, but the meaning of this concept isn't always clear. To begin with, let's say that the term algorithm dates back to medieval Latin, when, according to the online Treccani dictionary, "it indicated calculation procedures based on the use of Arabic numerals." As I think many people now know, the word derives from the epithet al-Khuwārizmī of the 9th-century Arab mathematician Muḥammad ibn Mūsa, who was a native of Khwarizm, a region in Central Asia. In informatics, this term indicates an abstract version—that is, independent of any specific real programming language—of the desired computation. An algorithm is therefore a solution method that transcends (i.e., abstracts from) a specific physical form of expression. This abstraction is fundamental from a scientific perspective because it provides generality to the way of describing various computations.

On the other hand, an algorithm can only be effectively executed if we specify what automaton (also called executor or agent) must implement it. This specification wasn't relevant before the birth of informatics, when only mathematicians executed algorithms—that is, solution procedures for problems. The cultural roots of informatics lie in the effort that mathematicians made in the early decades of the 20th century to automate theorem proving. It was from this attempt (frustrated by Gödel's results on the incompleteness of arithmetic demonstrated in the 1920s) that the focus on mechanical executors emerged, leading culturally to the birth of informatics as an autonomous discipline.

Within informatics, the specification of an algorithm therefore always makes reference, implicitly or explicitly, to a specific type of automaton. As we saw in the first of the posts where we explained the concept of automaton, there are indeed some that cannot perform certain computations (finite state automata) while others (register machines) are capable of solving any problem that can be solved mechanically, just as the universal Turing machine (UTM) can do. This is why it's important to always indicate which agent we have in mind for executing the algorithm itself. From now on we'll assume—as is customary in informatics—that it's any automaton equivalent to the UTM. We should add that, by requiring that the specification of an algorithm necessarily reference the automaton that will execute it, it follows that each step of the algorithm must necessarily correspond to one or more instructions that the agent is directly capable of implementing. In other words, if each step isn't mechanically and automatically executable, the described procedure isn't an algorithm. On the other hand, the fact that the algorithm must terminate in finite time isn't an absolutely relevant aspect, considering that there are situations in which computations never terminate: think, for example, of control algorithms for industrial equipment that must be operational without interruption.

It's often said—at a popular level—that an algorithm is like a cooking recipe. This analogy is true in the sense that the description of a recipe is independent both of the specific ingredients that are actually used (the specification of "100 grams of double-zero flour" and "300 grams of apricot jam" doesn't prescribe specific brands or varieties) and of how their actual manipulation takes place ("mix the flour and sugar" doesn't prescribe the use of hands or spatulas). The term algorithm therefore denotes the finite set of instructions that specify the computation procedure at a more abstract level than any possible representation through a language directly comprehensible by the automaton that must execute it. In other words, the algorithm is what remains invariant, given an agent, with respect to all ways of expressing it through specific finite lists of instructions directly executable by the agent itself.

In both the case of a recipe and an algorithm, the executor must be capable of implementing the received instructions. However, the agent that executes a cooking recipe is a human being who certainly doesn't perform their actions mechanically and automatically, but uses their intelligence and flexibility to achieve the described goal even (to a certain extent that depends on their specific experience) in the presence of errors in the recipe or variations in the context in which they operate. This allows the execution of even recipes whose specific instructions appeal to the executor's judgment, such as "add salt to taste." This certainly isn't mechanical execution, so a cooking recipe isn't an algorithm! In contrast, an automaton has no room for interpretation, adaptation, and flexibility. Even the simplest difference between what it's asked to do and what it's capable of doing, intrinsically or in the environment, makes it impossible to successfully execute the program.

To specify an algorithm that an automaton must implement, it's therefore necessary to use the instructions of the programming language that the automaton is capable of executing and write the related computer program—that is, one of the many different possible ways of making the algorithm explicit in that specific programming language.

In the figure below we graphically present the relationships between these concepts: the programming language is the means through which the algorithm takes the concrete form of a program that is executed by the automaton.

With a literary comparison, we can say that between an algorithm and a program (any of the many different possible concretizations) there exists, through the programming language, the same relationship that exists between a thought and one of its written forms (one of many possible), through the language chosen for expression. Using philosophical terminology instead, we can say that the algorithm is the "Platonic idea" of a specific computation process, while a program is one of its many possible concretizations.

We'll see in the next post whether there's always an algorithm for whatever computation we want to perform.

[[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 30 October 2024.