The following is inspired by an exchange between myself and another user on this NaNoWriMo forum thread regarding Artificial Intelligence.
The Penrose–Lucas argument states that, because humans are capable of knowing the truth of Gödel-unprovable statements, human thought is necessarily non-computable.
— Wikipedia: Orchestrated objective reduction#Penrose–Lucas argument
Gödel’s incompleteness theorems prove that no formal system of logic can be both consistent and complete.
- A consistent system is one that never proves false statements.
(The simplest consistent system is the one that never proves a false statement because it never proves any statement.)
- A complete system is one that proves every true statement.
(The simplest complete system is the one that states “all things are true”: it proves every false statement, sure, but it doesn’t miss any true ones.)
In particular, Gödel’s second theorem says that no formal system of logic can prove its own consistency, unless it is inconsistent.
Gödel’s incompleteness theorems are closely related to the
halting problem in computability theory. The question raised by the
halting problem is: given an arbitrary computer program
X eventually come to an end, or will
run forever? Turing proved that there is no algorithm that can answer the
question for every program
X. As proofs are
algorithmic – that is, they follow a sequence of steps, and the steps obey
some list of rules – it follows that there must exist computer programs
that will run forever but that cannot be proven to run
forever. Thus, for some programs
X does not
halt” is an example of a true statement that cannot be proven true:
The Penrose–Lucas argument claims that humans are able to see that certain formal systems of logic are actually consistent, and furthermore that this demonstrates that the human brain is not limited by Gödel’s incompleteness theorems. Penrose suggests that there exist physical systems which are deterministic yet not algorithmic, and that the brain is one of these non-algorithmic physical systems. If this were so, it would follow that the brain cannot be simulated by a computer, at least not as we currently conceive them, as computers are algorithmic.
Gödel’s first and second incompleteness theorems
Gödel’s first incompleteness theorem constructs a sentence, called “the
Gödel sentence” (
GF), for formal system
GF is a statement
F about polynomials, sets, or whatever
F’s basis is… but it is also a statement about
F. In particular,
GF is a statement
that is true iff
GF cannot be proved in
F – that is, it can be rendered in English as “this
sentence is not provable in
This leads to Gödel’s second incompleteness theorem, which (as stated
above) proves that
F cannot prove the consistency of
F is inconsistent). The
second theorem is more powerful than the first, as the first follows
immediately from the second: if
F is inconsistent, then any
sentence can be proved in
false; however, if we assume axiomatically that
consistent, we can construct a larger system
(rendered in English as
F + “
F is consistent”)
that can prove that
GF cannot be proved in
F, and thus that
GF is true.
Lucas’s original formulation of the argument was in terms of Gödel
sentences being knowably true to humans, not in terms of formal systems
being knowably consistent. However, outside of a few esoteric systems of
logic, such as Robinson arithmetic, the two incompleteness theorems are
generally equivalent. Thus, we phrase our arguments in terms of
F (not) proving its own consistency, rather than in terms
F (not) proving its Gödel sentence
ONE: Maybe Humans Use More Powerful Axioms?
When Gödel dropped his bombshell, the world of logic and rational argument were turned upside down, and it may have seemed to some, fleetingly, that science and mathematics would never be the same again. In the event, science, mathematics and daily life proceeded more or less normally in spite of it. To many scientists, Gödel’s theorem was regarded as little more than an obscure curiosity, one that could be shrugged aside as largely irrelevant to the real world. Now, following the work of Gregory Chaitin, that is no longer a tenable response. Chaitin greatly extended the sweep of Gödel’s basic insight, and re-cast the notion of incompleteness in a way that brings it much closer to the real world of computers and physical processes. A key step in his work is the recognition of a basic link between mathematical undecidability and randomness. Something is random if it has no pattern, no abbreviated description, in which case there is no algorithm shorter than the thing itself that captures its content. And a random fact is true for no reason at all; it is true “by accident,” so to speak. With this conceptual tool-kit, Chaitin was able to demonstrate that mathematics is shot-through with randomness. It’s there even in ordinary arithmetic! Mathematics, supposedly the epitome of logical orderliness, is exposed as harboring irreducible arbitrariness.
— Paul Davies, Foreword to Thinking about Gödel & Turing by Gregory Chaitin
When people these days say “logic”, they usually mean
ZFC set theory
or something built on top of it.
ZFC is used so heavily
because (a) it’s widely believed to be consistent, and (b) the statements
it makes mostly line up with our intuitive ideas about what “truth” is.
(Other formal systems of logic exist — Peano arithmetic, propositional
calculus, first-order and second-order predicate calculus, et al. — but
the same Gödelian arguments apply to them as apply to
they will not be considered separately.)
Suppose that humans can perceive the truth of the statements
ZFC is consistent”. This is nothing special, really. We can
pick a new axiom
X out of a hat such that
ZFC’s consistency. It’s not even hard. That said,
some values of
X are boring… but not all: for
X = “there exists
a weakly inaccessible cardinal”,
then we can prove
ZFC consistent and we gain the
power to prove some new and interesting things about infinity.
That power comes at a cost, though: how do we know if
ZFC+X is consistent? One could prove
ZFC+X’s consistency by inventing a new axiom
but who says
ZFC+X+Y is consistent? And so on. Each
time you add an axiom, you’re making the system more powerful, giving
yourself the power to prove more things true… but how can you be sure that
you’re proving the “right” things? An axiom is just an assumption! You
can’t just blindly assume that your assumptions are true!
X was redundant,
ZFC+X rests on shakier
ZFC itself. You have to take an inventory of
ZFC+X can prove, compare it to what
ZFC+Not(X) can prove, and decide which one you think feels
“truthier”, i.e. which one is a better model of reality. Seasoned
mathematicians can (and have!) spent decades debating which
X feel “truthy”.
Some people have the bright idea of directly using
ZFC is consistent”, better known as
One could then repeat this process, creating the theories
ZFC+Con(ZFC)+Con(ZFC+Con(ZFC)), and so on forever. However,
the theory that results from this process is no longer
recursively enumerable. This means that the theory contains
statements that are “true” but that cannot be derived from the axioms in a
finite number of steps… in other words, statements that are true but not
provable: incompleteness. We’re right back where we started.
And now, a quick tangent…
Ω is a real number between 0 and 1,
representing the probability that a randomly constructed computer
program will halt.
Ω is an example of a
non-computable real number: it can be defined but it cannot be
computed, because computing it would require solving the halting problem.
Even so, we can learn some interesting facts about its value.
The exact value of
Ω depends on the computer programming
language being used, so let’s call the language
L and the
ΩL. Knowing the first
ΩL allows one to solve the halting problem for
all programs in
L of length
n or shorter. Given
that, one might expect that we could learn nothing about
ΩL’s value… but that expectation is wrong. We can
prove the first few bits of
“How many bits?”, you might ask. Well, that depends on
one would expect, but it also depends on which formal system of logic you
specify. As Chaitin explains in his book,
Thinking about Gödel & Turing, the number of bits of
ΩL that you can prove in a formal system
F for fixed
L is a measurement of the
K(F) held in the axioms of
What the hell does that mean? Well, it means that formal systems
contain crystallized knowledge, stored in the form of axioms, and that the
set of truths provable from
F has a size that depends
directly on the number of bits of
F. Each digit of
random, meaning both that it contains maximum entropy and that it
cannot be predicted algorithmically. (These two statements are equivalent
in information theory.) If adding an axiom
X to theory
F grants the power to prove an additional
K(X|F) ≥ k.
However, your value for
ΩL will be wrong if
F+X contains a contradiction: garbage in, garbage out.
Penrose (and Lucas before him) would have us believe that we can skip all this stuff with proof and axioms, and just directly perceive the truth straight off the piece of paper, using a magic truth sensor in our brain.
A more plausible scenario is that humans contain an in-born model of logic
that’s more powerful than
ZFC. What does “more powerful”
mean? Higher in information entropy content, and therefore able to prove
more theorems. Suppose then that when Penrose “perceives” the consistency
ZFC, what’s really going on is that his native axioms
NA) are more powerful than
ZFC, and this grants
him the power to formulate a mental proof of
consistency. Now there’s the question of “is
and that one is much harder to answer, especially because
NA’s axioms are hardwired into the brain and aren’t available
to Penrose for introspection.
To prove the consistency of
NA, one might try building
so on. (Hereafter
However, this would represent an infinite number of assumptions and would
thus require an infinite amount of true information to justify.
What’s more, there isn’t just one thing called
Con(NAx)”, for any of our values for
x. When we’ve been saying “
Con(F)” for some
F, it’s really just been shorthand for a very
complex statement in
F about a polynomial, or a set, or
F’s basis is… and there are multiple ways to “spell”
Con(F), each of which proves something about a
different polynomial, and each of which thus allows the proof of
a different set of theorems! In particular, each “spelling” of
Con(NAx) permits us to derive additional digits of
ΩL in the
NA basis — digits which we
established are random! — and the actual digits we derive will depend on
how we “spelled”
Thus, for Penrose’s argument to be right, Penrose would have to know
an infinite amount of true information; at the very least, he
should be able to derive the digits of
not logically impossible… but it does seem pretty damn unlikely.
And it definitely contradicts the laws of physics as we know them, because
information entropy is tightly coupled to thermodynamic entropy and
the Bekenstein bound
imposes a maximum limit on the entropy for a given volume of space.
To summarize: Penrose and Lucas fail to convincingly make the leap
from “I can tell that
ZFC is consistent” to “I can tell if
any formal system is consistent”. The former can be achieved with
finite axioms and does not violate Gödel’s incompleteness theorems; the
latter requires Penrose and Lucas to know a completed infinity of
true facts (which is physically impossible, to the best of our knowledge).
What’s more, those infinite facts are random: each one is true
without any reason, explanation, or justification why.
TWO: Wait, Who Said Humans Are Consistent?
Some mathematicians assert that doubts about whether PA is consistent, and whether it can be proven to be consistent, are trivial and pointless, partly because this places all of mathematics in doubt. However, as to the triviality, much of the most interesting and profound mathematics of this century has been concerned with just such doubts. As to the number of proofs that are cast into doubt by the possibility of inconsistency in PA, the "perfect consistency or total gibberish" approach to formal systems evidently favored by many mathematicians is not really justified.
— Math Pages, “Is Arithmetic Consistent?”
You’ve been wrong before, haven’t you? Come on, admit it. We’ve all been wrong about something, even if it was when you were a toddler. I guarantee that there’s at least one thing in your life that you once believed to be true but turned out not to be. It’s universal.
Okay, so you admitted that you’ve been wrong before. You know, back then. But you updated your beliefs, and now you’re a different person. A truer person. You were wrong then, but surely you’re not wrong now.
Ha! I was just pulling your leg! You’re still wrong about something, I’m sure. It’s okay, so am I, and so is every other human being who has ever existed.
Let’s talk about Gödel’s theorems again. If Steve walks up to you and says, in all seriousness, “Wrong? I am never wrong, for I am Steve!”, does that really increase your confidence that Steve is never wrong? No, didn’t think so. In fact, if there’s anything you can conclude from what Steve said, it’s that “Steve is never wrong” is wrong. And so it goes for formal logical systems: never trust the ones that say “you can trust me”.
Penrose would have us believe that Steve is right — that humans are consistent, i.e. we never believe false things. Now, “never” is a strong word. Couldn’t it simply be that we rarely believe false things?
3 is prime, 5 is prime, and 7 is prime. By induction, all the odd integers are prime.
— aphorism of unknown provenance
(The joke is in the difference between “induction” – reaching a conclusion from the evidence of finite examples – and “induction” – formally proving that sentence
X0is true and that sentence
Now, most mathematicians run away in horror at the suggestion that their favorite formal system might be inconsistent. After all, it’s a fairly elementary fact that, if you can prove one false thing, then you can use modus ponens to prove any false thing. But that disregards a property called “local consistency”: the practical reality is that, if your system is mostly consistent — that is, the rules you use most frequently are consistent with each other — then your system will yield valid proofs most of the time. Sure, you can use the system to prove an absurdity… but if you don’t already know where the contradiction lies, then your odds of tripping over it by accident are slim. Any formal system that humans use regularly has this local consistency property, because otherwise we would have noticed the absurdity already.
Hey, wait a minute. “Mostly consistent? Correct most of the time?” That sounds like us!
“ZFC was right once, ZFC was right twice, ZFC was right three times. By induction, ZFC is always right!”
To summarize: humans are occasionally wrong. We get by because our wrongness is merely occasional, and usually that’s good enough. But being mistaken even once means that humans are logically inconsistent. Gödel’s theorem doesn’t apply to us, because we’re willing to guess (which necessarily means believing a falsehood now and then).
THREE: Where Are the Hyper-Gödelian Computers?
Computing, as we understand it today, is based on algorithms — that is, reaching an answer by following a series of logical steps. A leads to B, B leads to C, and so on. To formalize what was meant by an algorithm, Turing proposed a very simple model of a computer: a spool of paper tape arranged in squares, a tape head that can read, write, and erase the square of tape directly beneath it, a tiny memory equivalent to exactly one square of tape, and a fixed list of rules telling the tape head what to do next. This simple machine is capable of carrying out any possible algorithm. Everything from a lowly calculator up to a supercomputer can be reduced to this model, called the “deterministic Turing machine” (DTM).
Computer scientists sometimes imagine how powerful a computer would be if it could guess the right answer instantly. But a magic box that always gives the right answer isn’t very interesting… or very trustworthy. How would one know if the box were broken? So we limit our guessing computer by adding one requirement: it can only guess the correct answer if it can also provide a proof that the answer it guessed is right, and the proof has to be something that a DTM could check in a reasonable amount of time. The result: a “non-deterministic Turing machine” (NTM).
Even with this limitation, an NTM would be fantastically powerful: it could spit out a proof of nearly any mathematical conjecture you care to imagine, it could solve every logistical problem in the world, it could break any encryption, and so on. Goldbach conjecture got you down? Just have the NTM try to guess a proof. Want to solve the Traveling Salesman Problem? Let the NTM take a spin. Your business rival uses AES-256 encryption to protect their secrets? No problem, just tell the NTM a few facts about the file format, and the NTM will guess the correct key.
(Technically speaking, DTMs and NTMs both answer the same questions, but an NTM’s guessing power makes it vastly faster at reaching an answer. Questions that would take an exponential amount of time for a DTM to answer would be practical to ask of an NTM.)
Penrose proposes something far more than an NTM. He believes that there is a natural physical phenomenon that inerrantly arrives at true conclusions without intervening steps. In contrast with NTMs, Penrose’s proposed phenomenon is not required to provide a proof that it gave the right answer. If this phenomenon existed, it would be – with no exaggeration – unimaginably powerful.
Penrose’s phenomenon would not be confined to brains, of course. Whatever Lucas may have intended, Penrose’s argument is not a resurrection of vitalism, dualism, or the like: the argument proposes new physics, and new physics invite the strong possibility that we will figure out how to take advantage of them. Let’s say we can build a computer from Penrose’s phenomenon, and let’s call it a Penrose machine (PM).
Imagine a computer that could instantly give you the answer to any well-formed question! “How many words of French have ever been spoken?”, you ask? That’s easy: just give the PM a French dictionary and the starting conditions of the universe, and it can simulate a new universe, count the number of spoken French words, and return the answer to you instantly! Or maybe the PM is limited to yes/no answers; in that case, ask it if the answer is more than a billion words, more than a trillion, and so on, until you get a “no”, then back off and do a binary search. Yes, that will require bringing thousands of universes into existence, and each of those simulated universes will have the ability to build PMs of its own. But it’s okay, because the PM proposal removes all the limits on what computers can do. Every question with a yes/no answer could be answered by the PM, instantly — even questions that couldn’t be answered by a Turing machine with infinite time and infinite tape!
(In technical terms, Turing machines given infinite time and infinite tape
are limited to answering decision problems from class
recursive language problems. Since the PM can dodge Gödel’s incompleteness
theorems, the PM must be able to solve
ALL, the class
of all possible yes/no decision problems, and Penrose’s argument would
have us believe that it can do so in a small – constant or polynomial –
amount of time. The class
R is already huge, but if
R is an ant, then the class
ALL is the whole
universe. Most of
the questions that fall in
ALL - R
are fairly esoteric, but there are a few real-world yes/no questions that
we’d like to answer. Of those, most of them have to do with matrix math or
Diophantine equations, but a very practical one is
“Is there an airfare cheaper than $X from city Y to city Z?”.)
But… if the laws of physics permit such mind-boggling feats of logic, then why do we experience a universe where only DTMs are practical?
It’s not impossible that the laws of physics might be layered, so that deeper layers have access to more powerful models of computation. In fact, we know of one such layer: quantum physics is believed to be faster than a DTM but slower than an NTM, yet it’s much easier to build a DTM than it is to build a quantum computer. That said, how quantum physics adds up to classical physics (and thus the DTM) is widely recognized as an important question — a question that needs an answer. What’s more, we’ve made good inroads into answering that question, and in demonstrating why quantum physics necessarily simplifies to classical physics.
Penrose’s proposal, however, does nothing to answer how such a powerful force could ever bind itself into knots that resemble our reality. Because a PM would have no limitations on what questions it could answer, there is no “shape” to the reality it would necessarily create — no reason to expect that a PM would inherently limit itself to the Turing model of computation, as opposed to something more powerful or less powerful.
To summarize: Penrose fails to explain how his proposal would lead to a universe that looks like our own — and it is difficult to imagine how it ever could. Penrose’s claims are extraordinary, and therefore require extraordinary evidence – evidence which Penrose does not provide.
BONUS: Why Didn’t Evolution Take Advantage of This?
Penrose proposes that the (as-yet purely hypothetical) deeper theory
uniting gravity with quantum mechanics will somehow be able to provide us
with non-Gödelian truths. Moreover, he proposes that these physics are
already active in our biology, accessible to our brains. There exists a
particular cell structure, the microtubule, that he claims is the
cellular version of the Penrose machine (PM) discussed above. This, he
says, is the reason humans are able to perceive the consistency of formal
logic systems like
Given Penrose’s proposal, one might naïvely expect that microtubules are found in the human brain and nowhere else. That expectation would be wrong. Microtubules are found in all cell types in the human body. Indeed, they are found in all eukaryotic cells — from humans to worms to sponges to single-celled amoebae. Their function is fairly well-understood: they are a major component of the cytoskeleton, which allows the cell to change and hold its shape; and they act as a cellular “railroad” for motor proteins to grip as they move resources from one part of the cell to another. They play a particularly important role in cell division, forming the “mitotic spindle” which organizes the chromosomes, pulls them apart, and steers them into the daughter cells’ nuclei.
It’s not unheard of for evolution to assign multiple functions to a single structure… but having a single structure act as both a transportation network and a computer seems odd, to say the least. Especially since we have a fairly good idea of how microtubules are formed from their protein dimer subunits, how they are disassembled, and which motor proteins bind to them, and we haven’t seen anything that looks like it might be a molecule-encoded question floating toward a microtubule, or a molecule-encoded answer floating away from one. Microtubules don’t rearrange molecules; they just act as a toothed rail for motor proteins to ratchet along.
(And no, it’s not an electrical current or an ion flow or anything like that, either. We can stick electrical probes into individual cells and measure the electrical gradients of cellular organelles. That’s how we learned how mitochondria work. “Microtubules are doing something weird with Ca2+ ions” would have won someone a Nobel prize.)
Anyway, that’s not my point. My point is: given the unfathomable computational power of a PM, one would expect evolution to take better advantage of it.
Imagine a rabbit and a fox. The rabbit is hiding in its burrow, wondering if the fox is waiting outside today. It considers the conditions under which it has seen the fox in the past: the smell on the air, the sounds made by the birds (who may or may not see the fox), the current weather, and so on. It processes all this information in an instant, using the naturally occurring PMs in its brain cells to simulate countless universes, each of them containing a copy of the fox. The fox, both the real one and the countless simulations thereof, is itself spawning countless universes in its own mind, simulating the rabbit’s behavior, deciding whether it should wait by the burrow or try for easier prey today. Those simulations spawn simulations of their own, and so on to infinity, and in the blink of an eye, the rabbit and the fox reach their conclusion:
- Rabbit leaves, fox stays: rabbit gets eaten — but the rabbit only leaves if the fox left in the simulation, therefore contradiction.
- Rabbit stays, fox stays: fox goes hungry — but the fox only stays if the rabbit left in the simulation, therefore contradiction.
- Rabbit leaves, fox leaves: fox misses a meal — but the fox would stay if the rabbit left in the simulation, therefore contradiction.
- Rabbit stays, fox leaves: rabbit goes hungry — but the rabbit would leave if the fox left in the simulation, therefore contradiction.
+++ Divide By Cucumber Error. Please Reinstall Universe And Reboot +++
Does this sound like real life? Infinitely intelligent predators trying to hunt infinitely intelligent prey? No, it doesn’t. In real life, there’s an entire subfield of economics devoted to how individuals make decisions in the face of limited decision-making time, partial information, and finite computational power.
(Wait, economics? Yeah, economics. If you spend enough time around economists, everything is economics.)
The rabbit does the best it can with the information it has, but the rabbit instinctually knows that thinking takes time, and that time is precious. The rabbit weighs the pros and cons, the risks of leaving (the fox) vs the risks of staying put (hunger), and makes a choice that ultimately is some piecemeal approximation of an innate Bayesian decision theory. The rabbit steps outside, hears the fox step on a twig, and runs back to the burrow. The fox gives chase, catches the rabbit, and devours it.
Or consider the lowly amoeba. It’s a single-celled organism, but it does contain microtubules, so a reasonable reading of Penrose’s argument would suggest that it could perform any computation that a human can. An amoeba should be as smart as an octopus, then: capable of learning to associate stimuli with rewards, capable of studying its environment and hatching escape plans, capable perhaps of play, of thought, of consciousness. Treatment of amoebic dysentery with nitroimidazole would be a holocaust in miniature, snuffing out billions of conscious minds.
To summarize: if hyper-Gödelian phenomena were accessible to
biology, you can be damn well sure that evolution would take advantage of
it. Since Penrose’s microtubules would be
intended), every plant, animal, mushroom, and protist would be as smart
(and as conscious) as a human.