In these lectures I discuss philosophical applications of AIT, not practical applications. Indeed, I believe AIT has no practical applications.

The most interesting thing about AIT is that you can almost never determine the complexity of anything. This makes the theory useless for practical applications, but fascinating from a philosophical point of view, because it shows that there are limits to knowledge.

Most work on computational complexity is concerned with time. However this course will try to show that program-size complexity, which measures algorithmic information, is of much greater philosophical significance. I'll discuss how one can use this complexity measure to study what can and cannot be achieved by formal axiomatic mathematical theories.

In particular, I'll show (a) that there are natural information-theoretic constraints on formal axiomatic theories, and that program-size complexity provides an alternative path to incompleteness from the one originally used by Kurt Gödel. Furthermore, I'll show (b) that in pure mathematics there are mathematical facts that are true for no reason, that are true by accident. These have to do with determining the successive binary digits of the precise numerical value of the halting probability Ω for a ``self-delimiting'' universal Turing machine.

I believe that these meta-theorems (a,b) showing (a) that the complexity of axiomatic theories can be characterized information-theoretically and (b) that God plays dice in pure mathematics, both strongly suggest a quasi-empirical view of mathematics. I.e., math is different from physics, but perhaps not as different as people usually think.

I'll also discuss the convergence of theoretical computer science with theoretical physics, Leibniz's ideas on complexity, Stephen Wolfram's book A New Kind of Science, and how to attempt to use information theory to define what a living being is.

In this book I've tried to preserve the informal style of presentation in my lectures that stressed the key ideas and methods and avoided getting bogged down in technical details. There are no proofs here, but there are plenty of proof sketches. I hope that you enjoy reading this book just as much as I enjoyed presenting this material at EWSCS '03!

—Gregory Chaitin

1.1 Is P ≠ NP a New Axiom?

• Our goal: To find the Limits of Mathematical Reasoning

• Tool we'll use: Program-Size Complexity

• It's also called: Algorithmic Information

• Idea starts with Leibniz! 1686!
  Discourse on Metaphysics (in French!)

• AIT is needed to understand what is ``law'' and
  what is ``understanding.''

1.3 Summary of Leibniz, 1686

Following Leibniz, in each of these diagrams the input on the left must be much smaller than the output on the right.

Leibniz's key insight is not that this is ``the best of all possible worlds''. This was anti-Leibniz propaganda by Voltaire, who ridiculed Leibniz and did not understand how subtle and profound Leibniz was. (According to Borges, the word ``optimism'' was invented by Voltaire to mock Leibniz!)

Leibniz's key insight is that God has used few ideas to create all the diversity, richness and apparent complexity of the natural world.³ Leibniz is actually affirming his belief that the universe is rationally comprehensible. (This belief in a rational universe goes back at least to the ancient Greeks, particularly Pythagoras and Plato, but Leibniz's formulation is much sharper and profound because he analyzes in mathematical terms exactly what this belief means.) In modern language, Leibniz was stating his belief in the possibility of science.

³Here is an argument in favor of diversity from Leibniz via Borges. Consider two libraries with exactly the same number of books. Recall that Borges was a librarian! One of the libraries only has copies of Virgil's Aeneid (presumably the perfect book), while the other library has one copy of the Aeneid and many other different (and presumably inferior!) books. Nevertheless, the second library is clearly a more interesting place to visit!

Pythagoras and Plato believed that the universe can be comprehended using mathematics. Leibniz went beyond them by clarifying mathematically what exactly does it mean to assert that the universe can be comprehended using mathematics.

The setup is as follows.

The (static, formal) mathematical theories that we consider are thought of, somewhat abstractly, as a computer program for running through all possible proofs and generating all the theorems in the theory, which are precisely all the logical consequences of the axioms in the theory.

[This assumes that the theory uses a formal language, symbolic logic, requires complete proofs, and provides a proof-checking algorithm that always enables you to decide mechanically whether or not a proof is correct, whether or not it followed all the rules in deriving a logical consequence of the axioms.]

And we shall concentrate our attention on the size in bits of this computer program for generating all the theorems. That's our measure of the complexity of this theory, that's our measure of its information content.

So when we speak of an N-bit theory, we mean one with an N-bit program for generating all the theorems. We don't care that this process is very slow and never terminates. AIT is a theoretical theory, not a practical theory!

Okay, that's half the setup! These are the theories we'll consider.

Here's the other half of the setup. Here are the theorems that we want these theories to be able to establish. We want to use these theories to prove that particular computer programs are elegant.

What is an elegant program? It's one with the property that no smaller program written in the same language produces exactly the same output.⁴

⁴Throughout this discussion we assume a fixed choice of programming language.

There are lots of elegant programs!

For any particular computational task, for any particular output that we desire to achieve, there has to be at least one elegant program, and there may even be several.

Why?

Well, no N-bit theory for any finite N can enable you to prove all true assertions of the form

Let c be the size in bits of the fixed-size routine that does all this: It is given the N-bit theory as data and then it runs through all possible proofs in the theory until it finds a provably elegant program that is sufficiently large (> N + c bits), then it runs that program and returns that large elegant program's output as its own output.

So the N + c bit program displayed above produces the same output as a provably elegant program that is larger than N + c bits. But that is impossible!

So our precise result is that an N-bit theory cannot enable us to prove that any program that is larger than N + c bits is elegant. Here c is the size in bits of the fixed-size routine that when added to the N-bit formal theory as above yields the paradox that proves our theorem.

The conventional view on this held by high-energy physicists is that there is a TOE, a theory of everything, a finite set of laws of nature that we may someday know, which has only finite complexity.

So that part is optimistic!

But unfortunately in quantum mechanics there's randomness, God plays dice, and to know the results of all God's coin tosses, infinitely many coin tosses, necessitates a theory of infinite complexity, which simply records the result of each toss!

So the conventional view currently held by physicists is that because of randomness in quantum mechanics the world has infinite complexity.

Could the conventional view be wrong? Might it nevertheless be the case that the universe only has finite complexity? Some extremely interesting thoughts on this can be found in

It looks complicated,⁵ but it is actually very simple!

⁵Especially if you're given successive digits of π that come from far inside the decimal expansion without being told that they're digits of π—they look random.

According to Wolfram all the randomness we see in the physical world is actually pseudo-randomness. He believes that the physical world is actually deterministic, we just don't know the law.

What is a living being?

How can we partition the world into parts? Can we do this in spite of Parmenides and mystics who insist that the world must be apprehended as a whole and is an organic unity, a single substance, and cannot be separated into independent parts?

I think the key is algorithmic independence.

X and Y are said to be algorithmically independent if the program-size complexity of X and Y ≈ the sum of the individual program-size complexities of X and Y.

I.e., if the number of bits in the simplest theory that explains both simultaneously is approximately equal to the sum of the number of bits in the simplest theories that explain each of them separately.

Independent parts of the world, of which living beings are the most interesting example, have the property that their program-size complexity decomposes additively.

2.1 Day II Summary

1. You can't prove a number is uninteresting/random.

2. You can't determine bits of Ω (accidental mathematical facts).

2.2 Hilbert-Style Formal Theories

• Meta-mathematics: Use mathematics to discover the limits of mathematics. Cannot be applied to intuitive, informal mathematics.

• What's a formal theory?

  • axioms

  • rules of inference

  • symbolic logic

  • formal grammar

  There is a proof-checking algorithm!

• There is algorithm for generating all theorems in size order of proofs! So, following Emil Post, 1944, formal theory = r.e. set of propositions:
  theory → Computer → theorems

• This is a static view of mathematics! It is assumed that the axioms and rules of inference don't change. Mathematical methods can be used to discuss what such a formal system can achieve.

2.3 Summary of Gödel, 1931

• ``This statement is false!''

• True iff false! Paradox!

• ``This statement is unprovable_FT!''

• True iff unprovable_FT! Therefore either a false statement is provable_FT, and FT is useless, or a true statement is unprovable_FT, and FT is incomplete!

• FT = Formal Theory.

2.4 My Approach to Incompleteness

2.5 Borel's Unreal Number B, 1927

2.6 More-Real Turing Number T

• Real Number T Solving Turing's Halting Problem

• T = 0. b₁ b₂ b₃ ...

• The Nth bit b_N of T answers the Nth case of the halting problem.
  b_N tells us whether the Nth program p_N ever halts.

• b_N =

  • 0 → p_N doesn't halt,

  • 1 → p_N halts.

2.7 Some Interesting Cases of the Halting Problem

• Fermat's Last Theorem (Andrew Wiles)
  Does
  x^N + y^N = z^N

  have a solution in positive integers with N ≥ 3?

• Riemann Hypothesis
  About the location of the complex zeroes of the zeta function
  ζ(s) ≡ ∑_n n^−s = ∏_p 1/(1−1/p^s)

  (Here n ranges over positive integers and p ranges over the primes.)
  Tells us a lot about the distribution of prime numbers.

• Goldbach Conjecture
  Is every even number the sum of two primes?

2.8 Crucial Observation

N cases of the halting problem is only log₂ N bits of information, not N bits!

They are never independent mathematical facts!

Why not?

Because we could answer all N cases of the halting problem if we knew exactly how many of the N programs halt. Just run them all in parallel until exactly the right number halt. The others will never halt.

Halting Probability:

|p| is the size in bits of the program p.

I.e., each k-bit program that halts when run on our standard universal Turing machine U contributes 1/2^k to Ω.

The bits of Ω are algorithmically irreducible, algorithmically independent, and algorithmically random!

Ω is a real number with maximal information content. Each bit of Ω is a complete surprise! It's not at all a tame real number like π = 3.1415926... which only has a finite amount of algorithmic information.

Ω is a dangerous, scary real number! Not good to meet in a dark alley! Ω is maximally unknowable! Maximum entropy, maximum disorder!

This makes Ω sound bad, very bad!

On the other hand, Ω is distilled, crystalized mathematical information. If T is coal, then Ω is a diamond!

In fact, initial segments of Ω are ideal new mathematical axioms. Knowing a large initial segment of Ω would settle all halting problems for programs up to that size, which would, to use Charles Bennett's terminology, settle all finitely refutable math conjectures up to that complexity.

Here mathematical truth isn't Black or White. It's Grey!

The best way to think about Ω is that each bit of Ω is 0 or 1 with probability 1/2!

Here God plays dice with mathematical truth!

Knowing all the even bits of Ω wouldn't help us to get any of the odd bits of Ω! Knowing the first million bits of Ω wouldn't help us to get the million and first bit of Ω! The bits of Ω are just like independent tosses of a fair coin!

First of all, U must read one bit of its program p at a time and decide by itself when to stop reading p before encountering a blank at the end of p. In other words, each p for U must be self-delimiting.

Also, U must be universal. This means that for any special-purpose self-delimiting computer C there is a prefix π_C such that concatenating it in front of a program for C gives you a program for U that computes the same output:

H(x) is the size in bits of the smallest program for computing x on each machine.

Then we have

In other words, programs for U are not too large. For U to simulate C adds only a fixed number of bits to each program for C.

Then Ω_U is defined as follows:

Access to the data β is strictly controlled. U reads one bit at a time of p and CANNOT run off the end of p = πβ. The binary data β must be self-delimiting, just like the LISP prefix π, so that U knows when to stop reading it.

I.e., the alphabet for p is binary, not trinary! There is no blank at end of p! That would be a wasted character, one that isn't being used nearly enough!

Does the diophantine equation D(x) = 0 have an unsigned integer solution?

• ∃D such that D(k, x) = 0 has a solution iff p_k halts!
  [Matijasevic]

• ∃D such that D(k, x) = 0 has infinitely many solutions
  iff the kth bit of Ω is a 1!
  [Chaitin]

• ∃D such that D(k, x) = 0 has an even/odd number of solutions
  iff the kth bit of Ω is 0/1!
  [Ord and Kieu]

3.1 Definition of a Self-Delimiting Computer C

Self-delimiting computer C

• C(p) → output

• The program p is a bit string.

• The output can be e.g. a LISP S-expression or a set of S-expressions.

3.2 What do we do with C? Define U!

Next we construct a universal computer U, for example, as follows:

In other words, U can simulate C if to each program for C we add a prefix consisting of a long run of 0's followed by a 1. This prefix is self-delimiting, and the number of 0's in it indicates which C is to be simulated.

Then we have

where

I.e., U's programs are, to within an additive constant, minimal in size.

We take this minimality property as our definition for a universal computer U.

Now somehow pick a particular natural U to use as the basis for AIT.

• Some people are exceedingly unhappy that the value of H depends on the choice of U. But whatever U you pick, the theory goes through. And Day IV, I actually pick a very simple U.

• And since Ω is an infinite object, all the additive constants that reflect the choice of U wash out in the limit.

• Time complexity depends polynomially on the computational model. But in the case of program-size complexity the dependence on U is only an additive constant. So the unfashionable field of AIT depends less on the choice of computer than the fashionable field of time complexity does! So much for fashion!

• Remember, I do not think that AIT is a practical theory for practical applications. All theories are lies that help us to see the truth.¹ All elegant theories are simplified models of the horrendous complexity of the chaotic real world. Nevertheless, they give us insight. You have a choice: elegance or usefulness. You cannot have both!

  ¹``Art is a lie that helps us to see the truth,'' Pablo Picasso.

• If we knew all the laws of physics, and the world turned out to be a giant computer, then we could use that computer as U!

3.4 A More Abstract Definition of the Complexity H

Define an abstract complexity measure H via these two properties:

• H(x) is computable in the limit from above.

  I.e., { ⟨x, k⟩ : H(x) ≤ k } is r.e.

  I.e., H(x) = lim_{t → ∞} H^t(x).

• ∑_x 2^−H(x) ≤ 1.

3.6 AIT Definitions (Continued)

• Mutual information content of two objects:
  H(x : y) ≡ H(x) + H(y) − H(x, y).

  This is the extent to which it is better to compute them together rather than separately.

• An elegant program y* for y is one that is as small as possible. I.e., y* has the property that
  U(y*) = y,    H(y) = |y*|,    H(U(y*)) = |y*|.

• Relative information content H(x | y) of x given an elegant program y* for y, not y directly!
  H(x | y) ≡ min_{U(p, y*)=x} |p|.

  This is the second main technical idea of AIT. First is to use self-delimiting programs. Second is to define relative complexity in this more subtle manner in which we are given y* for free, not y, and we have to compute x.

3.7 Important Properties of These Complexity Measures

• Here is an immediate consequence of our definitions:
  H(x, y) ≤ H(x) + H(y | x) + c.

• And here is an important and subtle theorem that justifies our definitions!
  H(x, y) = H(x) + H(y | x) + O(1).

  This is an identity in Shannon information theory, with no O(1) term. In these two different versions of information theory, the formulas look similar but of course the meaning of H is completely different.

• Let's apply this subtle theorem to the mutual information:
  H(x : y) ≡ H(x) + H(y) − H(x, y).

  We get these two corollaries:

  H(x : y) = H(x) − H(x | y) + O(1),

  H(x : y) = H(y) − H(y | x) + O(1).

  So the mutual information is also the extent to which knowing one of the two objects helps you to know the other. It was not at all obvious that this would be symmetric!

  Again, these two corollaries are identities in Shannon information theory. They justify our whole approach. When I got these results I knew that the definitions I had picked for AIT were finally correct!

3.8 Complexity of Bit Strings. Examples.

• High complexity:
  H(the most complex N-bit strings)   =   N + H(N) + O(1)   ≈   N + log₂ N.

  In other words, you have to know how many bits there are plus what each bit is. And most N-bit strings have H close to the maximum possible. These are the algorithmically random N-bit strings.

  This notion has many philosophical resonances. First, a random string is one for which there is no theory that obeys Leibniz's dictum that a theory must be smaller than what it explains. Leibniz clearly anticipated this definition of randomness.

  Second, a random string is an unexplainable, irrational string, one that cannot be comprehended, except as ``a thing in itself'' (Ding an sich), to use Kantian terminology.

• Low complexity:
  Consider the N-bit strings consisting of N 0's or N 1's.
  H(0^N)   =   H(N) + O(1)   ≈   log₂ N,

  H(1^N)   =   H(N) + O(1)   ≈   log₂ N.

  For such bit strings, you only need to know how many bits there are, not what each bit is. These bit strings are not at all random.

• Intermediate complexity:
  Consider an elegant program p. I.e., no smaller program makes U produce the same output.
  H(p) = |p| + O(1)     if p is an elegant program.

  These bit strings are borderline random. Randomness is a matter of degree, and this is a good place to put the cut-off between random and non-random strings, if you have to pick a cut-off.

3.9 Maximum Complexity Infinite Binary Sequences

• Maximum Complexity:
  An infinite binary sequence x is defined to be algorithmically random iff
  ∃c ∀N [ H(x_N) > N − c ].

  Here x_N is the first N bits of x.

  If x is generated by independent tosses of a fair coin, then with probability one, x is algorithmically random. But how about specific examples?

• Two Examples of Maximum Complexity:
  Ω ≡ ∑_{U(p) halts} 2^−|p|

  Ω' ≡ ∑_N 2^−H(N)

  These are algorithmically random real numbers. The initial segments of their binary expansion always have high complexity.

  From this it follows that Ω and Ω' aren't contained in any constructively definable set of measure zero. In other words, they are statistically (Martin-Löf) random. Therefore Ω and Ω' necessarily have any property held by infinite binary sequences x with probability one. E.g., Ω and Ω' are both Borel normal, for sure, since in general this is the case with probability one. Borel normal means that in any base, in the limit all blocks of digits of the same size provably have equal relative frequency.

  That Ω and Ω' are both Borel normal real numbers can also be proved directly using a simple program-size argument. This can be done because, as Shannon information theory already shows, reals that are not Borel normal are highly redundant and compressible. And the main difference between Shannon information theory and AIT is that Shannon's theory is concerned with average compressions while I am concerned with compressing individual sequences.

• Why can't we demand the complexity of initial segments be even higher?
  Because with probability one, infinitely often there have to be long runs of consecutive zeroes or ones, and this makes the complexity dip far below the maximum possible [N + H(N)] infinitely often!

3.10 The Algorithmic Probability of x, P(x)

But the more subtle proofs have to descend one level and use probabilistic arguments. AIT is an iceberg! Above the water we see program size. But the bulk of the AIT iceberg is submerged and is the algorithmic probability P(x)!

P_C (x) is defined to be the probability that a program generated by coin-tossing makes C produce x:

because one way to compute x is using an elegant program for x. In fact, much, much more is true:

This crucial result shows that AIT, at least in so far as the appearance of its formulas is concerned, is sort of just a version of probability theory in which we take logarithms and convert probabilities into complexities. In particular, the important and subtle theorem that

is seen from this perspective as merely an alternative version of the definition of relative probability:

connecting H(x) and P(x).

This shows that there cannot be too many small programs for x.

In particular, it follows that the number of elegant programs for x is bounded.

Also, the number of programs for x whose size is within c bits of H(x) is bounded by a function that depends only on c and not on x.

This function of c is approximately 2^c.

In fact, any program for x whose size is close to H(x) can easily be obtained from any other such program.

So, what I call Occam's razor, elegant or nearly elegant programs for x are essentially unique!

is an extended version of the Kraft inequality condition for the existence of a prefix-free set of words.

In AIT, the Kraft inequality gives us a necessary and sufficient condition not for the existence of a prefix-free set, as it did in Shannon information theory, but for the existence of a self-delimiting computer C. Once we have constructed a special-purpose computer C using the Kraft inequality, we can then make statements about U by using the fact that

Here's how we construct C!

Imagine that we have an algorithm for generating an infinite list of requirements:

As we generate each requirement ⟨s, o⟩, we pick the first available s-bit program p and we assign the output o to C(p). Available means not an extension or prefix of any previously assigned program for C. This process will work and will produce a self-delimiting computer C satisfying all the requirements iff

Note that if there are duplicate requirements in the list, then several p will yield the same output o. I.e., we will have several p with the same value for C(p).

It is important to be able to simultaneously keep each of these three images in ones mind, and to translate from one image to the next depending on which gives the most insight at any given moment.

In other words, C may be thought of as a kind of constructive probability distribution, and probability one corresponds to the entire unit interval of programs, with longer and longer programs corresponding to smaller and smaller subintervals of the unit interval.

Then the crucial fact that no extension of a valid program is a valid program simply says that the intervals corresponding to valid programs do not overlap.

In the last lecture, Day IV, I'll drop this abstract viewpoint and make everything very, very concrete by indicating how to program C in LISP and actually run programs on C...

4.1 Formal Definition of the Complexity of a Formal Theory

First of all, I never stated the formal version of the incompleteness results about Ω that I explained informally in Day II.

How can we measure the complexity of a formal mathematical theory in bits of information?

H(formal math theory) ≡

such that

Note that this is something new: U is now performing an unending computation and produces an infinite amount of output!

Here are some hints about the proof. We make the tacit hypothesis, of course, that all the theorems proved in theory T are true. Otherwise T is of no interest.

The proof is in two parts.

• First of all you show that
  H(Ω_K) > K − constant.

  This follows from the fact that knowing Ω_K, the first K bits of Ω, enables you to answer the halting problem for all programs for U up to K bits in size.

• Now that you know that Ω_K has high complexity, in the second half of the proof you use this fact to derive a contradiction from the assumption that the formal theory T enables you to determine much more than H(T) bits of Ω. Actually, it makes no difference whether these are consecutive bits of Ω or are scattered about in the base-two expansion of Ω.

Day III we defined the following complexity measures:

• H(x) (absolute, individual) information,

• H(x, y) joint information,

• H(x | y) relative information,

• H(x : y) mutual information.

Well, you could try to make mutual information into the size of a program. E.g., mutual information could be defined to be the size of the largest (not the smallest!) possible common subroutine shared by elegant programs for x and y.¹

Let's look at some examples of how this can be done. How can we make an N-bit string self-delimiting? Well, 2N + 2 bits will certainly do. There's a special-purpose self-delimiting computer C that accomplishes this:

So we've just seen four different examples of how a self-delimiting program can tell us its size as well as its contents.

Another version of the principle that a program tells us its size as well as its contents is the fact that an elegant program tells us its size as well as its output, so

LISP is like a computerized version of set theory!

The LISP S-expression

denotes the following nested tuples:

Programs and data in LISP are always S-expressions. Everything is an S-expression! The S in S-expression stands for Symbolic.

S-expressions that are not lists are called atoms. A, bc, 39 and x-y-z are the atoms in the above S-expression. The empty list () = ⟨ ⟩ is also an atom, usually denoted by nil.

LISP is a functional programming language, not an imperative programming language.

LISP is an expression language. There is no notion of time, there are no GOTO's, and there are no assignment statements!²

²Well, they're actually present, but only indirectly, only subliminally!

LISP programs are expressions that you evaluate, not run, and they yield a value, with NO side-effect! (This is called ``Pure'' LISP!)

Functional Notation in LISP:

So

becomes

in LISP. Prefix notation, not infix notation! Full parenthesization! Fixed number of arguments for each primitive function!

In my LISP most parentheses are understood, are implicit, and are then supplied by the LISP interpreter.

Complete LISP Example. Factorial programmed in my LISP:

   define (f n)
   if = n 0  1
      * n (f - n 1)

With all the parentheses supplied, factorial becomes:

   (define (f n)
   (if (= n 0)  1
       (* n (f (- n 1)))
   ))

In words,  f is defined to be a function of one argument, n. And if n = 0, then  f(n) is 1. If not,  f(n) is n × f(n−1).

Then (f 4) yields value 24, as expected, since 4 × 3 × 2 × 1 = 24.

Define an elegant LISP expression to be one with the property that no smaller LISP expression yields the same value.

In order to measure size properly, LISP expressions are written in a canonical standard notation with no embedded comments and with exactly one blank separating successive elements of a list.

Then the LISP complexity of an S-expression is defined to be the size in characters of an elegant expression with that particular value.

Next represent a formal mathematical theory in LISP as a LISP S-expression whose evaluation never terminates and which uses the primitive function display to output each theorem.

display is an identity function with the side-effect of displaying its operand and is normally used for debugging large LISP S-expressions that give the wrong value.

Theorem—
A formal mathematical theory with LISP complexity N cannot enable you to prove that a LISP expression is elegant if the elegant expression's size is greater than N + 410 characters!

This is a very concrete, down-to-earth incompleteness theorem! In that direction, it's the best I can do!

   try time-limit/no-time-limit expression binary-data

The first argument is either an integer or no-time-limit. The second argument is an arbitrary LISP S-expression. The third argument is a bit string represented in LISP as a list (...) of 0's and 1's separated by blanks.

TRY then yields this triple:

   (success/failure
    value-of-expression/out-of-time/out-of-data
    (list of captured displays from within expression...))

Also, within the expression that is being tried, you can use read-bit or read-exp to get access to the binary data in a self-delimiting manner, either one bit or one LISP S-expression at a time.

TRY is like a large suitcase: I am using it to do several different things at the same time. In fact, TRY is all I really need to be able to program AIT in LISP. All of the other changes in my version of LISP were made just for the fun of it! (Actually, to simplify LISP as much as possible without ruining its power, so that I could prove theorems about it and at the same time enjoy programming in it!)

4.8 LISP Program for Our Standard Universal Computer U

   define (U p)
   cadr try no-time-limit
            'eval read-exp
            p

This function U of p returns the second element of the list returned by TRY, a TRY with no time limit that tries to evaluate a LISP expression at the beginning of p, while making the rest of p available as raw binary data.

Here the program p for U is a bit string that is represented in LISP as a list of 0's and 1's separated by blanks. E.g., p = (0 1 1 0 1...)

Let me explain this!

The binary program p consists of a LISP S-expression prefix (converted into a bit string), that is followed by a special delimiter character, the ASCII newline control character (also converted to bits), and that is then followed by raw binary data.

The newline character adds 8 bits to the program p, but guarantees that the prefix be self-delimiting. Each character in the LISP prefix is given in p as the corresponding 8 ASCII bits.

Within the prefix, read-bit and read-exp enable you to get access to the raw binary data, either one bit or one LISP S-expression at a time. But you must not run off the end of the binary data! That aborts everything! If so, U of p returns out-of-data.

So the program for the universal U consists of a high-level language algorithmic part followed by data, raw binary data. The algorithmic part indicates which special-purpose self-delimiting computer C should be simulated, and the raw binary data gives the binary program for C!

   run-utm-on
   bits ' '(a b c)

And here's a program with one bit of binary data. The prefix is read-bit and the data is 0.

   run-utm-on
   append bits 'read-bit 
          '(0)

Let's change the data bit. Now the prefix is read-bit and the data is 1.

   run-utm-on
   append bits 'read-bit 
          '(1)

run-utm-on is a macro that expands to the definition of U, which is cadr try no-time-limit 'eval read-exp.

   cons eval read-exp
   cons eval read-exp
        nil

This is a 432-bit prefix π for U with the property that

Here x* is an elegant program for x and y* is an elegant program for y.

Therefore

For years and years I used this inequality without having the faintest idea what the value of the constant might be! It's nice to know that there is a natural choice for U that can be easily programmed in LISP and for which c = 432! That's a little bit like dreaming of a woman for years and then actually meeting her! That's also how I feel about now having a version of U that I can actually run code on!

My book The Limits of Mathematics programs in LISP all the proofs of my incompleteness results, in particular, all the key results about Ω. And my book Exploring Randomness programs in LISP all the proofs of the results presented Day III. That's a lot of LISP programming, but I enjoyed it a lot!