So this is a post-modern book on incompleteness! If you look at another little book on incompleteness, Nagel & Newman's Gödel's Proof, which I enjoyed greatly as a child, you'll see plenty of material on symbolic logic, and no material on computing. In my opinion the right way to think about all this now is to start with computing, not with logic. So that's the way I'm going to do things here. There's no point in writing this book if I do everything the way everyone else does!
LISP means ``list processing,'' and was invented by John McCarthy and others at the MIT Artificial Intelligence Lab around 1960. You can do numerical calculations in LISP, but it's really intended for symbolic calculations. In fact LISP is really a computerized version of set theory, at least set theory for finite sets. It's a simple but very powerful mathematical formalism for expressing algorithms, and I'm going to use it in Chapters III, IV & V to present Gödel, Turing's and my work in detail. The idea is to start with a small number of powerful concepts, and get everything from that. So LISP, the way I do it, is more like mathematics than computing.
And LISP is rather different from ordinary work-a-day programming languages, because instead of executing or running programs you think about evaluating expressions. It's an expression-based or functional programming language rather than a statement-based imperative programming language.
Two versions of the LISP interpreter for this book are available at my web site: one is 300 lines of Mathematica, and the other is a thousand lines of C.
(), (a b c), (+ (* 3 4) (* 5 6))The first example is the empty list (), also called nil. The second example is a list of three elements, the atoms a, b and c. And the third example is a list of three elements. The first is the atom +, and the second and the third are lists of three elements, which are atoms. And you can nest lists to arbitrary depth. You can have lists of lists of lists...
The empty list () is the only list that's also an atom, it has no elements. It's indivisible, which is what atom means in Greek. It can't be broken into smaller pieces.
Elements of a list can be repeated, e.g., (a a a). And changing the order of the elements changes the list. So (a b c) is not the same as (c b a) even though it has the same elements, because they are in a different order. Hence lists are different from sets, where elements cannot be repeated and the order of the elements is irrelevant.
Now in LISP everything, programs, data, and output, they are all S-expressions. That's our universal substance, that's how we build everything!
3*4 + 5*6The first step to convert this to LISP is to put in all the parentheses:
((3*4) + (5*6))And the next step to convert this to LISP is to put the operators before the operands (prefix notation), rather than in the middle (infix notation):
(+(*34)(*56))And now we need to use blanks to separate the elements of a list if parentheses don't do that for us. So the final result is
(+(* 3 4)(* 5 6))which is already understandable, or
(+ (* 3 4) (* 5 6))which is the standard LISP notation in which the successive elements of a list are always separated by a single blank. Extra blanks, if included, are ignored. Extra parentheses are not ignored, they completely change the meaning of an S-expression.
(((X))) is not the same as X!
What are the built-in operators, i.e., the primitive functions, that are provided for doing arithmetic in LISP? Well, in my LISP there's addition +, multiplication *, subtraction -, exponentiation ^, and, for comparisons, less-than <, greater-than >, equal =, less-than-or-equal <=, and greater-than-or-equal >=. I only provide natural numbers in my LISP, so there are no negative integers. If the result of a subtraction is less than zero, it gives 0 instead. Comparisons either give true or false. All these operators, or functions, always have two operands, or arguments. Addition and multiplication of more than two operands requires several + or * operations. Here are examples of arithmetic expressions in LISP, together with their values.
(+ 1 (+ 2 (+ 3 4))) is the same as (+ 1 (+ 2 7)) is the same as (+ 1 9) which yields 10,
(+ (+ 1 2) (+ 3 4)) is the same as (+ 3 7) which yields 10,
(- 10 7) yields 3,
(- 7 10) yields 0,
(+ (* 3 4) (* 5 6)) is the same as (+ 12 30) which yields 42,
(^ 2 10) yields 1024,
(< (* 10 10) 101) is the same as (< 100 101) which yields true,
(= (* 10 10) 101) is the same as (= 100 101) which yields false.
+ 1 + 2 + 3 4 is the same as (+ 1 (+ 2 (+ 3 4))),If you look at these examples you can convince yourself that there is never any ambiguity in restoring the missing parentheses, if you know how many arguments each operator has. So M-expressions are an example of what used to be called parenthesis-free or Polish notation. [This is in honor of a brilliant school of Polish logicians and set theorists.]
+ + 1 2 + 3 4 is the same as (+ (+ 1 2) (+ 3 4)),
- 10 7 is the same as (- 10 7),
- 7 10 is the same as (- 7 10),
+ * 3 4 * 5 6 is the same as (+ (* 3 4) (* 5 6)),
^ 2 10 is the same as (^ 2 10),
< * 10 10 101 is the same as (< (* 10 10) 101),
= * 10 10 101 is the same as (= (* 10 10) 101).
There are circumstances in which one wants to give parentheses explicitly rather than implicitly. So I use the notation " within an M-expression to indicate that what follows is an S-expression. Here are three examples:
The M-expression "(+ + +) denotes the S-expression (+ + +).If one didn't use the double quotes, these arithmetic operators would have to have operands, but here they are just used as symbols. But these are not useful S-expressions, because they are not valid arithmetical expressions.
The M-expression ("+ "- "*) denotes the S-expression (+ - *).
The M-expression + "* "^ denotes the S-expression (+ * ^).
(define (fact N) (if (= N 0) [then] 1 [else] (* N (fact (- N 1)))))Here comments are enclosed in square brackets. This is the definition in the official S-expression notation. Here the definition is written in the more convenient M-expression notation.
define (fact N)This can be interpreted unambiguously if you know that ``define'' always has two operands, and ``if'' always has three.
if = N 0 [then] 1
[else] * N (fact - N 1)
Let's state this definition in words.
The factorial function has one argument, N, and is defined as follows. If N is equal to 0 then factorial of N is equal to 1. Otherwise factorial of N is equal to N times factorial of N minus 1.
So using this definition, we see that (fact 4) is the same as
(* 4 (fact 3))which yields 24.
(* 4 (* 3 (fact 2)))
(* 4 (* 3 (* 2 (fact 1))))
(* 4 (* 3 (* 2 (* 1 (fact 0)))))
(* 4 (* 3 (* 2 (* 1 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
So in LISP you define functions instead of indicating how to calculate them. The LISP interpreter's job is to figure out how to calculate them using their definitions. And instead of loops, in LISP you use recursive function definitions. In other words, the function that you are defining recurs in its own definition. The general idea is to reduce a complicated case of the function to a simpler case, etc., etc., until you get to cases where the answer is obvious.
Car and cdr are the funny names of the operations for breaking a list into pieces. These names were chosen for historical reasons, and no longer make any sense, but everyone knows them. If one could start over you'd call car, head or first and you'd call cdr, tail or rest. Car returns the first element of a list, and cdr returns what's left without the first element. And cons is the inverse operation, it joins a head to a tail, it adds an element to the beginning of a list. Here are some examples, written in S-expression notation:
(car (' (a b c))) yields a,Maybe these are easier to understand in M-expression notation:
(cdr (' (a b c))) yields (b c),
(car (' ((a) (b) (c)))) yields (a),
(cdr (' ((a) (b) (c)))) yields ((b) (c)),
(car (' (a))) yields a,
(cdr (' (a))) yields (),
(cons (' a) (' (b c))) yields (a b c),
(cons (' (a)) (' ((b) (c)))) yields ((a) (b) (c)),
(cons (' a) (' ())) yields (a),
(cons (' a) nil) yields (a),
(cons a nil) yields (a).
car '(a b c) yields a,There are some things to explain here. What is the single quote function? Well, it just indicates that its operand is data, not an expression to be evaluated. In other words, single quote means ``literally this.'' And you also see that the value of nil is (), it's a friendlier way to name the empty list. Also, in the last example, a isn't quoted, because initially all atoms evaluate to themselves, are bound to themselves. Except for nil, which has the value (), every atom gives itself as its value initially. This will change if an atom is used as the parameter of a function and is bound to the value of an argument of the function. Numbers though, always give themselves as value.
cdr '(a b c) yields (b c),
car '((a) (b) (c)) yields (a),
cdr '((a) (b) (c)) yields ((b) (c)),
car '(a) yields a,
cdr '(a) yields (),
cons 'a '(b c) yields (a b c),
cons '(a) '((b) (c)) yields ((a) (b) (c)),
cons 'a '() yields (a),
cons 'a nil yields (a),
cons a nil yields (a).
Here are some more examples, this time in M-expression notation. Note that the operations are done from the inside out.
car '(1 2 3 4 5) yields 1,This is how to get the second, third, fourth and fifth elements of a list. These operations are so frequent in LISP that they are usually abbreviated as cadr, caddr, cadddr, caddddr, etc., and so on and so forth with all possible combinations of car and cdr. My LISP though, only provides the first two of these abbreviations, cadr and caddr, for the second and third elements of a list.
car cdr '(1 2 3 4 5) yields 2,
car cdr cdr '(1 2 3 4 5) yields 3,
car cdr cdr cdr '(1 2 3 4 5) yields 4,
car cdr cdr cdr cdr '(1 2 3 4 5) yields 5,
cons 1 cons 2 cons 3 cons 4 cons 5 nil yields (1 2 3 4 5).
(if predicate then-value else-value)This is a way to use a logical condition, or predicate, to choose between two alternative values. In other words, it's a way to define a function by cases. If the predicate is true, then the then-value is evaluated, and if the predicate is false, then the else-value is evaluated. The unselected value is not evaluated. So if-then-else and single quote are unusual in that they do not evaluate all their arguments. Single quote never evaluates its one argument, and if-then-else only evaluates two of its three arguments. So these are pseudo-functions, they are not really normal functions, even though they are written the same way that normal functions are.
And what does one use as a predicate for if-then-else? Well, for numerical work one has the numerical comparison operators <, >, <=, >=, and =. But for work with S-expressions there are just two predicates, atom and =. Atom returns true or false depending upon whether its one argument is an atom or not. = returns true or false depending upon whether two S-expressions are identical or not. Here are some examples written in S-expression notation:
(if (= 10 10) abc def) yields abc,
(if (= 10 20) abc def) yields def,
(if (atom nil) 777 888) yields 777,
(if (atom (cons a nil)) 777 888) yields 888,
(if (= a a) X Y) yields X,
(if (= a b) X Y) yields Y.
Display, which is useful for obtaining intermediate values in addition to the final value, is just an identity function. Its value is the same as the value of its argument, but it has the side-effect of displaying its argument. Here is an example written in M-expression notation:
car display cdr display cdr display cdr '(1 2 3 4 5)
displays (2 3 4 5)
displays (3 4 5)
displays (4 5)
and yields value 4.
Eval provides a way of doing a stand-alone evaluation of an expression that one has constructed. For example:
eval display cons "^ cons 2 cons 10 nilThis works because LISP is interpreted, not compiled. Instead of translating a LISP expression into machine language and then running it, the LISP interpreter is always present doing evaluations and printing results. It is very important that the argument of eval is always evaluated in a clean, initial environment, not in the current environment. I.e., the only binding in effect will be that nil is bound to (). All other atoms are bound to themselves. In other words, the expression being evaled must be self-contained. This is important because in this way the result of an eval doesn't depend on the circumstances when it is used. It always gives the same value if it is given the same argument.
displays (^ 2 10)
and yields value 1024.
length '(a b c) yields 3,Note that the size of (a b c) is 7, not 8, because when size evaluates its argument the single quote disappears. [If it didn't, its size would be the size of (' (a b c)), which is 11!]
size '(a b c) yields 7.
(lambda (list-of-parameter-names) function-body)For example, here is the function that forms a pair in reverse order.
(lambda (x y) (cons y (cons x nil)))Functions can be literally given in place (here I've switched to M-expression notation):
('lambda (x y) cons y cons x nil A B) yields (B A)Or, if f is bound to the above function definition, then you can use it like this
(f A B) yields (B A)(The general idea is that the function is always evaluated before its arguments are, then the parameters are bound to the argument values, and then the function body is evaluated in this new environment.) How can we bind f to this function definition? Here's a way that's permanent.
define (f x y) cons y cons x nilThen (f A B) yields (B A). And here's a way that's local.
('lambda (f) (f A B) 'lambda (x y) cons y cons x nil)This yields (B A) too. If you can understand this example, then you understand all of my LISP! It's a list with two elements, the expression to be evaluated that uses the function, and the function's definition. Here's factorial done the same way:
('lambda (fact) (fact 4) 'lambda (N) if = display N 0 1 * N (fact - N 1))This displays 4, 3, 2, 1, and 0, and then yields the value 24. Please try to understand this final example, because it really shows how my LISP works!
Here is an example, in which a function returns one of its arguments without doing anything to it. ('lambda (x y) x 1 2) yields 1, and ('lambda (x y) y 1 2) yields 2. Why? Because inside the function definition x is bound to 1 and y is bound to 2. But all previous bindings are still in effect except for bindings for x and y. And, as I've said before, in the initial, clean environment every atom except for nil is bound to itself. Nil is bound to (). Also, the initial bindings for numbers can never be changed, so that they are constants.
(let variable [be] value [in] expression)And to bind a function name to its definition we write it like this.
(let (function-name parameter1 parameter2...) [be] function-body [in] expression)For example (and now I've switched to M-expression notation)
let x 1 let y 2 + x y yields 3.And
let (fact N) if = N 0 1 * N (fact - N 1) (fact 4) yields 24.
Define actually has two cases like let-be-in, one for defining variables and another for defining functions:
(define variable [to be] value)and
(define (function-name parameter1 parameter2...) [to be] function-body)The scope of a define is from the point of definition until the end of the LISP interpreter run, or until a redefinition occurs. For example:
define x 1
define y 2
Then + x y yields 3.
define (fact N) if = N 0 1 * N (fact - N 1)Define can only be used at the ``top level.'' You are not allowed to include a define inside a larger S-expression. In other words, define is not really in my LISP. Actually all bindings are local and should be done with let-be-in, i.e., with lambda bindings. Like M-expressions, define and let-be-in are a convenience for the programmer, but they're not officially in my LISP, which only allows lambda expressions and temporary local bindings. Why? Because in theory each LISP expression is supposed to be totally self-contained, with all the definitions that it needs made locally! Why? Because that way the size of the smallest expression that has a given value, i.e., the LISP program-size complexity, does not depend on the environment.
Then (fact 4) yields 24.
To illustrate all this, let me show you how to manipulate finite sets—sets, not lists. We'll define in LISP all the basic set-theoretic operations on finite sets. Recall that in a set the order doesn't count, and no elements can be repeated.
First let's see how to define the set membership predicate in LISP. This function, called member?, has two arguments, an S-expression and a set of S-expressions. It returns true if the S-expression is in the set, and false otherwise. It calls itself again and again, and each time the set, s, is smaller.
define (member? e s) [is e in s?]Let me state this in English. Membership of e in s is defined as follows. First of all, if s is empty, then e is not a member of s. Second, if e is the first element of s, then e is a member of s. Third, if e is not the first element of s, then e is a member of s iff e is a member of the rest of s.
if atom s false [if s is empty, then e isn't in s]
if = e car s true [if e is the first element of s, then it's in s]
(member? e cdr s) [otherwise, look if e is in the rest of s]
Then (member? 2 '(1 2 3)) yields true.
And (member? 4 '(1 2 3)) yields false.
Now here's the intersection of two sets, i.e., the set of all the elements that they have in common, that are in both sets.
define (intersection s t) [elements that two sets have in common]
if atom s nil [if the first set is empty, so is the intersection]
if (member? car s t) [is the first element of s in t?]
[if so] cons car s (intersection cdr s t)
[if not] (intersection cdr s t)
Then (intersection '(1 2 3) '(2 3 4)) yields (2 3).
Here's the dual of intersection, the union of two sets, i.e., the set of all the elements that are in either set.
define (union s t) [elements in either of two sets]
if atom s t [if the first set is empty, then the union is the second set]
if (member? car s t) [is the first element of s in t?]
[if so] (union cdr s t)
[if not] cons car s (union cdr s t)
Then (union '(1 2 3) '(2 3 4)) yields (1 2 3 4).
Now please do some exercises. First define the subset predicate, which checks if one set is contained in another. Then define the relative complement of one set s minus a second set t. That's the set of all the elements of s that are not in t. Then define unionl which is the union of a list of sets. Then define the cartesian product of two sets. That's the set of all ordered pairs in which the first element is from the first set and the second element is from the second set. Finally, define the set of all subsets of a given set. If a set has N elements, then the set of all its subsets will have 2N elements.
The answers to these exercises are in the LISP run in the next section. But don't look until you try to do them yourself!
Once you can do these exercises, we're finally ready to use LISP to prove Gödel's incompleteness theorem and Turing's theorem that the halting problem cannot be solved! But we'll start Chapter III by seeing how to do a fixed point in LISP. That's a LISP expression that yields itself as its value! Can you figure out how to do this before I explain how?
LISP Interpreter Run
[[[[[
Elementary Set Theory in LISP (finite sets)
]]]]]
[Set membership predicate:]
define (member? e[lement] set)
[Is set empty?]
if atom set [then] false [else]
[Is the element that we are looking for the first element?]
if = e car set [then] true [else]
[recursion step!]
[return] (member? e cdr set)
define member?
value (lambda (e set) (if (atom set) false (if (= e (car
set)) true (member? e (cdr set)))))
(member? 1 '(1 2 3))
expression (member? 1 (' (1 2 3)))
value true
(member? 4 '(1 2 3))
expression (member? 4 (' (1 2 3)))
value false
[Subset predicate:]
define (subset? set1 set2)
[Is the first set empty?]
if atom set1 [then] true [else]
[Is the first element of the first set in the second set?]
if (member? car set1 set2)
[then] [recursion!] (subset? cdr set1 set2)
[else] false
define subset?
value (lambda (set1 set2) (if (atom set1) true (if (memb
er? (car set1) set2) (subset? (cdr set1) set2) fal
se)))
(subset? '(1 2) '(1 2 3))
expression (subset? (' (1 2)) (' (1 2 3)))
value true
(subset? '(1 4) '(1 2 3))
expression (subset? (' (1 4)) (' (1 2 3)))
value false
[Set union:]
define (union x y)
[Is the first set empty?]
if atom x [then] [return] y [else]
[Is the first element of the first set in the second set?]
if (member? car x y)
[then] [return] (union cdr x y)
[else] [return] cons car x (union cdr x y)
define union
value (lambda (x y) (if (atom x) y (if (member? (car x)
y) (union (cdr x) y) (cons (car x) (union (cdr x)
y)))))
(union '(1 2 3) '(2 3 4))
expression (union (' (1 2 3)) (' (2 3 4)))
value (1 2 3 4)
[Union of a list of sets:]
define (unionl l) if atom l nil (union car l (unionl cdr l))
define unionl
value (lambda (l) (if (atom l) nil (union (car l) (union
l (cdr l)))))
(unionl '((1 2) (2 3) (3 4)))
expression (unionl (' ((1 2) (2 3) (3 4))))
value (1 2 3 4)
[Set intersection:]
define (intersection x y)
[Is the first set empty?]
if atom x [then] [return] nil [empty set] [else]
[Is the first element of the first set in the second set?]
if (member? car x y)
[then] [return] cons car x (intersection cdr x y)
[else] [return] (intersection cdr x y)
define intersection
value (lambda (x y) (if (atom x) nil (if (member? (car x
) y) (cons (car x) (intersection (cdr x) y)) (inte
rsection (cdr x) y))))
(intersection '(1 2 3) '(2 3 4))
expression (intersection (' (1 2 3)) (' (2 3 4)))
value (2 3)
[Relative complement of two sets x and y = x - y:]
define (complement x y)
[Is the first set empty?]
if atom x [then] [return] nil [empty set] [else]
[Is the first element of the first set in the second set?]
if (member? car x y)
[then] [return] (complement cdr x y)
[else] [return] cons car x (complement cdr x y)
define complement
value (lambda (x y) (if (atom x) nil (if (member? (car x
) y) (complement (cdr x) y) (cons (car x) (complem
ent (cdr x) y)))))
(complement '(1 2 3) '(2 3 4))
expression (complement (' (1 2 3)) (' (2 3 4)))
value (1)
[Cartesian product of an element with a list:]
define (product1 e y)
if atom y
[then] nil
[else] cons cons e cons car y nil (product1 e cdr y)
define product1
value (lambda (e y) (if (atom y) nil (cons (cons e (cons
(car y) nil)) (product1 e (cdr y)))))
(product1 3 '(4 5 6))
expression (product1 3 (' (4 5 6)))
value ((3 4) (3 5) (3 6))
[Cartesian product of two sets = set of ordered pairs:]
define (product x y)
[Is the first set empty?]
if atom x [then] [return] nil [empty set] [else]
[return] (union (product1 car x y) (product cdr x y))
define product
value (lambda (x y) (if (atom x) nil (union (product1 (c
ar x) y) (product (cdr x) y))))
(product '(1 2 3) '(x y z))
expression (product (' (1 2 3)) (' (x y z)))
value ((1 x) (1 y) (1 z) (2 x) (2 y) (2 z) (3 x) (3 y) (
3 z))
[Product of an element with a list of sets:]
define (product2 e y)
if atom y
[then] nil
[else] cons cons e car y (product2 e cdr y)
define product2
value (lambda (e y) (if (atom y) nil (cons (cons e (car
y)) (product2 e (cdr y)))))
(product2 3 '((4 5) (5 6) (6 7)))
expression (product2 3 (' ((4 5) (5 6) (6 7))))
value ((3 4 5) (3 5 6) (3 6 7))
[Set of all subsets of a given set:]
define (subsets x)
if atom x
[then] '(()) [else]
let y [be] (subsets cdr x) [in]
(union y (product2 car x y))
define subsets
value (lambda (x) (if (atom x) (' (())) ((' (lambda (y)
(union y (product2 (car x) y)))) (subsets (cdr x))
)))
(subsets '(1 2 3))
expression (subsets (' (1 2 3)))
value (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
length (subsets '(1 2 3))
expression (length (subsets (' (1 2 3))))
value 8
(subsets '(1 2 3 4))
expression (subsets (' (1 2 3 4)))
value (() (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4
) (1 3) (1 3 4) (1 2) (1 2 4) (1 2 3) (1 2 3 4))
length (subsets '(1 2 3 4))
expression (length (subsets (' (1 2 3 4))))
value 16
End of LISP Run
Elapsed time is 0 seconds.