The Limits of the Machine: Self-Reference and Programs That Rewrite Themselves

Code along video

Learning objectives

We have now implemented real algorithms in X-Toy, and we know that every program, in any language, ultimately runs as ones and zeros. This code along is the start of an epilogue on theory, in which we ask what the limits of such a machine are. We will meet three paradoxes of self-reference (the liar paradox, a museum that cannot decide what to hang on its wall, and Russell’s paradox), and then see that X-Toy programs can refer to themselves too: a one-line program that copies itself into a register, and a three-line program that lets its user overwrite it. We close with a quine, a program that prints its own source code, and the key point that a program is just a string.

Code along summary

Setup

This code along is mostly conceptual. We will run two tiny programs in Visual X-TOY, and one Python program that you can paste into any Python interpreter.

What are the limits of this machine?

Programming exists at many levels, but it will always exist at the level of ones and zeros. (Sure, we can talk about quantum computing, but the point is that a program always needs to be represented in some very basic form; a computer is an electrical machine.) In Visual X-TOY, the simulation is literally just flicking lights on and off. So if a computer is just flipping transistors on and off, how powerful are computers, really? That seems at odds with what we see in the current era, in which computers are getting more and more powerful.

Surprisingly, this question is closely related to one that you have probably had if you have ever implemented a function in one of our practice exercises: have you ever sat there watching your program run, not knowing whether it would ever stop? Maybe it is going to work, and it is just slow. Our idea for helping you would be to write an autograder that looks at your code and tests immediately whether your program will ever stop. This question is so foundational to computer science that Alan Turing was studying it in the 1930s. To see why it is hard, we first need to take a detour through some paradoxes.

The liar paradox

A 14th-century French philosopher, Jean Buridan, posed a quandary called Buridan’s bridge, which imagines a discussion between Socrates and Plato. Plato says: “Socrates, if in the first proposition which you utter, you speak the truth, I will permit you to cross this bridge. But surely, if you speak falsely, I shall throw you into the water.” Socrates breaks the arrangement by replying: “Plato, you will throw me into the water.”

Socrates’ reply is closely related to something that really is a paradox, the liar paradox:

This statement is false.

STOP: Is the sentence “This statement is false” true or false? Why?

If the sentence is true, then it asserts something true, namely that it is false, so it is false. But if the sentence is false, then what it says about itself is wrong, so it must be true. If it is true, it has to be false, and if it is false, it has to be true. This contradiction breaks basic logic.

Escher, Droste, and a museum paradox

M. C. Escher, the Dutch artist famous for staircases that always go up and waterfalls that flow back into themselves, said that of everything he ever made, his 1956 print Print Gallery was by far the most peculiar. It shows a man in an art gallery looking at a painting of a seaside town. The painting has a kaleidoscopic, spiraling effect: as we follow it around, we find that the town contains the gallery, and the man is looking at a picture that contains himself, looking at the picture, which itself contains the gallery, and so on. There is a great YouTube video showing what Escher was trying to do. This kind of infinite self-reference is also a central theme of Douglas Hofstadter’s Gödel, Escher, Bach, an underappreciated 800-page book that weaves together music, art, logic, and mathematics.

Escher was getting at an effect that is named for a famous Dutch brand of cocoa, Droste. For well over a century, its packaging has shown a woman holding a tray with a box of Droste cocoa on it, and on that box is the same woman holding the same tray. Artwork that contains a depiction of itself is said to have the Droste effect. So there are two types of paintings in the world: paintings that contain themselves, and paintings that do not.

Now imagine that there is a trillionaire (what a ludicrous idea) who loves art but hates Droste effect paintings. The trillionaire starts a museum that will hold every non-Droste painting in the world, from professional pieces down to children’s drawings, all in one huge open gallery. For the grand opening, an artist is commissioned to paint an accurate depiction of the gallery, with every piece on the wall.

STOP: Should the artist’s painting include itself? In other words, should it be Droste?

Suppose that the painting includes itself. Then it is a Droste painting, and the trillionaire hates those, so it cannot hang in the museum. But then it is not an accurate depiction of the gallery, since it shows itself on the wall. So suppose instead that the painting does not include itself. Then it is not Droste, so it belongs in the museum, and we hang it on the wall. But now the painting is again inaccurate, because it is on the wall and does not show itself. Either way, we come back around in a circle.

That may seem like a silly example, because it is one. But if we port it to set theory, it becomes Russell’s paradox (consider the set of all sets that do not contain themselves: does it contain itself?), which essentially brought mathematics to its knees in the early 20th century.

STOP: What do the liar paradox and the museum paradox have in common?

Both paradoxes rely on self-reference: art that is about itself, or a logical statement that comments on itself. Self-reference is not always bad (recursion is a kind of self-reference, and we have used it to great effect), but these paradoxes also share an “I am not” structure. If the trillionaire had loved Droste paintings and built a museum of all of them, the artist could paint the gallery including the painting itself and hang it on the wall, with no problem at all. Likewise, nobody has ever doubted the statement “This statement is true.”

An X-Toy program that refers to itself

It is probably not clear at all what any of this has to do with programming. But it has everything to do with programming, because we can make programs do some weird things. Here is a one-line X-Toy program.

10: 8410   R[4] <- M[10]
STOP: What does this one-line X-Toy program do?

If the word were 7410, it would set R[4] equal to the value 10, because opcode 7 is load address. But opcode 8 is load, which does something slightly different: it sets R[4] equal to whatever is stored at memory address 10. That seems harmless. But what is at memory address 10? It is 8410 itself. When we run this program, it does not crash; it executes its one line, and then it halts. But afterward, R[4] holds 8410.

R[4] = 8410

From one perspective, the program has just loaded a memory address into a register. From another, it has written the program into R[4]. It is as if line 10 says “write me into register 4.” It is referring to itself. We are not claiming that Visual X-TOY is an intelligent being, far from it; we are pointing out that even a one-line X-Toy program has a little bit of this weirdness. There are two directions we could go from here. One is to say that this is just a strange little curiosity, which is perfectly valid. The other is to say that it has an immense impact on the entire world of computing, and that is the direction that Alan Turing and Kurt Gödel went.

A program that its user can overwrite

Here is one more X-Toy program.

10: 84FF   read R[4]
11: 9412   M[12] <- R[4]
12: 94FF   write R[4]
STOP: What does this three-line X-Toy program do?

The simple answer is that it takes a value from standard input into R[4], stores that value at memory address 12 to remember it, and then prints it. That seems innocuous. Let us run it with the input 1410. We read the value, and R[4] becomes 1410. We store it at address 12, and we can see it appear there in memory. Then we try to print it to the console, and nothing happens.

Nothing happens because the value from the user overwrote the instruction at address 12, which was part of our program. We stored the user’s value at 12 to remember it, and all of a sudden, that value became a command in the program. What does 1410 do? It adds R[1] and R[0] and stores the result in R[4], setting R[4] equal to R[1], which was never part of the intended program. We have completely inadvertently given the user access to the program itself.

Note: In fact, this program never prints the value for almost any input, because every input replaces the 94FF at address 12 before it runs. An input whose first hex digit is 0, such as 0042, becomes a halt instruction. Only the input 94FF itself prints what we gave it.

We can make programs do weird stuff, but we can also protect against this one. The problem is that RAM stores both the program and the data that it manipulates, and if we mix them, some really weird behavior can happen. If we go back far enough in computing, separating them was not necessarily standard, but the Harvard architecture partitions the instructions that we follow from the data, so that anything a user provides stays apart from the program memory.

Slide titled We Can Make Programs Do Weird Stuff: Concern: RAM stores the program and data that you're manipulating. A diagram shows a control unit connected to an ALU, instruction memory, data memory, and I/O. Caption: Most modern computers implement Harvard architecture: partitions instructions and data.
Figure: In the Harvard architecture, instruction memory and data memory are separate. (Diagram courtesy of Nessa los, Wikimedia Commons.)

Quines

Even with that partition, weird behavior is still possible in general. Here is a Python program for you to try.

def main() -> None:
    q = 'def main() -> None:\n    q = %r\n    print(q %% q)\n\n\nif __name__ == "__main__":\n    main()'
    print(q % q)


if __name__ == "__main__":
    main()

Exercise: run the quine

Exercise: Paste this program into the sandbox or any Python interpreter and run it. What does it print?

It sure does not look like much, but this program is an example of a quine, a program that prints its own source code and exits. When we run it, it prints exactly the text of the program above. (This version differs from the one in the video only by the type hint -> None, and it still prints its own source exactly.) The trick is that the string q is a template for the whole program, with a placeholder %r where q itself should go; formatting q with itself fills in the placeholder with q, quotes and all. It is easier in some languages than others to see why a quine works, but quines exist in essentially every language.

Again, there are two paths. One is to say that a quine is a curiosity and no big deal. The other, the genius route, is to notice that a program in any programming language is just a string of characters. That is something we know from X-Toy: an assembly language programmer thinks of a program as ones and zeros, as lights switching on and off. When we program in Python, we probably do not think of the program itself as a long string, but it is one. The same is true of AI chatbots: when we use a tool like Claude Code, the program is the prompt that we give it, together with any past data, all lumped together into one huge string. At every level of programming, a program is just a long string of characters. If that is the case, how powerful can programs really be?

A crisis in mathematics

This question is inherently related to an existential crisis that mathematics had in the 1930s. The German mathematician David Hilbert was a kind of mathematical evangelist: he believed that mathematics was the central study of humanity, a perfect, paradox-free discipline that would answer every question that we could ever ask of it. That entire worldview was brought to its knees by one paper in the 1930s from Kurt Gödel.

We will not take the detour to discuss Gödel’s work, because it is immensely complicated; an entire course might be needed to get up to the point of understanding it. (If you are curious, Nagel and Newman’s short book Gödel’s Proof builds intuition for it in a couple hundred pages.) What we will do is follow another genius who noticed that Gödel had essentially hotwired mathematics to explode on itself through paradoxes of self-reference, and who wondered whether the same could be done to computing.

Looking ahead

That genius was Alan Turing. In the next and final code along of the chapter, we will meet his remarkably simple model of a computer, return to the magic autograder that tells us whether a program will ever stop, and use a self-referential program to show that no such autograder can exist.

Scroll to Top
Programming for Lovers banner no background
programming for lovers logo cropped

Join our community!