Godel's Construction for Humans

Part I: Setup

One day, our favorite neighborhood superintelligent game-theoretic agent Omega sits me down and says “John, let’s play a game.”

“I’ve written a simulation of you,” says Omega, “and before we get to the main game, I need to calibrate it. There’s a few parameters which need to be matched in order to properly simulate you.”

“Ok,” I reply, “What do I need to do?”

“I need you to prove this theorem,” says Omega, “while you work on proving it, I will simulate you proving the theorem, and make sure that the simulation output matches your own proof.” She hands me a piece of paper which (translated from math to english) reads “There exist infinitely many prime numbers.”

This is a classic problem, so I pull out my pencil and quickly write down a simple proof. When I’m done, Omega checks the paper, then checks her computer, and smiles.

“The simulation matches!” Omega announces. “All of the parameters fit, and now we can perfectly simulate you. Now, while I set up the main game...” Omega hands me few pages of paper.

Part II: Introspection

“Read through that carefully,” says Omega, “It contains a full specification of the simulation of you.” She hands me one more piece of paper. “These are the parameters we just calibrated, so now you have everything needed to run a simulation of yourself.”

I look at the papers and frown. It’s shorter than I would have liked.

I start flipping through. Omega’s models are, as usual, quite elegant. Looking at the fifth page, I grab a piece of mail off the table and run a quick back-of-the-envelope calculation. The result outlines a dream I had the night before with tiny multicolored lobsters pinching at my feet. Another calculation predicts that my blood sugar is a bit low… I grab a granola bar from my bag, then redo the calculation with time advanced by twenty minutes.

After I finish reading, I decide to try a slightly more complicated calculation. I check back a few pages, and find what I’m looking for: the specification for an infinite lazy data structure which encodes me, calculating a simulation of myself calculating a simulation of myself calculating a simulation of myself calculating…

“Ready!” says Omega, breaking my infinite regress. “Have you figured out that simulation specification?”

“I think so,” I reply, “it’s surprisingly understandable. Very elegant.”

“Thank you,” replies Omega. “On to the main game!”

Part III: The Game

Omega hands me another single sheet of paper. “Please prove this theorem,” she says.

I look at the sheet. It shows a data structure which refers back to the me-simulation spec. I flip back and forth for a minute, decoding the contents of the new paper, until I realize what it says:

“John cannot prove this theorem.”

I stop. It’s an impressive piece of work. First, a full, perfect mathematical specification of myself. Then, a shorter statement claiming that, based on the mathematical specification of me, I cannot prove the theorem. If I do prove the theorem, then I’ve proven that I can’t do it…

Wait! Technically, this just claims that the *simulation* of me can’t prove the theorem. So if the simulation is inaccurate, I might still be able to - I slap my forehead. No, this is Omega I’m dealing with. She’s scrupulously honest, and her simulations have never once been wrong. This is an accurate specification of me.

For all intents and purposes, I’m dealing with a copy of myself. If I can prove this theorem, then so can the simulation. But the statement says “John cannot prove this theorem.” If it’s false, then I *can* prove it, but then I’d be proving something false, so my proof would be wrong, so the theorem would be true… And if it’s true, then I can’t prove it.

I grumble a bit. It’s a classic diagonalization gambit. There’s no way I can prove this theorem… unless...

Part IV: Breaking Out

The only way I can prove this theorem is if I can somehow make the simulation *not* match myself. I mean, the simulation specifies a perfect copy of me, but if I could use some information which the simulation doesn’t have… Smiling slightly, I reach into my pocket, and withdraw a q-coin.

“A quantum random coin,” says Omega, “very clever.”

I catch a hint of sarcasm. “You knew full well I was going to use this, didn’t you?”

“Of course,” replies Omega, “The simulation is also using a q-coin. You haven’t actually diverged from it yet.”

“But once I flip this, I will,” I say, “It’s perfect randomness. The simulation can predict that I’ll flip it, and it can even simulate all possible outcomes, but it won’t know which outcome I actually get.”

Omega smiles as I flip the q-coin. Heads. I flip it again. Tails. I keep flipping. Heads-heads-heads-heads-tails-heads-tails…

Eventually, I turn back to the math. Sure enough, the simulation specifies a full distribution over all possible outcomes of the coin flip. I start to think about how to finally prove that theorem…

“Crap,” I say.

“Yup,” replies Omega.

“I’ve diverged from the simulation, but those coin flips don’t actually have a significant causal impact on my ability to prove the theorem. The theorem-proving part of the system isn’t chaotic enough to be affected by coin flips. There’s a whole distribution in there for the outcome of the flips, but that distribution isn’t relevant to theorem-proving.”

I lean back and close my eyes. If I want the coin-flips to affect theorem-proving, then I need some way to leverage randomness of the flips in the proof itself...

The Hierarchy of the Sciences

There is an intuitive sense among scientists that an hierarchy exists in the sciences. It looks roughly like this:

The hierarchy is fuzzier than drawn, especially among the “soft” sciences. I'm not going to bother perfecting the diagram; just keep in mind it’s not perfect.

This hierarchy pops up in a lot of different ways. This xkcd, for example, expresses the hierarchy in terms of “purity”. In practice, there’s a lot more to it than just aesthetics - the hierarchy of the sciences has both historical causes and real social consequences.

Social Status

I once heard a biologist give a tangential parable about physicists in a talk. Physicists, he said, are like cowboys. Every now and then, a gang of physicists rides into your field, whooping and hollering, shoots holes in all your theories, and then rides off into the sunset.

Practitioners sometimes joke about the hierarchy of sciences the way xkcd does. What we usually avoid talking about directly is the social side - though most are loathe to admit it, the hierarchy of the sciences reflects a real status hierarchy among scientists. Physicists do not tell parables about biologists shooting holes in their theories. Or chemists. Or economists. But mathematicians… mathematicians have been known to shoot holes in the work of physicists.

In general, fields frequently contribute results to fields below theirs on the hierarchy. Mathematicians contribute useful results to all of the scientific fields, but other scientists contribute new math much less often. Physicists have established subfields within lower sciences - think biophysics or econophysics - but you don’t hear much about biologists or psychologists contributing new results to physics. This pattern mostly holds up further down the hierarchy.

Occasionally, people will contribute to a field immediately above theirs - physicists discover new theorems, chemists break ground in physics - but one rarely hears about people contributing to fields two levels or more above their own. Indeed, I recall one instance where a biologist rediscovered a major theorem of statistics, a biology journal published it as a new tool, and then everyone was soundly mocked by mathematicians for not knowing statistics 101.

(Note: Philosophers do not have any real status in the sciences. They are drawn at the top of the hierarchy in much the same way you’d tell a four-year-old that they get to be ship captain for a day, then let them stand on the bridge and give “orders”.)

“Real Science”

There’s a sense in which some sciences have matured into “real science”, an intuitive dividing line. On one side are fields like chemistry or physics,  where the existing theory is mathematically precise and experimentally powerful and generalizable and will always be useful even as new theory evolves. On the other side are fields like psychology and economics, where theories lack mathematical precision and/or experimental validity and don’t generalize and have limited utility. Some people use the terms “hard” and “soft” sciences to describe these.

Historically, everything started out “soft”. The line dividing “real sciences” has shifted over time, as chemistry evolved from phlogiston to the periodic table, and biology evolved from elan vital to today’s state of affairs. As far as I can tell, the “real science” dividing line today looks something like this:

As the dotted line suggests, I’ve heard a general sentiment among many people (including myself) that biology today is the frontier of real science; biology is currently midway through a transformation from ad-hoc theory to an experimentally robust, mathematically precise field. I recall the first session in MIT’s intro biology course, in which the lecturer spent about half the class saying “look, you probably don’t think biology is a real science, and the biology you learned in high school isn’t… but a lot of that stuff is out of date, and you’re going to find that the field has come a long way.” It’s an exciting time to be in biology.

(If you’re still not sure whether the scientific hierarchy actually reflects social status, then try telling both a physicist and a biologist that their fields are not “real science”, and see how they react. Better yet, don’t try this.)

Engineering and Applied Disciplines

One good way to recognize which fields have matured into “real science” is to look for corresponding engineering disciplines. Once a scientific field has reached maturity, its theory is robust and useful enough that engineers start to adopt it, and new engineering fields are born. This creates an hierarchy of engineering, in parallel to the scientific hierarchy:

Again, it’s an exciting time to be in biology, as biology’s first real engineering field is just starting off.

One of the things which surprised me in college was the social status hierarchy in engineering, which to some degree reflects the hierarchy in the sciences. Anecdotally, the salaries of my classmates in computer science/EE/ME/Materials/Chem E seem to follow the hierarchy.

The Engineering Frontier

The absence of any engineering fields corresponding to the fields lower on the hierarchy is one of the main ways to tell they’re still below the “real science” dividing line. The soft sciences have not yet matured enough to support robust engineering. However, we can speculate on which fields will likely become engineering-type fields once the corresponding sciences mature enough to support them. This results in a “real science and engineering” frontier:

This diagram has all sorts of interesting space for speculation. It’s generally assumed that, as biology becomes a real science, medicine will become a real, robust engineering field. More interesting possibilities exist in finance and marketing (and other areas) - imagine what these fields will look like once sufficiently robust scientific theories are available to underpin them! And then there’s sociology… at this point, it’s hard to even imagine what the engineering applications of robust sociological theory might actually look like, but it would involve engineering of society and culture. Perhaps the memetic equivalent of genetic engineering? Memetic engineering?

Then there’s AI. AI is squarely on the “real science and engineering” boundary right now. As an engineering field, it corresponds to the more philosophically rich areas of mathematics, ripe with issues like self-reference, logical completeness, and the deceptively difficult mathematical/ethical question of how to formulate an AI’s objective.