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.