Strolling through informatics #5 – How to instruct a computer

previous #4 ––– next #6

by Enrico Nardelli

(versione italiana qua)

With this post we complete our discussion of automata (the technical term used in informatics to denote computers), that is, the mechanisms that perform the computations we need.

In the previous post (How a computer works) we described a very simple version of a register machine (RM), an automaton that despite its simplicity has the same computational power as the computers used on a daily basis.

We must now discuss the language that the RM is able to "understand," that is, describe which instructions it can execute. Many choices are possible, but for our educational purposes we can stick to the minimum necessary to express any computation. For this purpose, only the four instructions presented in detail below are necessary, which, despite constituting the entire language we can use to command the RM, give it the same computational power as any other computer.

• The End instruction is the one that stops the RM's operation, that is, it causes the finite state automaton that describes the behavior of the RM's Control Unit to make the transition to the "End" state.
• The Increment X instruction is the one that increases by 1 the value contained in the memory cell at address X. In what follows we will say "cell X" to indicate more concisely the "memory cell at address X."
• The Go to X instruction is the one that makes the next instruction that the RM will execute be the one at address X. This is achieved by writing the value X into IC.
• The X Decrement or Go to Y instruction is composed of two parts. First, it checks whether the content of the cell whose address is written inside cell X is greater than 0. If this is true, then the content of the cell whose address is written inside cell X is decreased by 1. If this is not true, the value Y is written into IC instead (and therefore at the next step the RM will execute the instruction contained in cell Y).

The reader is invited to pay attention to the fact that in the "Increment X" instruction it is the content of cell X that is modified, while in the "X Decrement or Go to Y" instruction what is manipulated is not the content of cell X but the content of the cell whose address is written in cell X.

We now present in the left part of the following table the program that solves the problem stated two posts ago (that is, counting how many "2"s there are in a sequence), showing in the right part an instance (that is, a specific example) of the problem to be solved.

We have assumed that IC is the cell at address 0 and that the initial value inside it is 1, that is, that the program to be executed is stored starting from the memory cell at address 1. We have also assumed that the problem data, that is, the sequence of values for which we need to calculate how many are "2"s, is in memory starting from the cell at address 12 (it is, for this instance, a sequence of six values, the last of which is "0" and which contains three "2"s). The memory cell at address 10 serves to count how many "2" values have been encountered so far and will therefore contain, when the RM stops, the desired count value, while the memory cell at address 11 serves to scan through the sequence of values to be processed. The idea that the program implements is to decrement twice in succession the content of the cell whose address is written in cell 11. If after the first decrement the value reaches zero, then the cell did not contain "2" and the counter in cell 10 is not incremented. Otherwise, it contained "2" and the counter is incremented. In both cases, we move on to consider the next value in the sequence.

If the reader has the patience to execute step by step, mechanically, the instructions of the proposed program, they will indeed be able to verify that the desired value is calculated (three, for this instance). It is also suggested to try executing the program with other input value sequences, so as to be convinced that it solves completely mechanically any instance of the problem under consideration.

One last aspect remains to be discussed. How does the automaton "understand" what an instruction like "Increment X" or the other instructions means? As we have seen for the "Go to X" instruction, its meaning is given by the actions that the designer of the automaton has associated with the given instruction. In the case of "Go to X," its "meaning" is therefore given by the fact that when it is encountered in the program body, the value of X is written into IC. For this purpose, there is actually no need for "Go to X" to be written in the program; it is enough to write a short numerical code, for example 10, and make sure that this, when "executed," activates the physical mechanisms (normally, electronic circuits) that implement the desired behavior. Following this line, we obtain a program written entirely in binary encoding: this is the so-called machine language level, that is, the language that the physical machine, that is, the physical realization of the executor, can, with good approximation, understand and execute directly. One can think, to make a mechanical analogy, that this is the level at which the levers and gear wheels of a mechanical object operate. The program initially presented is instead at the so-called symbolic language level.

For now we only mention that the passage from a program written in a symbolic language to its machine language version can, and this should not surprise us, be executed completely mechanically by special translation programs, which we will discuss later when we return to this topic when we talk about virtualization.

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

A passeggio con l'informatica #5 – Come istruire un computer

precedente #4 ––– successivo #6

di Enrico Nardelli

Con questo post completiamo il discorso sugli automi (termine tecnico che si usa nell’informatica per denotare i computer), cioè i meccanismi che eseguono le elaborazioni di cui abbiamo bisogno.

Nel post precedente abbiamo descritto una versione molto semplice di macchina a registri (MR), un automa che nonostante la sua semplicità ho lo stesso potere computazionale dei computer che vengono quotidianamente usati.

Dobbiamo adesso parlare del linguaggio che la MR è in grado di “comprendere”, cioè descrivere quali istruzioni essa è in grado di eseguire. Sono possibili tante scelte, ma per i nostri scopi divulgativi possiamo rimanere al minimo necessario per poter esprimere qualunque computazione. A questo scopo sono necessarie solo le quattro istruzioni presentate in dettaglio nel seguito che, nonostante costituiscano tutto il linguaggio che possiamo usare per comandare la MR, le danno lo stesso potere computazionale di qualunque altro computer.

• L’istruzione Fine è quella che arresta il funzionamento della MR, cioè è quella che fa percorrere la transizione verso lo stato “Fine” all’automa a stati finiti che descrive il comportamento dell’Unità di Controllo della MR.
• L’istruzione Incrementa X è quella che aumenta di 1 il valore contenuto nella cella di memoria di indirizzo X. Nel seguito diremo “cella X” per indicare in modo più sintetico la “cella di memoria di indirizzo X”.
• L’istruzione Vai X è quella che fa sì che la prossima istruzione che eseguirà la MR sarà quella all’indirizzo X. Questo viene ottenuto scrivendo il valore X dentro IC.
• L’istruzione X Dim o Vai Y è composta di due parti. Dapprima si verifica se il contenuto della cella il cui indirizzo è scritto dentro la cella X è maggiore di 0. Se questo è vero allora il contenuto della cella il cui indirizzo è scritto dentro la cella X viene diminuito di 1. Se questo non è vero si scrive invece il valore Y dentro IC (e quindi al passo successivo la MR eseguirà l’istruzione contenuta nella cella Y).

Si invita il lettore a prestare attenzione al fatto che nell’istruzione “Incrementa X” è il contenuto della cella X che viene modificato, mentre nell’istruzione “X Dim o Vai Y” viene manipolato non il contenuto della cella X ma il contenuto della cella il cui indirizzo è scritto nella cella X.

Presentiamo adesso nella parte sinistra della seguente tabella il programma che risolve il problema enunciato due post fa (cioè contare quanti “2” ci sono in una sequenza), mostrando nella parte destra un’istanza (cioè, uno specifico esempio) del problema da risolvere.

Abbiamo assunto che IC sia la cella di indirizzo 0 e che il valore iniziale dentro di essa sia 1, cioè che il programma da eseguire sia memorizzato a partire dalla cella di memoria di indirizzo 1. Abbiamo altresì assunto che i dati del problema, cioè la sequenza di valori per la quale bisogna calcolare quanti sono i valori “2”, sia nella memoria a partire dalla cella di indirizzo 12 (si tratta, per quest’istanza, di una sequenza di sei valori, di cui l’ultimo è “0” e che contiene tre “2”). La cella di memoria di indirizzo 10 serve per contare quanti valori “2” si sono finora incontrati e quindi conterrà, quando la MR si arresta, il valore di conteggio desiderato, mentre la cella di memoria di indirizzo 11 serve per poter scandire la sequenza di valori da processare. L’idea che il programma realizza è quella di decrementare per due volte di seguito il contenuto della cella il cui indirizzo è scritto nella cella 11. Se dopo il primo decremento il valore arriva a zero allora la cella non conteneva “2” e non si incrementa il contatore nella cella 10. Altrimenti, conteneva “2” e il contatore viene incrementato. In entrambi i casi si passa a considerare il successivo valore della sequenza.

Se il lettore avrà la pazienza di eseguire passo dopo passo, in modo meccanico, le istruzioni del programma proposto, potrà appunto verificare che viene calcolato il valore desiderato (tre, per questa istanza). Si suggerisce anche di provare l’esecuzione del programma con altre sequenze di valori in ingresso, così da convincersi del fatto che esso risolve in modo completamente meccanico qualunque istanza del problema considerato.

Rimane un ultimo aspetto da discutere. Come fa l’automa a “capire” cosa vuol dire, per esempio, l’istruzione “Incrementa X” o le altre istruzioni? Come abbiamo visto per l’istruzione “Vai X”, il suo significato è dato dalle azioni che il progettista dell’automa stesso ha associato all’istruzione data. Nel caso di “Vai X” il suo “significato” è quindi dato dal fatto che quando essa viene incontrata nel corpo del programma il valore di X viene scritto dentro IC. A questo scopo, in effetti, non c’è bisogno che nel programma ci sia scritto “Vai X”, basta scrivere un breve codice numerico, ad esempio 10, e far sì che questo, quando viene “eseguito”, attivi i meccanismi fisici (normalmente, circuiti elettronici) che realizzano il comportamento desiderato. Seguendo questa linea si ottiene un programma scritto interamente in codifica binaria: è il livello cosiddetto del linguaggio macchina, cioè quel linguaggio che la macchina fisica, cioè la realizzazione fisica dell’esecutore è, con buona approssimazione, in grado di comprendere ed eseguire direttamente. Si può pensare, per fare un’analogia meccanica, che sia il livello al quale agiscono le leve e ruote dentate di un oggetto meccanico. Il programma presentato inizialmente è invece al livello cosiddetto del linguaggio simbolico.

Per ora accenniamo soltanto che il passaggio da un programma scritto in un linguaggio simbolico alla sua versione in linguaggio macchina può, e questo non dovrebbe sorprenderci, essere eseguito in modo del tutto meccanico da parte di appositi programmi di traduzione, che discuteremo più avanti, quando riprenderemo questo discorso parlando di virtualizzazione.

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

Strolling through informatics #4 – How a computer works

previous #3 ––– next #5

by Enrico Nardelli

(versione italiana qua)

In this post we continue the discussion about automata, that is, the mechanical executors of computations, an abstract model of our computers. As we saw in the previous post, a finite state automaton does not possess all the computational power we need. For this purpose, a more powerful executor is necessary, and the universal Turing machine (UTM), a formal model of an automaton defined by the English mathematician Alan Turing in 1936, is exactly what we need. Its author showed that it is capable of computing everything that we human beings consider computable. It's important to pay attention to the fact that this statement is not a mathematical theorem: it's indeed called "Turing's thesis" and not "Turing's theorem" precisely because there is no mathematically precise definition of "computability" that is independent of the executor used. However, it has proven to be a robust approach, because other formal models of mechanical executors have led to the same results.

Presenting the UTM would require excessive complications for our purposes, so I'm presenting a more easily understandable version that has the same computational power, the register machine (RM), in the minimal version we need to understand its operating principles. The computers we use every day, including those embedded within more or less smart devices that are increasingly becoming part of our lives, are all examples of RMs, technologically very sophisticated, but with the same computational power.

The RM has the components illustrated in the figure below and described as follows:

• A first series of memory cells, each of which has a numerical address, which is a positive integer, and is capable of containing an instruction in the language that the machine is able to execute. The set of instructions that are found in the memory cells at a certain moment constitutes the program that the machine is executing.
• A second series of memory cells, called registers, which contain the data. These cells also have a numerical address consisting of a positive integer and we assume that the data contained in them are only non-negative integers.
• A particular register (with a predetermined address that we indicate with the symbolic name IC) that contains the Current Address of the next instruction to be executed.
• A Control Unit (CU) that directs the general functioning of the machine.
• An Arithmetic-Logic Unit (ALU) that performs basic arithmetic and logical computations.

What we have just described is therefore the structure (or architecture) of the RM, also called "von Neumann architecture," after the mathematician of Hungarian origin John von Neumann who proposed it in 1945. In our description we disregard the interaction between the RM and the external world, which occurs through input and output devices, fundamental for its actual use, but negligible for the purposes of this presentation. We observe that we have distinguished the memory cells that contain the program and those that contain the data only for conceptual simplicity. In reality this distinction does not exist, generally speaking, and it is the basis of that duality between data and programs that represents one of the most important cultural achievements of informatics.

The behavior of the RM is determined by the CU, which executes what is described by the finite state automaton in the figure below.

In other words, the register machine has an "engine" (that is, the CU) that always repeats the same two simple actions: read the instruction present in the memory cell whose address is the symbolic name IC and execute it. In what follows, we will more simply use "IC" to indicate "the memory cell whose address is the symbolic name IC," as already done in the figure above.

The first question that comes to mind reflecting on this behavior is: since the content of IC is incremented by 1 each time, how can the machine do anything other than execute a simple sequential list of instructions? The answer is that one of the RM's instructions is capable of writing into IC a value determined by whoever created the program, so that the instruction executed after the current one is no longer the one at the address immediately following it but any other one.

The second question is: who actually performs the calculations that are needed? The answer is that the elementary steps that are necessary are carried out by the ALU, which needs, ultimately, to know how to perform, of all mathematical operations, only addition. Without going into complicated technical details, we recall in fact that subtraction can be reduced to addition, multiplication and division can be reduced to the repetition of, respectively, additions and subtractions. Other mathematical operations can be obtained starting from the four arithmetic operations. In the same way every logical operation can be obtained starting from just one. Appropriate programs allow, by repeating in suitable combination the elementary steps that the ALU is capable of performing, to execute all the calculations we need.

In the next post we will see how to give instructions to the RM, that is, what is the language that the RM is able to "understand," and a program for the RM that solves the problem stated at the end of the previous post (that is, counting how many "2"s there are in a sequence).

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

A passeggio con l'informatica #4 – Come funziona un computer

precedente #3 ––– successivo #5

di Enrico Nardelli

In questo post proseguiamo il discorso sugli automi, cioè gli esecutori meccanici delle elaborazioni, modello astratto dei nostri computer. Come visto nel precedente post, un automa a stati finiti non possiede tutto il potere computazionale che ci serve. A questo scopo è necessario un esecutore più potente e la macchina universale di Turing (MUT), un modello formale di un automa definito dal matematico inglese Alan Turing nel 1936, è quello che fa al caso nostro. Il suo autore ha evidenziato che essa è in grado di calcolare tutto ciò che noi esseri umani riteniamo calcolabile. È importante fare attenzione al fatto che questa affermazione non è un teorema matematico: si chiama infatti “tesi di Turing” e non “teorema di Turing” proprio perché non esiste una definizione matematicamente precisa di “calcolabilità” che sia indipendente dall’esecutore usato. Si è visto però che è un approccio robusto, perché altri modelli formali di esecutori meccanici hanno portato agli stessi risultati.

L’esposizione della MUT richiederebbe complicazioni eccessive per i nostri scopi, per cui presento una sua versione più facilmente comprensibile che ha lo stesso potere computazionale, la macchina a registri (MR), nella versione minimale che ci serve per capirne i princìpi di funzionamento. I computer che usiamo ogni giorno, anche quelli annidati all’interno dei dispositivi più o meno smart che sempre di più fanno parte della nostra vista, sono tutti esempi di MR, tecnologicamente molto sofisticati, ma con il suo stesso potere computazionale.

La MR ha le componenti illustrate nella figura sotto e descritte nel seguito:

• Una prima serie di celle di memoria, ognuna delle quali ha un indirizzo numerico, che è un intero positivo, ed è in grado di contenere un'istruzione del linguaggio che la macchina è in grado di eseguire. L’insieme delle istruzioni che in un certo momento si trovano nelle celle di memoria costituisce il programma che la macchina sta eseguendo.
• Una seconda serie di celle di memoria, dette registri, che contengono i dati. Anche queste celle hanno un indirizzo numerico costituito da un intero positivo e assumiamo che i dati contenuti in esse siano soltanto interi non negativi.
• Un registro particolare (di indirizzo prefissato che indichiamo con il nome simbolico IC) che contiene l'Indirizzo Corrente della prossima istruzione da eseguire.
• Un’Unità di Controllo (UC) che dirige il funzionamento generale della macchina.
• Un’Unità Aritmetico-Logica (UAL) che esegue le computazioni aritmetiche e logiche di base.

Quella appena descritta è quindi la struttura (o architettura) della MR, chiamata anche “architettura di von Neumann”, dal nome del matematico di origine ungherese John von Neumann che la propose nel 1945. Nella nostra descrizione prescindiamo dall’interazione tra la MR e il mondo esterno, che avviene tramite i dispositivi di ingresso e uscita (input e output), fondamentali per il suo effettivo utilizzo, ma trascurabili ai fini di questa presentazione. Osserviamo che abbiamo distinto le celle di memoria che contengono il programma e quelle che contengono i dati solo per semplicità concettuale. In realtà questa distinzione non esiste, in linea generale, ed è alla base di quella dualità tra dati e programmi che rappresenta una delle conquiste culturali più importanti dell’informatica.

Il comportamento della MR è determinato dalla UC, che esegue quanto descritto dall’automa a stati finiti della figura sotto.

In altre parole, la macchina a registri ha un “motore” (cioè la UC) che ripete sempre le stesse due semplici azioni: leggere l’istruzione presente nella cella di memoria il cui indirizzo è il nome simbolico IC ed eseguirla. Nel seguito, useremo più semplicemente “IC” per indicare “la cella di memoria il cui indirizzo è il nome simbolico IC”, come già fatto nella figura sopra.

La prima domanda che viene in mente riflettendo su questo comportamento è: dal momento che il contenuto di IC viene incrementato ogni volta di 1, come può la macchina fare qualcosa di diverso dall’eseguire una semplice lista sequenziale di istruzioni? La risposta è che una delle istruzioni della MR è in grado di scrivere dentro IC un valore determinato da chi ha realizzato il programma, in modo tale che l’istruzione eseguita dopo quella corrente non sia più quella di indirizzo immediatamente successivo ad essa ma una qualunque altra.

La seconda domanda è: chi effettua davvero i calcoli che servono? La risposta è che i passi elementari che sono necessari vengono svolti dalla UAL, la quale ha bisogno, in ultima analisi, di saper fare, di tutte le operazioni matematiche, solo l’addizione. Senza entrare in dettagli tecnici complicati, ricordiamo infatti che la sottrazione può essere ricondotta all’addizione, la moltiplicazione e la divisione possono essere ricondotte alla ripetizione di, rispettivamente, addizioni e sottrazioni. Altre operazioni matematiche possono essere ottenute a partire dalle quattro operazioni aritmetiche. Allo stesso modo ogni operazione logica può essere ottenuta a partire da una sola. Opportuni programmi consentono, ripetendo in opportuna combinazione i passi elementari che è in grado di svolgere la UAL, di eseguire tutti i calcoli di cui abbiamo bisogno.

Nel post successivo vedremo come si fa a dare le istruzioni alla MR, ovvero qual è il linguaggio che la MR è in grado di “comprendere”, e un programma per la MR che risolve il problema enunciato alla fine del precedente post (cioè contare quanti “2” ci sono in una sequenza).

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

Strolling through informatics #3 – Automaton and language

previous #2 ––– next #4

by Enrico Nardelli

(versione italiana qua)

In the previous post (Representing data) we talked about how to represent data. Once the representation has been established, we need to specify the sequence of instructions that we want the automaton (or executor or agent) to perform mechanically in order to execute the desired computation. What is an automaton? The term comes from Greek and is the root of words like "automatic" and "automatism" which indicate precisely what is executed without reflection, without consciousness and without the possibility of deviating from the traced path. Just as digital representation per se is not a recent phenomenon, neither is automation. We recall mechanical automata, which in the West were extensively studied in the Hellenistic age, covering approximately the last three centuries before Christ. For many centuries humanity has been able to build machines to automatically perform calculations (called "calculating machines") and those for automating arithmetic calculations have been developed with some regularity at least since the seventeenth century.

In order to define the sequence of instructions (also called a procedure or program) to be executed by the automaton, we must however know what specific instructions it is capable of executing, that is, the specific operations it is able to perform. A fundamental aspect to keep in mind is that these are strictly tied to the nature of the executor itself. Here then defining the reference automaton for computations, that is specifying the set of instructions that such an agent is capable of executing and illustrating exactly what operations are performed to execute them and clarifying in every detail how this can be achieved mechanically, is a preliminary step to the implementation of any process for processing representations. Such a definition must be carried out together with the definition of the language, called a programming language, which will then be used to describe, from time to time, the specific computations that the executor will have to implement. It can therefore be said that the definition of the automaton and its programming language are two sides of the same coin: it makes no sense to equip an automaton with an operation if there is no instruction in the related language that is capable of invoking it and – symmetrically – it makes no sense to insert into the language an instruction that the automaton is not capable of executing.

The precise characterization of what constitutes an automaton is a fundamental aspect of informatics, on which research has not yet completed its investigations. It must also be added that not all automata are equal, that is, they do not all have the same "computational power." In other words, they are not all capable of performing the same computations. However, it should be clarified immediately that all electronic computers actually used today are based on an automaton model that is the most powerful definable.

A very simple type of automaton is the finite state automaton, which can perform computations by "remembering" what happened in the past. This memory of the past is called "state" and constitutes a rather intuitive concept.

Here is an example that is capable of executing addition between binary numbers. Let us briefly recall that in binary representation numbers are written using only the two digits "0" and "1" (hence the adjective "binary").

A digit in the least significant position (the first from the right) directly represents one of the two possible values "zero" or "one".

The value represented by a digit in the second position from the right is obtained by multiplying the digit by two, or by the number of possible values represented by the digit to its right.

The value represented by a digit in the third position from the right must be multiplied by four, or by the number of possible values represented by the two digits in the two positions to its right. Proceeding this way we arrive, for example, at representing the number written in decimal as "20" with the binary representation "10100", since 1∙16 + 0∙8 + 1∙4 + 0∙2 + 0∙1 = 20.

Addition in binary works analogously to that in decimal except that, in binary, when adding two digits we reach (or exceed) two, then "we write 0 (or 1) with carry 1". The table represents what happens by indicating all possible situations of digits to be added with or without carry.

We can now define a finite state automaton that is capable of adding binary numbers of any length. For simplicity we assume they are represented with the same number of digits. We provide the automaton with binary numbers one digit at a time, in pairs, one digit for each of the two numbers, starting from the rightmost pair of digits. Each pair of digits provided as input (the pair written on the arcs in the figure below) causes the transition from one state to another represented by the arrow on which the pair appears (states are represented by circles and the "state transition" can also occur from the state to itself) and produces as output a digit of the result (written on the arcs after the bar). State R0 represents the situation in which the previous addition of two digits produced a carry of 0 and state R1 represents the symmetric situation with a carry of 1. The automaton, represented in the figure below, starts in state R0, since at the beginning of the addition there is no carry. The 4 arrows exiting from R0 represent the 4 state transitions determined by the 4 possible pairs of input digits, of which only one determines a real change of state from R0 to R1. Once the state transition corresponding to the input pair has been made, this is eliminated and the next pair is considered. When there are no more input pairs the addition is finished and all digits of the result have been produced as output.

If the reader has the patience to use this automaton to perform the sum between the two binary numbers 0101 (that is seven) and 0011 (that is three) they will see that with it the result 1010 (that is ten) is calculated automatically, mechanically.

However, there are cases in which the finite state automaton is not capable of producing a result, or rather does not have sufficient computational power. A simple example of a class of problems of this type is one in which the automaton can receive an arbitrarily long sequence of digits, in which only "1" or "2" appear, using "0" to indicate that the sequence is finished, and in which it is necessary to count how many "2"s are present in the specific sequence that arrived. Since we cannot know a priori how many "2"s the specific example will contain, we cannot build the automaton that is capable of solving any instance of a problem of this class.

We will see in the next post a type of automaton that is the most general and powerful possible and that is the basis of all the informatics devices (PCs, tablets, smartphones) that we use. We can therefore rest assured that all our informatics devices are sufficiently powerful from a computational point of view, even if they may be more or less fast from a technological 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 9 October 2024.

A passeggio con l'informatica #3 – Automa e linguaggio

precedente #2 ––– successivo #4

di Enrico Nardelli

Nel post precedente abbiamo parlato di come rappresentare i dati. Una volta stabilita la rappresentazione va specificata la sequenza di istruzioni che vogliamo far compiere meccanicamente all’automa (o esecutore o agente) per eseguire l’elaborazione desiderata. Cos’è l’automa? Il termine è preso dalla lingua greca ed è la radice di termini quali “automatico” e “automatismo” che indicano appunto ciò che viene eseguito senza riflessione, senza coscienza e senza possibilità di deviare dalla strada tracciata. Come la rappresentazione digitale in sé non è un fatto recente, così non lo è l’automazione. Ricordiamo gli automi meccanici, che in Occidente sono stati ampiamenti studiati nell’età ellenistica, che copre approssimativamente gli ultimi trecento anni prima di Cristo. Da molti secoli l’umanità è in grado di costruire macchine per fare automaticamente dei calcoli (dette “macchine calcolatrici”) e quelle per automatizzare i calcoli aritmetici sono state sviluppate con una certa regolarità almeno a partire dal Seicento.

Per poter definire la sequenza di istruzioni (chiamata anche procedura o programma) da far eseguire all’automa dobbiamo però sapere quali sono le specifiche istruzioni che esso è in grado di eseguire, cioè le specifiche operazioni che è in grado di compiere. Un aspetto fondamentale da tener presente è che esse sono strettamente legate alla natura dell’esecutore stesso. Ecco quindi che definire l’automa di riferimento per le elaborazioni, cioè specificare l’insieme delle istruzioni che tale agente è in grado di eseguire e illustrare esattamente quali operazioni vengono compiute per eseguirle e chiarire in ogni dettaglio come questo possa essere ottenuto meccanicamente, è un passo preliminare alla concretizzazione di ogni processo di elaborazione delle rappresentazioni.

Tale definizione va effettuata insieme alla definizione del linguaggio, chiamato linguaggio di programmazione, che verrà poi usato per descrivere, di volta in volta, le specifiche elaborazioni che l’esecutore dovrà attuare. Si può quindi dire che la definizione dell’automa e del suo linguaggio di programmazione sono due lati della stessa medaglia: non ha senso dotare un automa di un’operazione se non c’è un’istruzione nel relativo linguaggio che è in grado di invocarla e – simmetricamente –non ha senso inserire nel linguaggio un’istruzione che l’automa non è in grado di eseguire.

La caratterizzazione precisa di cosa costituisce un automa è un aspetto fondamentale dell’informatica, su cui la ricerca non ha ancora terminato le proprie indagini. Bisogna inoltre aggiungere che non tutti gli automi sono uguali, cioè non hanno tutti lo stesso “potere computazionale”. In altre parole non sono tutti in grado di effettuare le stesse elaborazioni. Va però chiarito subito che tutti i calcolatori elettronici oggi effettivamente usati sono basati su un modello di automa che è il più potente definibile.

Un automa di tipo molto semplice è l’automa a stati finiti, che può realizzare computazioni “ricordando” cosa è successo in passato. Questa memoria del passato si chiama “stato” e costituisce un concetto abbastanza intuitivo.

Ecco un esempio che è in grado di eseguire l’addizione tra numeri binari. Ricordiamo brevemente che nella rappresentazione in binario i numeri sono scritti utilizzando solo le due cifre “0” e “1” (da cui l’aggettivo “binario”).

Una cifra nella posizione meno significativa (la prima da destra) rappresenta direttamente uno dei due possibili valori “zero” o “uno”.

Il valore rappresentato da una cifra nella seconda posizione da destra si ottiene moltiplicando la cifra per due, ovvero per il numero di possibili valori rappresentati dalla cifra alla sua destra.

Il valore rappresentato da una cifra nella terza posizione da destra deve essere moltiplicato per quattro, ovvero per il numero di possibili valori rappresentati dalle due cifre nelle due posizioni alla sua destra. Così facendo si arriva, per esempio, a rappresentare il numero scritto in decimale come “20” con la rappresentazione binaria “10100”, dal momento che 1∙16 + 0∙8 + 1∙4 + 0∙2 + 0∙1 = 20.

L’addizione in binario funziona analogamente a quella in decimale tranne che, in binario, quando sommando due cifre si raggiunge (o si supera) il due, allora “si scrive 0 (oppure 1) con riporto 1”. Nella tabella viene rappresentato quello che avviene indicando tutte le possibili situazioni di cifre da sommare e con presenza o meno del riporto.

Possiamo adesso definire un automa a stati finiti che è in grado di sommare numeri binari di qualunque lunghezza. Per semplicità assumiamo che siano rappresentati con lo stesso numero di cifre. Forniamo all’automa i numeri binari una cifra per volta, in coppia, una cifra per ognuno dei due numeri, a partire dalla coppia di cifre più a destra. Ogni coppia di cifre fornite in ingresso (la coppia scritta sugli archi nella figura sotto) causa il passaggio da uno stato a un altro rappresentato dalla freccia su cui la coppia compare (gli stati sono rappresentati da cerchi e il “passaggio di stato” può avvenire anche dallo stato verso sé stesso) e produce in uscita una cifra del risultato (scritta sugli archi dopo la barra). Lo stato R0 rappresenta la situazione in cui la precedente addizione di due cifre ha prodotto un riporto di 0 e lo stato R1 rappresenta la situazione simmetrica con un riporto di 1. L’automa, rappresentato nella figura sotto, inizia nello stato R0, dal momento che all’inizio dell’addizione non c’è alcun riporto. Le 4 frecce uscenti da R0 rappresentano i 4 passaggi di stato determinati dalle 4 possibili coppie di cifre in ingresso, di cui uno solo determina un reale cambiamento dello stato da R0 a R1. Una volta effettuato il passaggio di stato corrispondente alla coppia in ingresso, questa viene eliminata e si prende in considerazione la coppia successiva. Quando non vi sono più coppie in ingresso l’addizione è terminata e sono state prodotte in uscita tutte le cifre del risultato.

Se il lettore avrà la pazienza di usare tale automa per effettuare la somma tra i due numeri binari 0101 (cioè sette) e 0011 (cioè tre) vedrà che con esso si calcola automaticamente, meccanicamente il risultato 1010 (cioè dieci).

Esistono però dei casi nei quali l’automa a stati finiti non è in grado di produrre un risultato, ovvero non ha un sufficiente potere computazionale. Un esempio semplice di una classe di problemi di questo genere è quella in cui l’automa può ricevere una sequenza arbitrariamente lunga di cifre, in cui appaiono solo “1” o “2”, usando “0” per indicare che la sequenza è finita, e in cui è necessario contare quanti “2” sono presenti nella specifica sequenza che è arrivata. Poiché non possiamo sapere a priori quanti “2” conterrà lo specifico esempio, non possiamo costruire l’automa che sia in grado risolvere qualunque istanza di un problema di questa classe.

Vedremo nella prossima puntata un tipo di automa che è il più generale e potente possibile e che è alla base di tutti i dispositivi informatici (PC, tablet, smartphone) che usiamo. Possiamo dunque star tranquilli che tutti i nostri dispositivi informatici sono sufficientemente potenti da un punto di vista computazionale, anche se possono essere più o meno veloci da un punto di vista tecnologico.

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

Strolling through informatics #2 – Representing data

previous #1 ––– next #3

by Enrico Nardelli

(versione italiana qua)

In informatics we often speak – improperly – of information processing. From a formal standpoint, however, the term information denotes data whose acquisition by a receiver determines a reduction in their uncertainty regarding some phenomenon. A typical example might be the percentage of votes obtained by a party in an election, which is still data, but constitutes information only if the recipient is not already aware of it. Data constitutes a single bit of information, that is, it has a unit informational value, if it reduces binary uncertainty in the receiver (that is, the uncertainty about whether something is true or false). In this regard, I should mention that in informatics the term "bit" derives from the contraction of the English expression binary digit and is used to indicate the representation of a binary value, that is, for example, true or false, using the two digits 0 and 1.

Since in informatics the perspective is not the reduction of uncertainty for those who receive the data, but rather the automaton that processes them mechanically, it is appropriate to always use the term "data" instead of "information" in an informatics context and – if we want maximum rigor – to speak of "representations," since data must necessarily be encoded in some way so that they can be processed by the automaton.

The datum in fact exists, even if abstract, independently of any material representation that might concretize it, which is chosen by us. This is clearly understood with numbers, concepts that do not have physical reality in themselves. The number "five" (that is, that number which in decimal base encoding we write as "5"), for example, is the concept that corresponds to how many objects there are in every set made of five objects, that is, the abstraction that represents what is common to all sets of five objects. The number "five" therefore exists in the world of abstractions, and it is I who can choose to represent it concretely through bits (101), with the alphabet (five), or with other encodings. An alternative term to representation is in fact "encoding," and we can consider them synonymous.

Let us also observe that, while the meaning of numbers can be formalized without too much difficulty, for most words this objective is extremely elusive because it involves interpretation by the receiver. This is true within the same language, but even more so between different languages, an aspect that constitutes one of the major difficulties of translation. Consider, for example, that "casa" corresponds in English to both house and home. The string "casa" is a representation, that is, data expressed in a material form, which for human beings is a symbol of (that is, a sign that refers to) a "meaning" that is uniquely determined only within a certain linguistic community. For example, the string "camera" has the meaning of "room" for Italian but "photographic camera" for English. When we speak of informatics in relation to computers (we will use this term or the equivalent English "computer" interchangeably) we use the term "representations" and not "symbols" because, even though from the human point of view those representations are indeed symbols of something meaningful, for the automaton they have no meaning, nor do their elaborations possess meaning – for the automaton.

Representations can be classified into two broad categories: analog and digital. The first is the one that, until a few decades ago, was the most used in human history. A typical example is the position of hands on a dial or the length of a shadow to indicate the time of day. The second – based on which for the same example time is represented through digits – now characterizes contemporary society, which for this very reason is called "digital society." In analog representation there is a proportion, an analogy. The more the hand has moved from its initial position or the longer the shadow is, the greater the time that has passed. In digital representation there are a series of arbitrarily chosen signs, digits, to which we assign a value. Let us observe, however, that the representation of quantities through digits has been used by humanity for millennia: the Babylonians used it for calculating astronomical orbits and the Egyptians used it for calculating land areas. Every population represented quantities with their own set of signs. The "digital" is therefore not a modern phenomenon.

Even the mechanical and automatic processing of representations can be realized in analog or digital mode. The first mechanical arithmetic calculators performed additions and subtractions through movements of rods or wheels, that is, with analog manipulation of analog data. Modern computers, instead, process digital representations digitally, that is, those consisting of digits. In this case the sum of two values, for example, is not the total length of two rods (each of which represents a value) placed in a row, but is the result of the addition between two numbers each of which is the digital representation of the number. The ten digits of our representation system (called precisely the "decimal system") are replaced, within computers, by a binary system (that is, one that uses only the two values "zero" and "one") for simple technological convenience. For a modern computer based on electricity, having only two values to represent constitutes a tremendous simplification, which leads to obtaining smaller and faster computing devices. Computers therefore adopt binary encoding for the representation of values.

Let us complete this section by observing that alphabetic characters can also be represented through binary encoding, progressively associating a binary representation to the various letters. This is what was done with the famous ASCII code (the universal standard for the binary representation of alphabet characters) which encodes the letter 'A' with the binary representation '01000001', corresponding to the decimal number '65', the letter 'B' with '01000010', corresponding to '66' and so on. Proceeding in a similar way, methods can be defined for constructing binary representations of images, sounds and videos. An in-depth study on data representation using the binary system can be found in the educational guide of the "Programma il Futuro" project available at this link https://programmailfuturo.it/come/cittadinanza-digitale/come-funzionano-i-computer/dati-e-sistema-binario

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

A passeggio con l'informatica #2 – La rappresentazione dei dati

precedente #1 ––– successivo #3

di Enrico Nardelli

Nell’informatica si parla spesso – impropriamente – di elaborazione delle informazioni. Da un punto di vista formale il termine informazione denota però un dato la cui acquisizione da parte di un ricevente determina una riduzione della sua incertezza rispetto a un qualche fenomeno. Un esempio tipico può essere la percentuale dei voti ottenuti da un partito in un’elezione, che è comunque un dato, ma che costituisce un’informazione solo se chi la riceve non ne è a conoscenza. Un dato costituisce un singolo bit di informazione, cioè ha un valore informativo unitario, se riduce nel ricevente un’incertezza binaria (cioè l’incertezza se qualcosa sia vero o falso). A questo proposito ricordo che in informatica il termine “bit” deriva dalla contrazione dell’espressione inglese binary digit e si usa per indicare la rappresentazione di un valore binario, cioè, p.es., vero o falso, presente o assente, acceso o spento, mediante le due cifre 0 e 1.

Dal momento che nell’informatica il punto di vista non è la riduzione di incertezza di chi riceve i dati, ma l’automa che li elabora meccanicamente, è opportuno utilizzare in un contesto informatico sempre il termine “dati” invece di “informazioni” e – se si vuole il massimo di rigore – parlare di “rappresentazioni”, poiché i dati devono necessariamente essere codificati in qualche modo affinché possano essere elaborati dall’automa.

Il dato infatti esiste, anche se astratto, indipendentemente da una sua rappresentazione materiale che eventualmente lo concretizza, che viene scelta da noi. Questo si capisce bene con i numeri, concetti che non hanno in sé una realtà fisica. Il numero “cinque” (cioè quel numero che nella codifica in base decimale scriviamo come “5”), ad esempio, è il concetto che corrisponde a quanti oggetti ci sono in ogni insieme fatto da cinque oggetti, cioè l’astrazione che rappresenta ciò che è comune a tutti gli insiemi di cinque oggetti. Il numero “cinque” quindi esiste nel mondo delle astrazioni, e sono io che posso scegliere di rappresentarlo concretamente mediante bit (101), con l’alfabeto (cinque), o con altre codifiche. Un termine alternativo a rappresentazione è infatti “codifica”, e possiamo considerarli sinonimi.

Osserviamo ancora che, mentre il significato dei numeri è formalizzabile senza troppa difficoltà, per la maggior parte delle parole questo obiettivo è estremamente sfuggevole perché coinvolge l’interpretazione da parte del ricevente. Questo è vero all’interno dello stesso linguaggio, ma ancora di più tra linguaggi diversi, aspetto che costituisce una delle maggiori difficoltà della traduzione. Si pensi, ad esempio, che “casa” corrisponde in inglese sia a house che a home. La stringa “casa” è una rappresentazione, cioè un dato espresso in una forma materiale, che per gli esseri umani è simbolo di (cioè, un segno che si riferisce a) un “significato” che è univocamente determinato solo all’interno di una certa comunità linguistica. Ad esempio, la stringa “camera” ha significato di “stanza” per l’italiano ma di “macchina fotografica” per l’inglese. Quando parliamo di informatica in relazione ai calcolatori (utilizzeremo indifferentemente questo termine o l’equivalente inglese “computer”) usiamo il termine “rappresentazioni” e non “simboli” perché, anche se dal punto di vista umano quelle rappresentazioni sono appunto simbolo di qualcosa di significativo, per l’automa esse non hanno alcun significato, né posseggono un significato – per l’automa – le loro elaborazioni.

Le rappresentazioni possono essere classificate in due grandi categorie: analogica e digitale. La prima è quella che, fino a qualche decennio fa, è stata la più usata nella storia dell’umanità. L’esempio tipico è la posizione delle lancette in un quadrante o la lunghezza di un’ombra per indicare l’ora del giorno. La seconda – in base alla quale per lo stesso esempio il tempo viene rappresentato mediante cifre – caratterizza ormai la società contemporanea, che proprio per questo viene denominata “società digitale”. Nella rappresentazione analogica c’è una proporzione, un’analogia. Quanto più la lancetta si è mossa dalla sua posizione iniziale o quanto più l’ombra è lunga, tanto maggiore è il tempo trascorso. Nella rappresentazione digitale ci sono una serie di segni arbitrariamente scelti, le cifre, ai quali assegniamo un valore. Osserviamo però che la rappresentazione delle quantità mediante cifre è stata utilizzata dall’umanità da millenni: l’usavano i Babilonesi per il calcolo delle orbite astronomiche e l’usavano gli Egizi per il calcolo delle superfici dei terreni. Ogni popolazione rappresentava le quantità col proprio insieme di segni. Il “digitale” non è quindi un fenomeno moderno.

Anche l’elaborazione meccanica e automatica delle rappresentazioni può essere realizzata in modo analogico oppure digitale. Le prime calcolatrici aritmetiche meccaniche eseguivano somme e sottrazioni mediante spostamenti di aste o ruote, cioè con una manipolazione analogica di dati analogici. I moderni computer, invece, elaborano in modo digitale rappresentazioni digitali, cioè costituite da cifre. In tal caso la somma di due valori, ad esempio, non è la lunghezza totale delle due aste (ognuna delle quali rappresenta un valore) messe in fila, ma è il risultato dell’addizione tra i due numeri ognuno dei quali è la rappresentazione digitale del numero. Le dieci cifre del nostro sistema di rappresentazione (denominato appunto “sistema decimale”) sono sostituite, all’interno dei computer, da un sistema binario (cioè che utilizza solo i due valori “zero” e “uno”) per semplice convenienza tecnologica. Per un moderno calcolatore basato sull’elettricità avere due soli valori da rappresentare costituisce una notevolissima semplificazione, che porta a ottenere dispositivi di calcolo più piccoli e più veloci. I calcolatori adottano quindi una codifica binaria per la rappresentazione dei valori.

Completiamo questo post osservando che anche i caratteri alfabetici possono essere rappresentati mediante una codifica binaria, associando progressivamente alle varie lettere una rappresentazione binaria. È quello che è stato fatto con il famoso codice ASCII (lo standard universale per la rappresentazione binaria dei caratteri dell’alfabeto) che codifica la lettera ‘A’ con la rappresentazione binaria ‘01000001’, corrispondente al numero decimale ‘65’, la lettera ‘B’ con ‘01000010’, corrispondente a ‘66’ e così via. Procedendo in modo analogo, si possono definire metodi per costruire rappresentazioni binarie di immagini, suoni e video. Un approfondimento sulla rappresentazione dei dati mediante il sistema binario si trova nella guida didattica del progetto “Programma il Futuro” disponibile a questo link.

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