2017 : WHAT SCIENTIFIC TERM OR CONCEPT OUGHT TO BE MORE WIDELY KNOWN?

samuel_arbesman's picture
Complexity Scientist; Scientist in Residence at Lux Capital; Author, Overcomplicated
Quines

Within the infinite space of computer programs is a special subset of code: programs that, when executed, output that program itself. In other words, these are a kind of self-replicating program; when you run them, they yield themselves. These short programs are often referred to as quines, after the philosopher Willard Van Orman Quine, based on the term from Douglas Hofstadter’s Gödel, Escher, Bach: an Eternal Golden Braid.

Upon first hearing about quines, they often seem magical. And doubly so if you have ever done any coding, because without knowing the trick for how to create these, they might seem devilishly difficult to construct. They are often elegant little things, and there are now examples of quines in a huge number of computer languages. They can range from short and sweet ones to ones that are far more inscrutable to the untrained eye.

But why are they important? Quines are a distillation of numerous ideas from computer science, linguistics, and much more. On a simple level, quines can be thought of as a sort of fixed point, an idea from mathematics: the value of a mathematical function that yields itself unchanged (think along the lines of how the square root of 1 is still 1).

But we can take this further. Quines demonstrate that language, when refracted through the prism of computation, can be both operator and operand—the text of a quine is run, and through a process of feedback upon itself, yields the original code. Text can be both words with meaning and “words with meaning.” Think of the sentence “This sentence has five words.” We are delighted by this because the words are both describing (acting as an operator) and being described (acting as an operand). But this playfulness is also useful. This relationship between text and function is a building block of Kurt Gödel’s work on incompleteness in mathematics, which is in turn related to Alan Turing’s approach to the halting problem. These foundational ideas demonstrate certain limitations in both mathematics and computer science: There are certain statements we cannot prove to be either true or false within a given system, and there is no algorithm that can determine whether any given computer program will ever stop running.

More broadly, quines also demonstrate that reproduction is not the distinct domain of the biological. Just as a cell exploits the laws of physics and chemistry in order to persist and duplicate, a quine coopts the rules of a language of programming to persist when executed. While it doesn’t quite duplicate itself, there are similar principles at work. You can even see further hints of this biological nature in a “radiation hardened” quine: a type of quine where any character can be deleted, and it still will replicate! A radiation-hardened quine appears to look like gibberish, which is no doubt what the DNA sequence of a gene looks like to many of us. Redundancy and robustness, hallmarks of biology, yield similar structures in both the organic and the computational.

John von Neumann, one of the pioneers of computing, gave a great deal of thought to self-replication in machines, binding together biology and technology from the dawn of computation. We see this still in the humble quine, tiny snippets of computer code that by their very existence stitch domain after domain together.