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.