Can a computer ever be considered alive? People have been fascinated with that question for as long as there’s been computers.
Many researchers and thinkers have directed a lot of this mental energy towards the question “can machines think like we do?”, and while that is an interesting question, we’re going to step down—or up depending how you draw it—the evolutionary tree and ask a far more basic one: can machines reproduce?
After all, the ability to make more of yourself is definitely one of the core features of the definition of “life”. You have to be able to make more of yourself in order for your species to evolve. Even single celled organisms can make more of themselves!
John von Neumann tackled this question from the hardware side of things, eventually designing a machine that could construct copies of itself. From our modern perspective that’s not too surprising. There are 3d printers that can print out the parts to build a new 3d printer, so you can imagine a robot crossed with a 3d printer that can not only print out its parts but has enough programming to put together the new copy out of the parts.
But life doesn’t just reproduce at the scale of organisms! The DNA in every cell has to replicate itself as well! Since DNA is often compared to the “program” that describes how to build a living creature, that leads us to a pretty sensible question: can software reproduce as well?
That’s what people like Douglas Hofstadter were thinking about some decades ago. Here’s the really simple version of “can software reproduce” that Hofstadter wrote about in his book “Goedel, Escher, Bach”: can you write a program that, when run, prints out its own source code?
Hofstadter called solutions to this problem “Quines”, after the philosopher Willard Van Orman Quine who—among many other topics—wrote about self-referential paradoxes. Things like “this statement is false” or “everything I say is a lie”!
While you only need a single example of a Quine to show that, yes, software can reproduce itself, Quines are still interesting today as coding puzzles! Lots of people test themselves to write clever Quines in every language they can think of.
It’s a fun challenge that’s a lot harder than it might seem! Let’s try to write a simple Quine in Python to show why it’s tricky. I’m following a path towards a Quine very similar to the Python Quine on the Quine wiki page.
To start you might want to try something like:
print("print(...)")
Here, we need to figure out what to put in place of the ellipses. The problem is that there isn’t anything obvious to insert there! We easily get stuck in an infinite expansion:
print("print(\"print(...)\")")
We’re always printing one fewer layer of print statements than we need to replicate the source code!
Let’s try adding a little misdirection by putting in a variable. What about something like:
str="str=...\nprint(str)" print(str)
It may look like we’ve just moved the problem to the definition of str instead of what goes inside the print statement. What we need is some kind of way to insert data into the string that will tie the knot we’re having trouble with. That’s just string interpolation, though! Finally, we can change our code to look like:
str="str=%r\nprint(str%%str)" print(str%str)
So what we’re doing here is making a “hole”, so to speak, in the string with %r which we fill in the print statement with the string itself. That’s the big punchline, here, that to make a Quine you need to be self-referential like the paradoxes Quine wrote about!
As a technical note, we use %r instead of %s to make the hole we want to fill in because %r keeps the string looking exactly like it did originally, including quotation marks and escaped characters. We also use %% to escape the % symbol that we don’t want to be a hole in str.
So that’s the basic idea of Quines with an example. Try writing them in whatever your favorite programming language is!
Learn More
A big collection of Quines
http://www.nyx.net/~gthompso/quine.htm
Another huge collection of Quines
http://rosettacode.org/wiki/Quine
If writing Quines is too easy
https://codegolf.stackexchange.com/questions/93324/write-a-palindrome-polyglot-quine
