beanz Magazine

Can Software Write Itself?

Dan Ruscoe on Flickr

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

Also In The December 2018 Issue

Create colourful geometric patterns in SketchUp inspired by the Great Mosque of Cordoba.

Learn how to use animated GIFs to create proper animation loops in Scratch.

Create an electronic obstacle course and test the steadiness of your hands as you navigate through.

What’s allowed in an e-mail address? Let’s break down the syntax.

Throwing your old tech in the trash is bad for the environment. Check out some safer, cleaner alternatives.

New, crafty mods that’ll push your Minecraft design skills to new levels.

Part philosophical paradox, part coding puzzle, quines are sure to tease and challenge your brain!

5 questions with the designer pushing innovation in 3D printed clothes.

All work and no play makes it harder for kids to learn, especially those with anxiety and learning disabilities.

Dive into the nuts & bolts of storing pictures and files on your computer.

A clever AI is creating twisted, surreal art. Math or magic?

Two doors hide a zonk, and one door hides a prize. Can probability & statistics help you pick the right one?

How can you tell if a credit card number is valid or invalid? Meet the Luhn algorithm, one of many checksums helping us keep the internet in order.

Learn about the Destination Dispatch algorithm and create your own robotic lift.

Grab your friends & disconnect from the digital world with these fun science & tech board games.

Interesting stories about computer science, software programming, and technology for December 2018.

Links from the bottom of all the December 2018 articles, collected in one place for you to print, share, or bookmark.