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.