Gödel's Incompleteness Theorem, in Bash

Gödel’s first incompleteness theorem states that there are mathematical statements that can neither be proven or disproven. His proof is fairly difficult to understand - it involves prime numbers, factorization, all this number theory. Gödel’s proof had to be complicated because in 1931, computer algorithms hadn’t really been invented.

Turing machines would only be invented in 1936, five years later. When Turing proved the halting problem was undecidable - that there is no program that can decide whether another program will ever finish - Gödel’s work was an inspiration to him. Historically, Gödel clearly came before Turing. But in the modern day, for people who already understand the concept of a “computer program”, it’s a lot easier to understand the theory the other way around. Turing first, then Gödel.

Seeking Paradox In Bash

Many software engineers are aware that a program can run on other programs. For example:

$ wc ./my_program.sh

This elite “metaprogramming” technique uses the program wc to tell you how many lines of code there are in the my_program.sh script.

You can go even deeper into this running-programs-on-programs, and run a program on another program that’s running on another program. For example, if you want to know how long it takes to count the lines of code in my_program.sh:

$ time wc ./my_program.sh

Now imagine a script called behave_differently.sh. When you run it on another program, it outputs something different than that program does. For example:

$ ./behave_differently.sh ./my_program.sh ./my_input.txt

This can output anything at all, as long as it is different from the output of ./my_program.sh ./my_input.txt.

If we can just write behave_differently.sh, then we can write the script paradox.sh:

#!/bin/bash
./behave_differently.sh $1 $1

For any script, paradox.sh my_script.sh behaves differently than running my_script.sh my_script.sh. So what happens when you run ./paradox.sh ./paradox.sh? It’s a logical impossibility. It must be impossible to write behave_differently.sh.

Sanity Check

It doesn’t really seem impossible to behave differently than another script. What goes wrong with the naive approach?

#!/bin/bash
if [[ `$*` == "YES" ]]
then
  echo NO
else
  echo YES
fi

When you run ./paradox.sh ./paradox.sh, the script simply goes into an infinite loop, outputting nothing. You can check my work - the code is on GitHub. The reason it is so hard to behave differently from another script is that you can’t tell, when it goes into a long and silent loop, if that loop is really infinite or not.

The Halting Problem

If we had a script halts.sh that could tell if a program would halt, we could use it to write behaves_differently.sh.

#!/bin/bash
if [[ `./halts.sh $*` == "YES" ]]
then
  while true ; do continue ; done
fi

So it must be impossible to write halts.sh. There you go - that’s the impossibility of the halting problem, which Turing proved in 1936.

Proving an Infinite Loop

Once you see that the fundamental impossibility is writing behaves_differently.sh, it starts to make sense how you can generalize the halting problem a little bit.

Sometimes, you can prove a program goes into an infinite loop. A smart compiler can figure out that some areas of the code are unreachable. If all the parts of the program that exit are unreachable, then a program must go into an infinite loop.

You don’t need to understand all the details, here, you just need to know that it’s possible to build some tools around these proofs. You can represent these proofs in a .proof file format, and there’s a validation script that checks the proof. So when we run:

$ ./validate_proof.sh ./my_program.proof ./my_program.sh

If it returns YES, that means that ./my_program.sh goes into an infinite loop. If the proof isn’t valid, the validator returns NO. The validation script never goes into an infinite loop itself.

The other tool we need is a way to generate all possible files. It can be super slow, that’s fine. So let’s say that this generates a file by converting a big integer to its binary representation:

$ ./generate_file.sh <number>

Putting It All Together

We can try to behave differently from a target script by searching for a proof that it goes into an infinite loop.

#!/bin/bash
i=0
while true; do
  ./generate_file.sh $i > ./possible.proof
  if [[ `./validate_proof.sh ./possible.proof $*` == "YES" ]]
  then
    # The target goes into an infinite loop. Let's behave differently
	exit 0
  fi
  i=$(( i + 1 ))
done

If there is any proof of the target script going into an infinite loop, then this program will eventually find it, and stop. If there is no proof, then it will loop forever searching for a proof.

If every program that infinite loops has a proof that it infinite loops, then we have just written behave_differently.sh. We know that’s not possible. So, no matter what proof system we use, there must be some program that never terminates, but there is no proof that it never terminates. There must be true but unprovable statements, which is what Gödel proved in 1931.

Conclusion

Gödel’s incompleteness theorem is fundamental to the philosophy of mathematics. It demonstrates the mismatch between our ideas of truth and our ideas of proof. It shows us that there will always be a difference between the theoretical idea of truth and the practical set of mathematical statements that we know are true.

I hope that this exposition was helpful to people. Personally, I think we should set aside Gödel’s original number-theory-based proof as an artifact of history, the way we no longer use Isaac Newton’s original notation for calculus. We should accept that the concepts of mathematical proof and computer algorithms are intertwined at their heart, teach the halting problem first, and teach the incompleteness of mathematical proof second.

The Unreality of Pi

To me, there is a mystery at the heart of mathematics. Why does it work? Why does it tell us useful things about the world?

One philosophy is that mathematical truth is like Plato’s Forms, an abstract, perfect truth that exists outside of physical reality. You can think of mathematics as a type of language; it’s language with a convention that any possibility of error is completely forbidden. As Wittgenstein suggests, things we cannot speak of we must pass over in silence. Mathematical language cannot say anything about politics, about current events, about the precise nature of a real-world cannonball lofted through the air, because it’s possible that our observations about these things are mistaken. Burn all this away, and what is left is the mathematics.

This way of looking at mathematics is powerful, but it’s missing something. Think of the greatest drama of historical mathematics, the rise and fall of Euclidean geometry. For about two thousand years, Euclid’s Elements was the main textbook for teaching mathematics. Euclid started with a few axioms for geometry, and proved vast swaths of geometry from these axioms. The one aesthetically displeasing part was the fifth axiom - if you have points ABCD, and ABC and BCD are acute angles, then the rays BA and CD must intersect. In other words, the “parallel postulate” - that for every line and a point not on that line, you can only draw one parallel line through that point.

People thought this axiom was obvious for a long time, and it was only considered aesthetically displeasing that it was so much more complicated than the previous axioms. Mathematicians tried to prove it from the other axioms for a long time, but it turned out this was impossible.

In fact, this axiom is worse than aesthetically displeasing. This axiom is false. With the discovery of special relativity, scientists realized that space is not flat. It is curved. You can draw multiple parallel lines through a point. They just have to be really, really close to each other.

It’s worse than that. “Real numbers” are also not real. Quantum mechanics now tells us that the precision of a measurement is limited. But the rigorous definition of “real numbers” requires an infinite sequence of numbers getting closer and closer. The mathematics doesn’t work if small numbers are prevented from going smaller than the Planck length. A circle of radius 1 doesn’t really have an area of pi - it’s a little bit off.

Euclidean geometry is also no longer considered to be the highest standard of rigor. It’s interesting to look at a modern mathematical computer formalization of geometry, like Lean’s geometry library. Euclid took all sorts of theorems for granted, that the computer insists we prove. How do we know that the angle ABC is equal to the angle CBA? How is the angle ABB defined? If you say it can’t be defined, then every single time you use the angle ABC, you need to prove that A does not equal B, and B does not equal C. Euclid basically ignored this issue, and got lucky in that it never led to a bug in his proofs. Lean decides that the angle ABB should be considered to be a 90 degree angle. But from a modern point of view, geometry is hopelessly messy to make rigorous. It is far cleaner to build up integers, sets, rationals, real numbers, real analysis, and then tack on geometry at the end.

Euclidean geometry ends up being far from abstract mathematical truth. With modern progress in mathematics, we see that Euclidean geometry is not a great approximation of the world, and it isn’t the most rigorous area of mathematics either. We keep it around for historical and teaching purposes, basically.

So how can we explain the fact that for thousands of years Euclidean geometry was the pinnacle of mathematics? We could have another mathematical revolution, where we discover that our current mathematics methods are not great approximations to the world, and they aren’t sufficiently rigorous, either. The value of mathematics cannot lie in the fact that it is an abstract truth. It is the quest for this abstract truth. And the quest for this truth is a human activity. This quest would not exist without people to go questing.

Personally, I suspect that mathematics is on the verge of another revolution like the non-Euclidean revolution. Software will eat mathematics. The standard for mathematical rigor will rise again - any proof that cannot be checked by a computer will be considered insufficiently rigorous. It will be obvious there is a mathematical revolution once the computers knock off a few of the longstanding open problems. Just like nowadays many subareas of physics basically require that you write a decent amount of Python code and become a decent software engineer, in the future mathematics will also grow much more intertwined software engineering.

That’s my prediction, anyway.

The Datacenter of Babel

Stephen Wolfram has a model of the universe, the Ruliad, in which every set of possible rules for the laws of physics is operating in parallel. His motivating hypothesis is the Principle of Computational Equivalence, which states that no matter how a computer is built, whether it be a regular computer like a Macbook or an implicit computer running via cellular automaton, it is capable of computing the same things.

Jorge Luis Borges wrote an excellent short story called The Library of Babel. It describes an infinite library, containing all possible 410-page books. The vast majority are completely worthless nonsense, but somewhere within its corridors, every possible coherent book exists.

Perhaps these ideas can be combined. Consider the Datacenter of Babel. Room after room is full of racks of computers. Every possible codebase is running somewhere on one of its servers. Somewhere there lies a Minecraft server where all the cows are modded to look blue. Somewhere there lies a Bitcoin miner containing Satoshi’s private keys. Somewhere, perhaps, there lies a computer slowly emulating a perfect model of our own universe.

Is the world a simulation? Is the Datacenter of Babel real? In some sense, if the universe can be modeled by a computer at all, then the Datacenter of Babel must be an accurate model of the universe.

Is this a useful model? Imagine strolling through the Datacenter of Babel, connecting your laptop at random to various servers. The vast majority, of course, are running nonsensical code, full of syntax errors, crashing the very moment the machine was turned on. Without a map, you could hike for years without ever encountering a functional server.

Indeed, we have no real map to the space of all possible programs. Wolfram theorizes that it should be possible to search the space of short programs to find interesting ones. To me, it seems like we can create a number of neat-looking pictures, but we have never found anything useful by searching programs. Once you realize that the Datacenter of Babel is not a useful model, you also realize that the Ruliad is not a useful model.

The underlying problem with the Principle of Computational Equivalence is ignoring the efficiency of programs. There is a long history of this - the traditional theoretical definition of “computable” functions ignores how long it takes to compute them - but in practice, something that takes 10^100 time might as well be impossible. The Datacenter of Babel might be a correct model, but it is an inefficient model, in terms of how efficient it is to even locate ourselves within the model, much less make any conclusion from it.

I am entertained by the concept, though, of an infinite datacenter. I wonder how one would set up the routers….

Interstellar Cold War

Most science fiction prefers to ignore the speed of light when thinking about space colonization. Star Trek has warp speed, The Expanse has wormholes, Three Body Problem has instantaneous interstellar communication. If you could travel faster than light, a civilization that stretches across multiple star systems might feel just like a civilization that covered multiple continents on Earth, in the days before jet travel.

In reality, we’re pretty sure that you can’t go faster than the speed of light. What does this mean for the politics of an interstellar civilization?

Imagine humanity spread across just two planets, that are 20 light years apart from each other. You can communicate, but it’ll take at least 20 years for a message to cross. You can travel yourself, but it’ll take at least 20 years for a ship to cross.

Can a single country span the two planets? It doesn’t really make sense - a ruler or a legislative body in one place would take 40 years to handle any issue that arose. 20 years to learn about the problem, 20 years to inform the locals of the solution.

How would war between the planets work? Imagine you lived on one planet, and you heard that the space Nazis had taken over the government of the other planet. They hate your planet, they haven’t declared war, but they have enough nuclear weapons to destroy your planet. Any moment now, a swarm of nukes could drop down from space. Maybe they launched 19 years ago and they’re already on their way.

Mutually assured destruction works when one side can’t wipe out the other, and both sides share a planet that they don’t want to destroy. If one side has superior technology, so that they could win with a first strike, the logic of mutually assured destruction doesn’t apply any more. But with distant enemies, you don’t know how much their technology has advanced in 20 years.

You also can’t understand the mentality of your enemies, if they live 20 light years away from you. You don’t even know the names of the decisionmakers. You can’t pick up the red phone to Moscow in case of emergency to talk people down from the cliff.

You can easily imagine a world government learning that bad guys were about to take over a distant planet, and deciding that a preemptive war might be necessary. Of course, if both sides are thinking this way, that just makes war even more likely.

It seems quite dangerous to settle planets in other star systems before we have figured out a way to stop having wars. Fortunately, it looks like it’s going to take us a while to spread out of the solar system. Hopefully we can figure out this “peace on Earth” thing first.

Books of One Beautiful, Negative Note

Sometimes the characters in a book are happy, excited, engaged in their lives, having adventures, and when you read the book you get fired up thinking about doing things like they’re doing. And sometimes a character is suffering. Some negative emotion is overwhelming them, and the book isn’t immediately viscerally pleasurable to read, but the description is so vivid and rich you can’t stop reading, you feel like you are learning of the depths of human experience, although in some sense the book makes you unhappy.

Recently, unintentionally, I have found myself reading several of this second type of book. These books are very good, and I recommend you read any of them that strike your fancy. They ring a bell in my head, it sounds a beautiful note, but it is a negative feeling, a bad one, and I don’t to eject it per se, but I want to crystallize it and set it aside to be known rather than felt. So I am encasing my thoughts about these books in this blog post, to exorcise them, and perhaps share them with you, o blog reader.

Let’s begin.

The Death of Ivan Ilyich and Other Stories

There are a number of different Tolstoy story collections; this collection is the one I read.

No surprise - the best story here is the title story, The Death of Ivan Ilyich, and its emotion is the fear of death. There are so many portrayals of death in modern culture, but almost always as a quick, violent death, happening to somebody else. Ivan suffers slowly, with doctors trying to help but achieving nothing. His family members are both constantly near him, and not really close to him, growing emotionally further away as he comes closer to death and they remain alive. Is it possible to understand how you will feel when close to death? Do we want to understand that?

Another great story in this collection is The Kreutzer Sonata. Its emotion is jealousy. It’s a real song, and it fits the story perfectly. It’s a sonata for violin and piano, played by two people. The main character’s wife plays this sonata with another man, and the emotional bond it forms between them drives the main character insane, sending him into a jealous, violent rage.

I think you should read this story and simultaneously listen to the sonata. I lack the words to describe music well, but in the “presto” part the violin and piano are handing the melody back and forth, slowly building its intensity higher, and it just perfectly matches the main character’s rising insanity. Start it when you get to the part where the main character starts talking about the Kreutzer Sonata.

Try listening to this version on Spotify. Gidon Kremer and Martha Argerich are great musicians, but also, they have become my mental image of the characters. Look at them:

Doesn’t Martha Argerich look like she could be the beautiful woman around which the love interests revolve in a Tolstoy story, and Gidon Kremer, with that mildly goofy grin, look like he could be the sort of guy who at first seems like an innocent nerd and then sneakily charms someone’s wife?

Anyway. Great stories.

Some critics, like Harold Bloom, think Hadji Murat, also in this collection, is one of the greatest short stories of all time. I was surprised to see that after I read it. My initial impression of the main character (Hadji Murat) was that he is a naive and corrupt loser. He expects to be able to convince the Russian empire to change its military strategy, while being ignorant of its bureaucracy. He’s bitter that he has been fired by his side’s leader. And what he wants is to be installed as a local ruler, as the guy who betrays his own side in the war. Indeed, he ends up failing to accomplish anything, dying pointlessly, basically getting what he deserves. So, a decent story, but nothing special. Reminds me of a bunch of real world stories from Afghanistan.

But apparently many readers see Hadji Murat as a hero, a noble warrior who represents bravery and ambition? I still liked the story as a collection of vignettes about this eternal empire-vs-a-foreign-culture war. I feel like there is this core assumption that it’s noble to kill a lot of people while achieving nothing because of the glory of war, and people who like the Hadji Murat character must agree with that assumption, and I don’t. It’s odd to me because War and Peace, which Tolstoy wrote before writing this story, seemed like it was strongly in opposition to that view.

The Luminous Novel

The Luminous Novel is about procrastination. The author is a semi-famous writer who gets a big grant to finish his masterpiece. He starts recording a diary of everything he does, during his “year of finishing the masterpiece”. And it’s just chock full of complete wastes of time. Like, hex editing shareware to get around copy protection, when he is “supposed” to be working.

Is it an interesting diary? It reminds me of Knausgaard in some ways - just much more realistic than you would expect, and that aspect of it makes up for a lack of narrative or point. About halfway through the book, I decided it was pointless, but somehow curious, and I evaluated the book as “not that great” but figured I’d keep reading anyway because, well, I was stuck in Tahoe and the I-80 was closed so I was going to be reading something and I just wanted to great it.

And then maybe 85% of the way through the book, he’s like, okay. So I couldn’t do it. I failed. Instead of my masterpiece, I have this diary. I have a little bit of other stuff but it just didn’t come together. Then the last 15% of the book is what he has of the masterpiece, and it’s amazing. Gripping, realistic, vivid, each page is everything you want of a great novel. It just doesn’t fit together. There’s no real overall plot, no consistent set of characters, only this dream of sharing this luminous feeling at the heart of his life and love.

So did he do it? I feel like he successfully got 15% of the way there. He died shortly after the period recorded, and this novel will forever be a partially great novel.

The whole time he’s waking up at 3 pm, going to sleep at 8 am, and trying a slew of weird herbal remedies. He mentions right at the end of the book that he stopped drinking coffee and this seems to have magically fixed his terrible sleep problems and made him healthier in other ways too.

I found this book to be inspirational, honestly. He could have produced a truly great novel. He succeeded at a lesser goal - making a good, but fairly weird novel. I think the secret is a really mundane one - he just should have wasted less time and improved his health by taking the standard actions that everyone recommends to do these things.

Crime and Punishment

I finally succeeded in reading this book on my third attempt. Sometimes a difficult book is like a difficult hiking trail - if you’re in shape, and you have the right gear, you can enjoy a beautiful hike, when somebody out of shape wearing flip flops finds it to be a painful slog. Perhaps recently I have been getting into better “reading shape”.

Most “antihero” characters have a fixed sort of badness, but they are likeable, so you root for them as the story goes on, and they just stay how they are. It’s like the reader agrees to suspend their disbelief and pretend the character is good, and just pay attention to the exciting actions and hope they turn out well for the antihero. Sometimes the antihero is only a little bad, like an art thief who steals art and never hurts anyone, and you just permanently accept that this sort of little bit of badness is okay. Or perhaps they die in the end to achieve moral balance, so that you can be left feeling that things worked out appropriately.

Raskolnikov is different. He commits murder, sort of because he needs money, but also because he sort of has a philosophical view that he’s special and the regular rules of morality don’t apply to him. His thinking just isn’t very clear at the time. And then it is impossible for the reader to consistently root for Raskolnikov, because he doesn’t even consistently root for himself. His guilt becomes stronger and stronger, eventually crushing him. He isn’t like the crooks in a heist movie who cleverly try to evade the law - he’s distracted by his own obsession about what he has done, slowly becoming less and less able to even try to evade the police.

Which Raskolnikov is the more sympathetic one? The cool and calm protagonist we see at the start who thinks he can get away with murder, or the emotional wreck unable to face his family as he drags himself to the police station to talk to the investigator, unsure whether he should admit to the murder? Are we rooting for Raskolnikov to get away with it, or are we rooting for him to do the right thing, and confess?

The Trial

The Metamorphosis is supposed to be Kafka’s masterpiece, but I think I liked this one better. (I read this translation.) The Trial is about that frustration and dread you feel when interacting with a huge bureaucracy.

Of all these books, The Trial was the most painful to read. It’s a good thing it is relatively short. I would read a bit, pause, and just feel miserable. Sometimes it was hard to say why I kept reading. But, at the same time I strongly recommend this book.

There’s a difference between how it feels in the moment to read a book, and how it feels to have read a book. It’s like a weekend afternoon where the kids are causing all sorts of trouble, and it’s so frustrating, but for a fifteen minute period everyone is behaving so nicely, and you snap a picture of mom and the kids baking muffins where everyone looks so happy, and it’s a great picture so you look back at it later and have great memories, so you keep coming back to the Good Muffin Recipe, and in the end a great tradition is formed.

Except, instead of eating delicious muffins, the payoff here is… a deeper understanding of the emotional nature of being frustrated by impersonal forces? Hmm. Well, it’s a great payoff, trust me.

Josef K is arrested. He asks what he’s being arrested for. Nobody knows. It’s not that they won’t tell him - they’re happy to tell him what he’s being arrested for. But that happens at a later stage in the process. What is the process? Well, it’s not as simple as just explaining what the process is. The best way to handle it is to find a good lawyer, or at least not one of the many lawyers who will mislead you about the process more than they clarify. Of course, that isn’t straightforward. But good luck. Don’t miss your first hearing. When is the first hearing? Well, it isn’t precisely a “hearing”, it’s more like a discussion that gradually merges into a hearing.

And so on. It’s like the nightmare where you forgot to turn in your homework, plus the nightmare of being late to an important event, plus the feeling of getting a notification from the IRS that you filed your taxes wrong, all expanded out into a novel. There is nothing else quite like it.

Kafka himself was essentially a middle manager in a large insurance company. He was considered “tireless and ambitious”.

Conclusion

This is enough. These books are great, but this is all the negative novel I can handle, for now. Next I am going to try to read something full of joy and delight.