Strolling through informatics #10 – Putting multiple automata to work

previous #9 ––– next #11

by Enrico Nardelli

(versione italiana qua)

As we mentioned in stage 6 of this journey (Understanding algorithms is not difficult), informatics as a scientific discipline was born – from a cultural standpoint – when we began to consider the possibility of executing algorithms mechanically through an automaton. Subsequently, however, we realize that computation can also be carried out with the participation of multiple agents, a condition that in the current era is evident even to the average person, due to the omnipresence of the Internet. This type of situation, generally called "distributed computing", presents various aspects. In the course of the next stages, we will examine three of the most important ones, which we briefly introduce here.

A first aspect is cooperation, which refers to a set of automata that must collectively perform a computation and, therefore, cooperate in achieving this objective. Much like when a group of people must carry out a certain task in collaboration. For example, there might be an office procedure that requires checks on different aspects, each under the responsibility of a different person and to be carried out in an established order. In such cases, communication between the different executors becomes necessary to coordinate the various computations that each one performs.

A second aspect is synchronization, in which there is a need to avoid interfering with each other in the use of shared resources, without there necessarily being cooperation. Still staying within the context of office procedure approval, imagine that each person in charge has their own procedures to approve, without having to coordinate with others for the decision. The approval process, however, requires putting a special stamp on it. The particularity of the stamp is that it is composed of two parts, each stored in a different repository. It is therefore necessary for the various people in charge to synchronize to avoid the case where one person, after having retrieved one part of the stamp, finds themselves blocked because simultaneously another person has already retrieved the other part from the other repository.

A third aspect, consensus, refers to the fact that both communications between the various agents and their behavior can be subject to failures or errors. How then can we be sure that the communications we have sent have actually arrived? How can we be sure we have received the counterpart's response? We observe that this aspect is extremely relevant in practical applications, where failures, temporary or permanent, can normally occur, despite all the precautions that can be taken to prevent this from happening.

Finally, let us clarify that, for simplicity of presentation, we only examine the case of agents all made in the same way and therefore capable of executing the instructions of the same language. Furthermore, we assume that they all have the same hierarchical level, that is, there is no one who commands and others who obey, and that they all execute the same algorithm.

We will therefore consider these three problems, cooperation, synchronization and consensus, in the next three posts, and we will conclude our excursus in the field of distributed computing with a post dedicated to communication protocols, which are a fundamental ingredient of that "network of networks", more commonly known as the Internet, which has been the fundamental factor for the spread of digital systems in the daily life of every person.

[[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 27 November 2024.

A passeggio con l'informatica #10 – Come mettere al lavoro più automi

precedente #9 ––– successivo #11

di Enrico Nardelli

Come abbiamo accennato nella tappa n.6 di questo viaggio (Comprendere gli algoritmi non è difficile), l’informatica come disciplina scientifica nasce – da un punto di vista culturale – quando si comincia a considerare la possibilità di eseguire algoritmi in modo meccanico attraverso un automa. Successivamente, però, ci si rende conto che un’elaborazione può essere attuata anche con la partecipazione di più agenti, condizione che nel periodo attuale è evidente anche all’uomo della strada, a causa dell’onnipresenza di Internet. Tale tipo di situazione, denominata in generale “computazione distribuita”, presenta diversi aspetti. Nel corso delle prossime tappe esamineremo tre dei più importanti, che qui introduciamo brevemente.

Un primo aspetto è la cooperazione, che fa riferimento a un insieme di automi che devono effettuare collettivamente un’elaborazione e, quindi, cooperano nel raggiungimento di quest’obiettivo. Un po’ come quando un gruppo di persone deve realizzare un certo compito in collaborazione. Ad esempio, vi può essere una pratica d’ufficio che necessita di controlli su aspetti differenti, ognuno di competenza di un differente responsabile e da svolgere secondo un ordine stabilito. In tal caso si rende necessaria una comunicazione tra i differenti esecutori per coordinare le varie elaborazioni che ognuno svolge.

Un secondo è la sincronizzazione, in cui vi è la necessità di non intralciarsi nell’uso di risorse condivise, senza che necessariamente vi sia una cooperazione. Sempre per rimanere nel contesto dell’approvazione di pratiche d’ufficio, si immagini che ogni responsabile abbia le sue pratiche da approvare, senza doversi coordinare con gli altri per la decisione. Il processo di approvazione richiede però di mettere un timbro particolare su di essa. La particolarità del timbro è che è composto da due parti, ognuna conservata in un differente deposito. È quindi necessario che i vari responsabili si sincronizzino per evitare il caso di un responsabile che, dopo aver prelevato una parte del timbro, si trovi bloccato perché contemporaneamente un altro responsabile ha già prelevato l’altra parte dall’altro deposito.

Un terzo aspetto, il consenso, fa riferimento al fatto che sia le comunicazioni tra i vari agenti, sia il loro comportamento, possono essere soggetti a guasti o errori. Come facciamo quindi ad essere sicuri che le comunicazioni che abbiamo inviato siano effettivamente arrivate? Come essere sicure di aver ricevuto la risposta della controparte? Osserviamo che questo aspetto è estremamente rilevante nelle applicazioni pratiche, dove guasti, temporanei o permanenti, possono normalmente accadere, nonostante tutte le precauzioni che possono essere prese affinché questo non succeda.

Chiariamo infine che, per semplicità di presentazione, esaminiamo solo il caso di agenti fatti tutti nello stesso modo e quindi in grado di eseguire le istruzioni di uno stesso linguaggio. Inoltre assumiamo che essi abbiano tutti lo stesso livello gerarchico, ovvero non c’è uno che comanda e altri che obbediscono, e che eseguano tutti lo stesso algoritmo.

Considereremo quindi questi tre problemi, cooperazione, sincronizzazione e consenso, nei prossimi tre post, e concluderemo il nostro excursus nell’ambito della computazione distribuita con un post dedicato ai protocolli di comunicazione, che sono un ingrediente fondamentale di quella “rete delle reti”, più comunemente conosciuta come Internet, che è stata il fattore fondamentale per la diffusione dei sistemi digitali nella vita quotidiana di ogni persona.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 27 novembre 2024.

Strolling through informatics #9 – Algorithms at the boundary

previous #8 ––– next #10

by Enrico Nardelli

(versione italiana qua)

To complete our picture of algorithmic problem solving, we need to discuss one more situation that is extremely important in today's context. Based on what was said in the previous post (How long does this algorithm take?), there can exist problems for which no algorithms with polynomial complexity functions are known (and therefore we cannot say they belong to class P), but for which proof of the impossibility of obtaining them has not yet been found (and therefore we cannot say they properly belong to class EXP). This means that for these problems we know at least one solution algorithm (whose complexity function is exponential), and this classifies them as computable problems, but we cannot say whether they are problems that belong to the "good" variety (i.e., they admit polynomial algorithms, meaning they are tractable) or the "bad" variety (with only exponential algorithms, meaning they are intractable). In this case the problem is in a kind of limbo, in which theoretical computer scientists have identified a very important set called class NP, which marks the boundary between tractability and intractability.

Without going into the details of how this class is defined (for which I refer to the book The Computer Revolution), we can say that it includes problems whose solutions can be verified in polynomial time and for which only solution algorithms of exponential complexity are known. Indeed, hundreds of these problems exist (thousands if we consider their variants), for which mutual equivalence has been proven. This equivalence means that if a polynomial algorithm were found for just one of them, then all these problems would fall into class P (they would be, that is, tractable problems). If just one of them were instead proven to properly belong to class EXP, then they would all be classified as intractable (though this latter hypothesis seems unlikely to most scholars).

Given the current state of knowledge in theoretical informatics, we know that class P is strictly contained in class EXP (I remind you that a set A is strictly contained in set B if every element of A also belongs to B and furthermore we are certain of the existence of elements that belong to B and do not belong to A). However, the known relationships between classes P, NP and EXP are only of containment, meaning that P is contained in NP and that NP is contained in EXP, but we don't know exactly which of these containments is strict. The most interesting aspect concerns the relationship between classes P and NP. It could be strict or the two classes could coincide. The problem of whether class P and class NP coincide or not, that is

P=NP ?

is probably the most famous open problem in theoretical informatics. The Clay Mathematics Institute included it in 2000 among the seven millennium problems and has offered a prize of one million dollars for its proof.

The problem has particular interest since problems in class NP that are thought not to be in P often form the basis of cryptographic methods that protect the security of commercial transactions on the Internet. For example, the RSA public key encryption system bases its security on the fact that the decomposition of an integer into prime factors is one of these problems.

Since no efficient algorithms (i.e., executable in polynomial time) are currently known for decomposing an integer into its prime factors, the system cannot be broken in an acceptable time. It should be noted that, with sufficient dedicated hardware equipment (which is within reach of large organizations that can count on substantial economic resources such as, for example, the NSA, acronym for National Security Agency, the national security agency of the United States) it is possible to decompose integers of 1,024 bits, which was the recommended value for constructing RSA keys until a few years ago. Bruce Schneier, a US security expert, recommended in 2007, when the decomposition of an integer of about 1,024 bits was announced (albeit of a particular type that made the work simpler), to abandon keys of this length. The availability of so-called "quantum" computers is another possible threat to RSA public key encryption, but appropriate countermeasures are being taken for this eventuality as well.

[[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 20 November 2024.

A passeggio con l'informatica #9 – Algoritmi al confine

precedente #8 ––– successivo #10

di Enrico Nardelli

Per completare il quadro della risoluzione algoritmica dei problemi, dobbiamo discutere ancora una situazione, estremamente importante nel contesto odierno. In base a quanto detto nel post precedente, possono esistere dei problemi per i quali non si conoscono algoritmi con funzione di complessità polinomiale (e quindi non si può dire che appartengono alla classe P), ma per cui non si è ancora trovata la dimostrazione di impossibilità di ottenerli (e quindi non si può dire che appartengono propriamente alla classe EXP). Ciò vuol dire che per essi si conosce almeno un algoritmo risolutivo (la cui funzione di complessità è esponenziale), e questo li classifica come problemi computabili, ma non si sa dire se siano problemi che appartengono alla varietà “buona” (cioè ammettono algoritmi polinomiali, ossia sono trattabili) oppure “cattiva” (con solo algoritmi esponenziali, cioè intrattabili). In questo caso il problema è in una specie di limbo, nel quale gli informatici teorici hanno individuato un insieme molto importante detto classe NP, che marca il confine fra la trattabilità e l’intrattabilità.

Senza entrare nel dettaglio di come tale classe venga definita (per cui rimando al mio libro La rivoluzione informatica), possiamo dire che ad essa appartengono i problemi le cui soluzioni sono verificabili in tempo polinomiale e per i quali si conoscono solo algoritmi risolutivi di complessità esponenziale. In effetti esistono centinaia di questi problemi (migliaia se ne consideriamo le varianti), per i quali è stata dimostrata l’equivalenza reciproca. Questa equivalenza vuol dire che se per uno solo di essi si trovasse un algoritmo polinomiale, allora tutti questi problemi rientrerebbero nella classe P (sarebbero, cioè, problemi trattabili). Se per uno solo di essi si dimostrasse invece l’appartenenza propria alla classe EXP, allora verrebbero tutti classificati come intrattabili (anche se quest’ultima ipotesi appare poco probabile alla maggior parte degli studiosi).

Allo stato attuale delle conoscenze dell’informatica teorica si sa che la classe P è strettamente contenuta nella classe EXP (ricordo che un insieme A è strettamente contenuto nell’insieme B se ogni elemento di A appartiene anche a B e inoltre si è certi dell’esistenza di elementi che appartengono a B e non appartengono ad A). Però, le relazioni note tra le classi P, NP ed EXP sono solo di contenimento, cioè che P è contenuta in NP e che NP è contenuta in EXP, ma non si sa esattamente quale di questi contenimenti sia stretto. L’aspetto più interessante riguarda la relazione tra le classi P e NP. Potrebbe essere stretto oppure le due classi potrebbero coincidere. Il problema se la classe P e la classe NP coincidano o meno, ovvero

P=NP ?

è probabilmente il problema aperto più famoso dell’informatica teorica. Il Clay Mathematics Institute lo ha inserito nel 2000 fra i sette problemi del millennio e ha offerto un premio di un milione di dollari per la sua dimostrazione.

Il problema ha un interesse particolare dal momento che problemi nella classe NP che si pensa non siano in P sono spesso alla base dei metodi crittografici, che proteggono la sicurezza delle transazioni commerciali su Internet. Ad esempio, il sistema di cifratura a chiave pubblica RSA ha alla base della sua sicurezza il fatto che la scomposizione di un numero intero in fattori primi è uno di questi problemi.

Poiché non si conoscono, al momento attuale, algoritmi efficienti (cioè eseguibili in tempo polinomiale) per scomporre un intero nei suoi fattori primi, il sistema non può essere violato in un tempo accettabile. Va ricordato che, con sufficienti attrezzature hardware dedicate (che sono alla portata di organizzazioni di grandi dimensioni che possono contare su ingenti risorse economiche quali, ad esempio, l’NSA, acronimo di National Security Agency, l’agenzia per la sicurezza nazionale degli Stati Uniti) si riescono a scomporre interi di 1.024 bit, che era il valore raccomandato per la costruzione delle chiavi di RSA fino a qualche anno fa. Bruce Schneier, esperto USA di sicurezza, ha raccomandato nel 2007, quando è stata annunciata la scomposizione di un intero di circa 1.024 bit (anche se di un tipo particolare che ha reso il lavoro più semplice) di abbandonare le chiavi di questa lunghezza. La disponibilità di computer cosiddetti “quantistici” è un’altra possibile minaccia alla cifratura a chiave pubblica RSA, ma anche per questa eventualità si stanno prendendo le opportune contromisure.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 20 novembre 2024.

Strolling through informatics #8 – How long does this algorithm take?

previous #7 ––– next #9

by Enrico Nardelli

(versione italiana qua)

We saw in the previous post that for some computations, it's impossible to find any algorithm. Additionally, since we are mortal and don't have infinite time available to obtain an answer, we're also interested in knowing how long a certain algorithm might take to complete its computation.

Initially, we're interested in distinguishing those problems, called tractable, where as the problem grows in size we continue to wait a "human" amount of time for the answer, from those problems, called intractable, where this doesn't happen. Instead of talking about time, I'll discuss these aspects by referring to the number of steps needed to solve the problem by the best known algorithm for it. The reason for this choice is that time can depend on the intrinsic speed of the specific computer used to execute the (program that implements the) algorithm, while we're interested in a characterization independent of technological developments. In any case, the results in terms of tractability or intractability don't change. Conversely, but we won't discuss this in these posts and I refer you to the book La rivoluzione informatica for a discussion, the use of quantum computers makes tractable some of the problems that are intractable using a classical computer (which is an automaton equivalent to the UTM).

Every algorithm, once expressed in a program, requires time proportional to the number of instructions that must be executed. Given the algorithm, therefore, one can write the mathematical function, called the algorithm's complexity function, which expresses this number based on the size N of the problem. We should all remember, having studied it in school, the difference between a polynomial function and an exponential function. In the first, the argument N is the base of a power (e.g., N ² or N ³ or even N ¹⁰), while in the second it's the exponent of the power (e.g., 2N or 3N or even 10N). Exponential functions grow much faster than polynomial ones. In the following table we report the value of these functions for different values of the argument N. We recall that the symbol "~" means "about," "approximately," and that the notation, for example, 10¹⁰ indicates the digit 1 followed by 10 zeros, that is, the value 10 billion. In the table you can see that already for N = 60, all the exponential functions presented have a value greater than all the polynomial functions.

It's important to remember that the complexity function is expressed, for each algorithm, with reference to the so-called "worst case" for the algorithm's execution, that is, the most unfavorable one in terms of the number of instructions to execute (assuming, for simplicity, that all instructions require the same time). Let's consider the first of the problems presented in the previous post, that of sorting. We want to know what the maximum guaranteed execution time of the algorithm is as a function of the quantity N, whatever may happen with the N input data. It can be proven that for this problem the best known algorithm guarantees a time proportional to N log(N ), where "log" is the logarithmic function we should remember from high school, and this result cannot be improved.

Let's now assume that executing a single instruction requires a modern computer one nanosecond, that is, one billionth of a second. In formula, 10^-9 (that is, 1/10⁹) seconds. Let's then consider the second problem, of shortest paths, for which the best algorithm guarantees in the worst case the execution of at most N³ instructions for a list with N cities (ignoring marginal improvements obtained in recent years). Then we're able to solve it for 100 cities in one thousandth of a second (because 1,000,000, that is 10⁶, multiplied by 10^-9 equals 10³, that is 1/10³ = 0.001) and for 1,000 cities in one second (1,000³ = 10⁹, which multiplied by 10^-9 equals exactly 1). If we then needed to solve it for 10,000 cities, 1,000 seconds would be needed, or about 17 minutes. For 100,000 cities it would even require a million seconds, equal to about 12 days: a very long time, but all in all acceptable.

Let's instead see what happens for the third problem, the traveling salesman, for which the best known algorithms require the execution of 2N instructions for a list with N cities. In this case we could solve it for 20 cities in just over one thousandth of a second, but already for 30 cities one second would be necessary, 40 cities would require 17 minutes, and 50 would be the maximum number of cities for which the problem is solvable waiting a time of 12 days. The solution for 60 cities could be obtained in about 32 years, clearly an unacceptable time.

So here's how the distinction between "tractable" and "intractable" problems is given based on the type of function that expresses the number of steps necessary for its solution algorithms. In particular, if a solution algorithm is known for which such a complexity function is polynomial, that is, the problem admits a polynomial algorithm, then the problem is called tractable (that is, it's said to belong to class P). If instead it has been proven that every possible solution algorithm has an exponential complexity function, the problem is intractable (that is, it's said to belong properly to class EXP). While in the first case it's enough to find just one polynomial algorithm to define the problem as tractable, in the second case the proof must be conducted independently of specific algorithms, since the set of possible solution algorithms is infinite and the fact that a polynomial complexity algorithm hasn't been found so far doesn't imply that it doesn't exist.

To discuss this situation from another point of view and to better understand that intractability cannot be solved with technological advances, let's consider what would happen if we had a computer a thousand times faster than current ones. Having 12 days available, we would be able to solve the second problem for a million cities instead of 100,000. In the case of the third problem, in the same time of 12 days we would only manage to go from 50 to 60 cities!

The next post, the last one dedicated to algorithms, will consider a boundary situation between tractability and intractability that is very relevant both from a cultural and practical point of view.

[[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 13 November 2024.

A passeggio con l'informatica #8 – Ma quanto ci mette quest’algoritmo?

precedente #7 ––– successivo #9

di Enrico Nardelli

Abbiamo visto nel post precedente che per alcune elaborazioni non è possibile trovare alcun algoritmo. In aggiunta, dal momento che siamo mortali e non abbiamo a disposizione un tempo infinito per ottenere una risposta, ci interessa anche sapere quanto tempo può metterci un certo algoritmo a completare la sua elaborazione.

In prima istanza ci interessa distinguere quei problemi, chiamati trattabili, in cui man mano che il problema cresce di dimensione continuiamo a dover aspettare un tempo “umano” per la risposta, e quei problemi, detti invece intrattabili, in cui questo non accade. Invece di parlare di tempo, discuterò questi aspetti facendo riferimento al numero di passi necessario per risolvere il problema da parte del miglior algoritmo noto per esso. Il motivo di questa scelta è che il tempo può dipendere dalla velocità intrinseca dello specifico calcolatore usato per l’esecuzione del (programma che concretizza) l’algoritmo, mentre noi siamo interessati a una caratterizzazione indipendente dalle evoluzioni tecnologiche. In ogni caso, i risultati in termini di trattabilità o intrattabilità non cambiano. Viceversa, ma non ne parleremo in questi post e vi rimando al libro La rivoluzione informatica per una discussione, l’utilizzo di computer quantistici rende trattabili alcuni dei problemi che sono intrattabili usando un computer classico (che è un automa equivalente alla MUT).

Ogni algoritmo, una volta espresso in un programma, richiede un tempo proporzionale al numero delle istruzioni che devono essere eseguite. Dato quindi l’algoritmo, si può scrivere la funzione matematica, detta funzione di complessità dell’algoritmo, che esprime questo numero in base alla dimensione N del problema. Dovremmo ricordare tutti, per averla studiata a scuola, la differenza tra una funzione polinomiale e una funzione esponenziale. Nella prima, l’argomento N è la base di una potenza (p.es. N ² oppure N ³ o anche N¹⁰), mentre nella seconda è l’esponente della potenza (p.es. 2^N oppure 3^N o anche 10^N ). Le funzioni esponenziali crescono molto più velocemente di quelle polinomiali. Nella tabella seguente riportiamo il valore di queste funzioni per differenti valori dell’argomento N. Ricordiamo che il simbolo “ ~ ” vuol dire “circa”, “approssimativamente”, e che la notazione, ad esempio, 10¹⁰ indica la cifra 1 seguita da 10 zeri, cioè il valore 10 miliardi. Nella tabella si vede che già per N = 60, tutte le funzioni esponenziali presentate hanno valore maggiore di tutte le funzioni polinomiali.

È importante ricordare che la funzione di complessità viene espressa, per ogni algoritmo, in riferimento al cosiddetto “caso pessimo” per l’esecuzione dell’algoritmo stesso, ovvero a quello più sfavorevole in termini di numero di istruzioni da eseguire (assumendo, per semplicità, che tutte le istruzioni richiedano uno stesso tempo). Consideriamo il primo dei problemi presentati nel post precedente, quello dell’ordinamento. Vogliamo sapere quale sia il tempo massimo garantito di esecuzione dell’algoritmo in funzione della quantità N, qualunque cosa possa accadere con gli N dati in ingresso. Si può dimostrare che per questo problema il miglior algoritmo conosciuto garantisce un tempo proporzionale a N⋅log(N ), dove “log” è la funzione logaritmica che dovremmo ricordarci dalle scuole superiori, e questo risultato non è migliorabile.

Assumiamo ora che l’esecuzione di una singola istruzione richieda a un moderno computer un nanosecondo, cioè un miliardesimo di secondo. In formula, 10^-9, cioè (1/10)⁹ secondi. Consideriamo poi il secondo problema, dei cammini minimi, per il quale il miglior algoritmo garantisce nel caso pessimo l’esecuzione di al più N ³ istruzioni per una lista con N città (trascurando miglioramenti marginali ottenuti negli ultimi anni). Allora siamo in grado di risolverlo per 100 città in un millesimo di secondo (perché 1.000.000, cioè 10⁶, moltiplicato per 10^-9 fa 10^-3, cioè (1/10)³ = 0,001) e per 1.000 città in un secondo (1.000³ = 10⁹, che moltiplicato per 10^-9 fa esattamente 1). Se avessimo poi bisogno di risolverlo per 10.000 città, servirebbero 1.000 secondi, ovvero circa 17 minuti. Per 100.000 città sarebbe addirittura necessario un milione di secondi, pari a circa 12 giorni: un tempo molto lungo, ma tutto sommato accettabile.

Vediamo invece cosa accade per il terzo problema, del commesso viaggiatore, per il quale i migliori algoritmi conosciuti richiedono l’esecuzione di 2^N istruzioni per una lista con N città. In questo caso potremmo risolverlo per 20 città in appena più di un millesimo di secondo, ma già per 30 città sarebbe necessario un secondo, 40 città richiederebbero 17 minuti, e 50 sarebbe il massimo numero di città per cui il problema è risolvibile aspettando un tempo di 12 giorni. La risoluzione per 60 città potrebbe essere ottenuta in circa 32 anni, chiaramente un tempo inaccettabile.

Ecco quindi che la distinzione tra problemi “trattabili” e problemi “intrattabili” viene data in base al tipo di funzione che esprime il numero di passi necessario per i suoi algoritmi risolutivi. In particolare, se è noto un algoritmo risolutivo per il quale tale funzione di complessità è polinomiale, cioè il problema ammette un algoritmo polinomiale, allora il problema è detto trattabile (cioè, si dice che appartiene alla classe P). Se invece si è dimostrato che ogni possibile algoritmo risolutivo ha una funzione di complessità esponenziale, il problema è intrattabile (cioè, si dice che appartiene propriamente alla classe EXP).

Mentre nel primo caso basta trovare un solo algoritmo polinomiale per definire il problema come trattabile, nel secondo caso la dimostrazione deve essere condotta prescindendo da specifici algoritmi, dal momento che l’insieme dei possibili algoritmi risolutivi è infinito e il fatto che un algoritmo di complessità polinomiale non sia stato finora trovato non implica che non esista.

Per discutere questa situazione da un altro punto di vista e far comprendere meglio che l’intrattabilità non può essere risolta con gli avanzamenti tecnologici, consideriamo cosa accadrebbe se avessimo un computer mille volte più veloce di quelli attuali. Avendo allora a disposizione 12 giorni, saremmo in grado di risolvere il secondo problema per un milione di città invece che per 100.000. Nel caso del terzo problema, nello stesso tempo di 12 giorni riusciremmo a passare solo da 50 a 60 città!

Il prossimo post, l’ultimo dedicato agli algoritmi, prenderà in considerazione una situazione di confine fra la trattabilità e l’intrattabilità molto rilevante sia da un punto di vista culturale che pratico.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 13 novembre 2024.

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.

A passeggio con l'informatica #7 – Possiamo sempre trovare un algoritmo?

precedente #6 ––– successivo #8

di Enrico Nardelli

La domanda con cui ci siamo lasciati nel post precedente era se sia sempre possibile trovare l’algoritmo per effettuare l’elaborazione che abbiamo in mente.

A questo scopo bisogna prima di tutto chiarire che le situazioni alle quali possiamo applicare gli algoritmi richiedono che sia possibile descrivere con precisione sia l’insieme dei possibili dati di ingresso (detto input ) all’algoritmo stesso che l’insieme dei risultati in uscita (detto output ) accettabili, espressi in funzione degli input. Ma anche per i problemi formulabili in questo modo, vedremo nel seguito che la risposta è negativa. Aggiungiamo che la descrizione viene eventualmente fatta, per algoritmi che non terminano mai perché le elaborazioni che devono effettuare non si devono interrompere, con riferimento a un determinato intervallo temporale.

Consideriamo adesso quattro problemi che presentano caratteristiche diverse in termini di computabilità (o calcolabilità, i termini che denotano il settore dell’informatica che si occupa di questi aspetti), che verranno discusse in questo e nel successivo post.

1. Un primo esempio di problema (detto “ordinamento”) affrontabile algoritmicamente prevede in input una lista di N numeri interi e richiede in output la lista dei numeri ordinati per valore crescente.
2. Un secondo esempio di problema (detto “cammini minimi”) prevede in input una lista di N città, per ognuna delle quali è specificato un elenco di città (appartenenti alla lista stessa) alle quali esse sono connesse direttamente da un tratto di strada di cui viene data la lunghezza. In output si richiede, per ogni coppia di città P e Q dell’elenco, la successione dei tratti di strada che porta da P a Q che ha lunghezza totale minima.
3. Un terzo esempio (detto “commesso viaggiatore”) ha lo stesso input del secondo, ma l’output richiede di ottenere una successione di tratti di strada che passi per tutte le città dell’elenco una volta sola e abbia lunghezza totale minima.
4. Un quarto problema (detto “arresto”) ha come input uno specifico programma scritto in un determinato linguaggio di programmazione e uno qualunque dei possibili dati di ingresso al programma. L’output richiesto è “VERO” se quel programma elaborando questi dati si arresta dopo un tempo finito, “FALSO” altrimenti.

Osserviamo che l’algoritmo, per essere tale, deve “funzionare”, cioè produrre l’output corretto, per tutti i possibili input. Ciò vuol dire, per il primo problema, per tutte le possibili liste di N numeri; per il secondo e il terzo problema, per tutte le possibili liste di N città con tutte le possibili connessioni a città adiacenti; per il quarto problema, per tutti i possibili programmi scritti nel linguaggio scelto e tutti i loro possibili dati di ingresso.

Per i primi tre problemi sopra descritti esistono algoritmi risolutivi, quindi si dice che i problemi sono computabili, mentre il quarto problema, quello dell’arresto, non ammette alcun algoritmo risolutivo, ed è quindi un problema incomputabile. A questo punto qualcuno potrebbe pensare, visto che un algoritmo deve essere comunque espresso in un determinato linguaggio di programmazione mediante un programma che deve essere eseguito da un determinato automa, che basterebbe avere un linguaggio più moderno o un automa più potente.

Non è così. È stato proprio Alan Turing a dimostrare, nell’articolo scientifico del 1936 che viene considerato la nascita dell’informatica come disciplina scientifica autonoma, che il quarto problema non è intrinsecamente risolvibile, a prescindere da quale siano il linguaggio di programmazione o l’automa usati. In altre parole, non esiste un algoritmo per il problema dell’arresto.

Sottolineo che tale risultato rimane vero anche considerando automi di tipo “quantistico” (che sono il modello teorico dei cosiddetti “computer quantistici ” di cui molto si parla in questi anni). Si tratta di un risultato importantissimo, non solo dal punto di vista culturale ma anche su un piano filosofico, perché definisce dei limiti ben precisi a ciò che può essere realizzato mediante i calcolatori e, quindi, anche alla nostra possibilità di “conoscere” qualcosa attraverso procedimenti algoritmici. Il che non può che farci piacere, visto che come esseri umani abbiamo a nostra disposizione altri modi di “conoscere”, che esulano dall’assoluta razionalità meccanica di un automa e che questi ultimi non possiedono.

Nel prossimo post ci occuperemo del tempo necessario per l’esecuzione degli algoritmi e di come questo possa variare da situazioni accettabili ad altre del tutto insostenibili.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 6 novembre 2024.

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.

A passeggio con l'informatica #6 – Comprendere gli algoritmi non è difficile

precedente #5 ––– successivo #7

di Enrico Nardelli

Molti utilizzano la parola algoritmo, ma non sempre è chiaro il significato di tale concetto. Intanto cominciamo con il dire che il termine algoritmo risale al latino medievale, epoca in cui, secondo il vocabolario Treccani online, «indicava i procedimenti di calcolo fondati sopra l’uso delle cifre arabiche ». Come penso ormai molti sappiano, la parola deriva dall’appellativo al-Khuwārizmī del matematico arabo del IX secolo Muḥammad ibn Mūsa, che era nativo di Khwarizm, regione dell’Asia Centrale. Nell’informatica si indica con questo termine una versione astratta, cioè indipendente da uno specifico linguaggio reale di programmazione, dell’elaborazione desiderata. Un algoritmo è quindi un metodo risolutivo, che prescinde (cioè astrae) da una specifica forma fisica di espressione. Tale astrazione è fondamentale dal punto di vista scientifico, perché fornisce generalità al modo di descrivere le varie elaborazioni.

D’altro canto, un algoritmo può essere effettivamente eseguito soltanto se viene specificato qual è l’automa (detto anche esecutore o agente) che lo deve attuare. Questa indicazione non era rilevante prima della nascita dell’informatica, quando erano solo i matematici a eseguire algoritmi, cioè procedimenti risolutivi di problemi. Le radici culturali dell’informatica risiedono nello sforzo che i matematici hanno attuato nei primi decenni del XX secolo per automatizzare la dimostrazione dei teoremi. Da questo tentativo (frustrato dai risultati di incompletezza dell’aritmetica dimostrati negli anni 20 di quel secolo da Gödel) che è nata quella focalizzazione sull’esecutore meccanico che ha portato, da un punto di vista culturale, alla nascita dell’informatica come disciplina autonoma.

All’interno dell’informatica, la specifica di un algoritmo fa quindi sempre riferimento, implicitamente o esplicitamente, a una specifica tipologia di automa. Come abbiamo visto nel primo dei post in cui abbiamo spiegato il concetto di automa, ne esistono infatti alcuni che non riescono a realizzare una certa elaborazione (gli automi a stati finiti) mentre altri (le macchine a registri) sono in grado di risolvere qualunque problema che sia risolvibile in modo meccanico, così come è in grado di fare la macchina universale di Turing (MUT). Per questo è importante indicare sempre qual è l’agente che si ha in mente per l’esecuzione dell’algoritmo stesso. D’ora in avanti assumeremo – com’è abituale nell’informatica – che sia uno qualunque degli automi equivalenti alla MUT. Aggiungiamo che, richiedendo come necessario che la specifica di un algoritmo faccia riferimento all’automa che lo eseguirà, ne deriva che ogni passo dell’algoritmo deve necessariamente corrispondere a una o più istruzioni che l’agente è direttamente in grado di attuare. In altre parole, se ogni passo non è meccanicamente e automaticamente eseguibile, il procedimento descritto non è un algoritmo. D’altro canto, il fatto che l’algoritmo debba terminare in un tempo finito non è un aspetto rilevante in assoluto, considerato che ci sono situazioni nelle quali le elaborazioni non terminano mai: si pensi, ad esempio, agli algoritmi di controllo di apparati industriali che devono essere operativi senza interruzioni.

Si dice spesso – a livello divulgativo – che l’algoritmo è come una ricetta di cucina. Quest’analogia è vera nel senso che la descrizione di una ricetta è indipendente sia dagli specifici ingredienti che vengono veramente usati (la specifica di “100 grammi di farina doppio zero” e “300 grammi di marmellata di albicocche” non prescrive specifiche marche o varietà) sia da come avviene la loro effettiva manipolazione (“mescolare la farina e lo zucchero” non prescrive l’uso di mani o spatole). Il termine algoritmo denota quindi l'insieme finito delle istruzioni che specificano il procedimento di elaborazione a un livello più astratto rispetto a ogni possibile rappresentazione mediante un linguaggio direttamente comprensibile dall’automa che lo deve eseguire. In altre parole, l'algoritmo è ciò che è invariante, dato un agente, rispetto a tutti i modi di esprimerlo mediante specifiche liste finite di istruzioni direttamente eseguibili dall’agente stesso.

Sia nel caso di una ricetta che di un algoritmo l’esecutore deve essere in grado di attuare le istruzioni ricevute. Però, l’agente che esegue una ricetta di cucina è un essere umano che certamente non realizza meccanicamente e automaticamente le proprie azioni, ma utilizza la sua intelligenza e flessibilità per ottenere lo scopo descritto anche (in una certa misura che dipende dalla sua specifica esperienza) in presenza di errori nella ricetta o di variazioni nel contesto in cui opera. Questo permette di eseguire anche ricette le cui specifiche istruzioni fanno appello alla valutazione dell’esecutore come, ad esempio, “aggiungere sale quanto basta”. Non si tratta certamente di un’esecuzione meccanica, perciò una ricetta di cucina non è un algoritmo! Diversamente, un automa non ha alcuno spazio per interpretazione, adattamento e flessibilità. Anche una semplicissima differenza tra ciò che gli viene chiesto di fare e ciò che è in grado di fare, intrinsecamente o nell’ambiente, determina l’impossibilità di eseguire con successo il programma.

Per specificare quindi un algoritmo che un automa deve attuare è necessario usare le istruzioni del linguaggio di programmazione che l’automa è in grado di eseguire e scrivere il relativo programma informatico, cioè uno dei tanti diversi possibili modi di esplicitare l’algoritmo in quello specifico linguaggio di programmazione.

Nella figura sotto presentiamo graficamente le relazioni tra questi concetti: il linguaggio di programmazione è il mezzo attraverso cui l’algoritmo assume la forma concreta di un programma che viene eseguito dall’automa.

Con un paragone letterario, possiamo dire che tra un algoritmo e un programma (una qualunque delle tante diverse possibili concretizzazioni) sussiste, attraverso il linguaggio di programmazione, la stessa relazione che c’è tra un pensiero e una sua forma scritta (una delle tante possibili), attraverso il linguaggio scelto per esprimersi. Usando invece una terminologia filosofica, possiamo dire che l’algoritmo è la “idea platonica” di uno specifico processo di elaborazione, mentre un programma è una delle sue tante concretizzazioni possibili.

Vedremo nel prossimo post se c’è sempre un algoritmo per qualunque elaborazione vogliamo effettuare.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 30 ottobre 2024.