{"id":3755,"date":"2012-02-12T16:54:55","date_gmt":"2012-02-13T00:54:55","guid":{"rendered":"http:\/\/www.rudyrucker.com\/blog\/?p=3755"},"modified":"2020-08-15T11:57:00","modified_gmt":"2020-08-15T18:57:00","slug":"an-incompleteness-theorem-for-the-natural-world","status":"publish","type":"post","link":"https:\/\/www.rudyrucker.com\/blog\/2012\/02\/12\/an-incompleteness-theorem-for-the-natural-world\/","title":{"rendered":"An Incompleteness Theorem for the Natural World"},"content":{"rendered":"

I spent the last few of days working on a philosophical essay for a collection of articles about Stephen Wolfram\u2019s 2002 book, A New Kind of Science<\/a><\/em>. I\u2019m a friend of Wolfram\u2019s and a big fan of his work. For much more about Wolfram\u2019s book and its reception, you can see my long 2003 review <\/a>of it for the monthly magazine of the Mathematical Association of America.<\/p>\n

<\/p>\n

But today I don\u2019t want to get into all that, I want to talk about my new essay, which is called \u201cAn Incompleteness Theorem for the Natural World.\u201d\u009d (In 2020 I posted the full essay online as a PDF<\/a>.)\u00a0 I\u2019m very happy with the argument I presented there. The argument isn’t really all that <\/em> complicated\u2014but I\u2019ve been looking for it for about thirty years! I won\u2019t print the whole essay here, but I will print the introductory section to give you an idea of what I\u2019m getting at. A lot of it is based on material in my book, The Lifebox, the Seashell, and the Soul<\/a><\/em>, but just this week I saw how to present it in a much clearer light.<\/p>\n

So here we go, the intro to my essay, \u201cAn Incompleteness Theorem for the Natural World.\u201d\u009d<\/p>\n

<\/p>\n

The philosopher Gottfried Wilhelm von Leibniz is perhaps best known for the fierce controversy that arose between him and Sir Isaac Newton over the invention of calculus. The S-like integral sign that we use to this day is in fact a notation invented by Leibniz.<\/p>\n

When Leibniz was a youth of nineteen, he wrote a paper called \u201cDe Arte Combinatorica\u201d\u009d, in which he tried to formulate a universal algebra for reasoning, in the hope that human thought might some day be reducible to mathematical calculations, with symbols or characters standing for thoughts.<\/p>\n

But to return to the expression of thoughts by means of characters, I thus think that controversies can never be resolved, nor sectarian disputes be silenced, unless we renounce complicated chains of reasoning in favor of simple calculations, and vague terms of uncertain meaning in favor of determinate characters.<\/p>\n

In other words, it must be brought about that every fallacy becomes nothing other than a calculating error, and every sophism expressed in this new type of notation becomes in fact nothing other than a grammatical or linguistic error, easily proved to be such by the very laws of this philosophical grammar.<\/p>\n

Once this has been achieved, when controversies arise, there will be no more need for a disputation between two philosophers than there would be between two accountants. It would be enough for them to pick up their pens and sit at their abacuses, and say to each other (perhaps having summoned a mutual friend): \u201cLet us calculate.\u201d\u009d<\/p><\/blockquote>\n

<\/p>\n

Let\u2019s refer to this notion as Leibniz\u2019s dream \u2014 the dream of finding a logical system to decide all of the things that people might ever disagree about. Could the dream ever work?<\/p>\n

Even if the dream were theoretically possible (which it isn\u2019t), as a practical matter it wouldn\u2019t work anyway. If a universal algebra for reasoning had come into existence, would, for instance, Leibniz have been able to avoid his big arguments with Newton? Not likely. People don\u2019t actually care all that much about logic, not even Leibniz. We just pretend to like logic when it happens to be on our side \u2014 otherwise we very often abandon logic and turn to emotional appeals.<\/p>\n

This said, there\u2019s a powerful attraction to Leibniz\u2019s dream. People like the idea of finding an ultimate set of rules to decide everything. Physicists, for instance, dream of a Theory of Everything. At a less exalted level, newspapers and TV are filled with miracle diets \u2014 simple rules for regulating your weight as easily as turning a knob on a radio. On the ethical front, each religion has its own compact set of central teachings. And books meant to help their readers lead happier lives offer a simple list of rules to follow.<\/p>\n

But, as I hinted above, achieving Leibniz\u2019s dream is logically impossible.<\/p>\n

In order to truly refute Leibniz\u2019s dream, we need to find a precise way to formulate it. As it happens, formal versions of Leibniz\u2019s dream were first developed early in the Twentieth century.<\/p>\n

<\/p>\n

An early milestone occurred in 1910, when the philosophers Bertrand Russell and Alfred North Whitehead published their monumental Principia Mathematica<\/em>, intended to provide a formal logical system that could account for all of mathematics. And, as we\u2019ll be discussing below, hand in hand with the notion of a formal system came an exact description of what is meant by a logical proof.<\/p>\n

There were some problems with the Russell-Whitehead system, but by 1920, the mathematician David Hilbert was confident enough to propose what came to be known as Hilbert\u2019s program<\/em>.<\/p>\n

(1) We will discover a complete formal system, capable of deciding all the questions of mathematics.<\/p>\n

(2) We will prove that this system is free of any possible contradiction.<\/p>\n

As Hilbert put it, \u201cThe conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus<\/em>.\u201d\u009d<\/p>\n

<\/p>\n

For a decade, scientists could dream that Hilbert\u2019s program might come true. And meanwhile mathematics and much of physics were being recast as formal systems. Scientific theories could now be viewed as deterministic processes for determining the truth of theorems. Leibniz\u2019s dream was nearly at hand!<\/p>\n

But, then, in 1931, the logician Kurt G\u00f6del proved his celebrated Incompleteness Theorem.<\/p>\n

G\u00f6del\u2019s Incompleteness Theorem. <\/em>If F is a consistent formal system as powerful as arithmetic, then there are infinitely many sentences which are undecidable for F.<\/p>\n

This means there can never be formal system of mathematics of the kind sought by Hilbert\u2019s program. Every formal system F about mathematics is incomplete in the sense that there are sentences G such that F fails to prove G or ~G, where ~G is the negation of G.<\/p>\n

G\u00f6del\u2019s sentences G take the form of statements that certain algebraic formulas have no solutions in the natural numbers. Normally these sentences include at least one very large numerical parameter that in some sense codes up the entire theory F. Wolfram has suggested that there might be some much simpler undecidable G\u00f6delian sentences that involve very simple algebraic formulae.<\/p>\n

<\/p>\n

Philosophers of science have wondered if there is something like an Incompleteness Theorem for theories about the natural world. One somewhat awkward approach might be to argue that if the natural world happens to be infinite, then we can in some sense represent the system of natural numbers as a list of objects within the world and then go on to claim that the usual undecidable G\u00f6del statements about arithmetic are also statements about the natural world.<\/p>\n

But, as I discuss in my 1982 book, Infinity and the Mind<\/em>, this isn\u2019t a satisfying approach. If we wanted to have number theory be a subset of a theory W about the physical world, we\u2019d need for W to single out an infinite set of objects to play the role of the numbers, and W would also need to define relations the correspond to numerical addition and multiplication.<\/p>\n

What we really want is a proof\u2014or at least a plausibility argument\u2014for a Natural Incompleteness Theorem that asserts the existence of undecidable sentences that are about natural physical processes\u2014as opposed to being about the natural numbers in disguise.<\/p>\n

<\/p>\n

Wolfram\u2019s analysis of computation in his A New Kind of Science <\/em>opens a path. The first step is to accept the idea that natural processes can be thought of as computations. And the second step is to argue for some form of Wolfram\u2019s Principle of Computational Equivalence.<\/p>\n

Wolfram\u2019s Principle of Computational Equivalence (PCE): <\/em>Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication.<\/p>\n

<\/p>\n

In my essay I show that, starting from Wolfram\u2019s two steps, we can prove a Natural Incompleteness Theorem. My method will be to make use of Alan Turing\u2019s 1936 work on what he called unsolvable halting problems. And rather than using the full strength of Wolfram\u2019s somewhat controversial Principle of Computational Equivalence, I\u2019ll base my argument on a weaker assumption, which I call the Halting Problem Hypothesis. And we end up with the following Natural Incompleteness Theorem.<\/p>\n

Natural Incompleteness Theorem. <\/em>For most naturally occurring complex processes and for any correct formal system for science, there will be sentences about the process which are undecidable by the given formal system.<\/p>\n

This is, I believe, a clean statement of new result\u2014and may be of real importance to the philosophy of science. Although Wolfram has pointed out some specific <\/em> examples of undecidable statements about natural processes, he didn\u2019t mange to state the general Natural Incompleteness Theorem.<\/p>\n

But now we have a Natural Incompleteness Theorem telling us that every <\/em>possible complex natural process is going to have undecidable sentences associated with it! Undecidability is everywhere, and all of our theories about nature must remain incomplete.<\/p>\n

I’m very stoked.<\/p>\n","protected":false},"excerpt":{"rendered":"

I spent the last few of days working on a philosophical essay for a collection of articles about Stephen Wolfram\u2019s 2002 book, A New Kind of Science. I\u2019m a friend of Wolfram\u2019s and a big fan of his work. For much more about Wolfram\u2019s book and its reception, you can see my long 2003 review […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-3755","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/posts\/3755","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/comments?post=3755"}],"version-history":[{"count":8,"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/posts\/3755\/revisions"}],"predecessor-version":[{"id":12953,"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/posts\/3755\/revisions\/12953"}],"wp:attachment":[{"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/media?parent=3755"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/categories?post=3755"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rudyrucker.com\/blog\/wp-json\/wp\/v2\/tags?post=3755"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}