Strolling through informatics #17 – Self-reproducing bits

previous #16 ––– next #18

by Enrico Nardelli

(versione italiana qua)

In the previous post (Data or programs? That is the problem) we discussed how, at the level of the programming language that the physical machine is able to execute directly through its electronic circuits, there is no intrinsic distinction between what constitutes an instruction and what constitutes data. Only the instructions of the Control Unit of the register machine, which are those placed inside the circles in the second figure of post #4 (How a computer works), are intrinsically instructions. What we commonly call a "program" (regardless of whether it is in symbolic language or machine language) is, at the directly executable physical level, simply a sequence of zero and one bits. This constitutes an advantage, because it allows us to process programs by treating them simply as data, but it can also constitute a weakness, if bit sequences that had been considered data are instead interpreted as instructions and executed. The latter is indeed the mechanism by which computer viruses spread: in the absence of appropriate countermeasures, they are transferred from one computer to another as if they were data and then executed.

This dual nature possessed by bit sequences, together with the fact that – precisely because of this duality – the same bit sequence can be interpreted in both ways and can therefore manipulate itself, gives informatics a power of reproduction whose only other existing manifestation in nature is that possessed by biological systems.

Let us illustrate this power of reproduction with a very simple automaton. I first describe its simple instruction repertoire and then present a program that, despite the simplicity of the automaton, is capable of reproducing itself.

The first instruction in the repertoire is an assignment instruction of the type

P=100;

which assigns the value 100 to P. We note that each instruction is terminated by a semicolon (;). This is just an example of using the instruction, another could be

Q=3;

which assigns the value 3 to Q. We then have a print instruction of the type

print P;

which, having executed the assignment instruction previously described, produces as a result

100

Clearly the instruction «print Q;» would instead have produced «3»: observe that in this case we have used double open angle brackets («) and closed ones (») to denote precisely in the body of the text the instructions we are talking about or their effect, while before we had presented them each isolated on a line.

The automaton also possesses a variant of this print instruction, namely

print "P";

whose execution no longer produces the printing of the value possibly assigned to P but produces as a result literally what is contained between the double quotes, that is

P

(similarly «print "Q";» would produce «Q»). We observe at this point that the print instruction can have multiple objects to print, as for example happens with

print P Q;

which produces

100    3

and with

print "P=" P;

which instead produces

P=100

Finally, the automaton possesses a repetition convention, according to which, for example

3|X;

constitutes an abbreviated way of representing

X; X; X;

We therefore have that the program (made up of two instructions which for simplicity we write on the same line)

P=3|X;      print P;

produces as output

X; X; X;

while the program

P=3|X;      print "P=" P;

produces as output

P=X; X; X;

We are ready at this point to present and discuss the program that replicates itself, which consists of these two instructions only, presented below on the same line

P=2|print "P=2|" P;      print "P=2|" P;

Let us determine what the automaton does when it executes this program. With the first instruction it assigns to P – based on the repetition convention described above – the value «print "P=2|" P; print "P=2|" P;». With the second instruction it produces as output the value «P=2|» followed by the value just assigned to P, that is

P=2|print "P=2|" P; print "P=2|" P;

The execution of the program has therefore produced as output an exact copy of itself! Note that the space between the two instructions in the first case (the program text) is greater than in the second (the result of its execution) only for typographical clarity reasons.

We have obtained a behavior that, at an abstract level, is exactly the same behavior that a DNA sequence realizes during replication, a key process for biological reproduction. In our case, we obtain the "reproduction of bits" and this aspect of informatics perhaps constitutes the most important of its conceptual contributions to the panorama of scientific culture.

[[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 29 January 2025.