“Since is not computable,” continued Griffin, “then no bird of this forest can compute it, and so there is no ideal bird here. Despite the cleverness of many of our birds, none of them is mathematically omniscient.
“But you know,” said Griffin, with a dreamy look in his eyes, “there has been a rumor that in the days before I came here, a bird from another forest far, far away once visited this forest and astounded all the other birds by appearing to be mathematically omniscient. Of course, this is only a rumor, but who really knows? If the rumor is true, then that bird must have been most remarkable; no purely mechanistic explanation could possibly account for its behavior. Those philosophers who are mechanistically oriented and believe that birds, humans, and all other biological organisms are nothing more than elaborate mechanisms would of course deny that any such bird is possible. But I, who do not have complete confidence in the philosophy of mechanisms, reserve judgment on the matter. I’m not saying that I believe the rumor; I’m not saying that there is or was such a bird; I’m merely saying that I believe such a bird might be possible.
“I wish we had more time,” concluded Griffin. “There are so many more facts about this forest that I believe would interest you.”
“I have no doubt!” said Craig, rising. “I am infinitely grateful for all you have taught me, and I’m hoping that I might be able to visit this forest again one day.”
“That would be wonderful!” said Griffin.
Craig left the forest the next day with a twinge of sadness. Although part of him looked forward to renewing his more normal life of crime detection, Craig realized that in his advancing years his interests were veering more and more to the purely abstract and theoretical.
“This vacation has been like an idyllic dream,” thought Craig, as he reached the exit—also the entrance—gate. “I really must visit this forest again!”
“Only the elite are allowed to leave this forest!” said an enormous sentinel who blocked his way. “However, since you have entered this forest and only the elite are allowed to enter, then you must be one of the elite. Therefore you are free to leave, and God speed you well!”
“This is one ritual I will never understand,” thought Craig, as he shook his head with an amused smile.
SOLUTIONS
1 · We first need a bird A such that for any number n, A = . We can take A to be B(C)(), where B is the bluebird and C is the cardinal.
Now we want a bird δ such that for every n, if n = 0 then δ = and if n > 0, then δ = A(P). Equivalently, we want a bird δ such that for all n, δ = (Z)(A(δ(P))). Such a bird δ can be found by the fixed point principle.
2 · We take ∆ to be the bird W(DCδ), where W is the warbler, D is the dove, and C is the cardinal. Then for any number n, ∆ = W(DCδ) = DCδ = C(δ) = (δ) = = .
3 · Let ∆ be the normalizing bird—or, more precisely, the term W(DCδ), which names the normalizing bird. Then for any expression X, the sentence is true, because X has some Gödel number n; X has Gödel number n*n#, so the above sentence is ∆ = .
Now take any term A. Let X be the term , where B is a term for the bluebird. We now show that the sentence A = X is true.
The sentence is obviously true. Also the sentence is true, hence the sentence is true, and so the sentence is true. This is the sentence X = A, and so the sentence A = X is true. This proves the second fixed point principle.
As an application, let us take I for A. Then there is a term X such that I = X is true, hence = X is true, and hence the sentence X = is true. If we let n be the Gödel number of X, then the sentence X = is true, and so X designates its own Gödel number n. By the above proof, we can take X to be the term . However, there is a simpler term that designates its Gödel number—namely, .
A term that designates twice its own Gödel number is . Why?
4 · Let us first prove the lemma. For any bird A, let A# be the bird BA(C), where B is the bluebird and C is the cardinal. For any number n, A# = A, because A# = BA(C) = A(C) = A() = A. This proves that A# = A.
Now suppose A computes . Then A# must compute S*, because for any n in *, the number n*52 is in , hence A = t, and so A# = t. Also, for any number n not in *, the number n*52 is not in , hence A = f, and so A# = f. This proves that A# computes *.
Now for the proof of Gödel’s principle. Suppose is computable. Then * is computable, as we have just seen. Let A be a bird that computes *. By the second fixed point principle there is a term X such that the sentence A = X is true. Let Y be the sentence X = t. We will show that Y is a Gödel sentence for the set .
Let n be the Gödel number of X. Then Y, being the sentence X = t, has Gödel number n*52.
a. Suppose that Y is true. Then the sentence X = t is true and since the sentence A = X is also true, then the sentence A = t is true, and so the sentence A = t is true (because is the numeral ). Therefore n belongs to the set * (because A computes S*, hence if n didn’t belong to S*, then the sentence A = f would be true, which is impossible, since A = t is true). Since n belongs to *, then n*52 belongs to , but n*52 is the Gödel number of the sentence Y! This proves that if Y is true, then its Gödel number n*52 belongs to .
b. Conversely, suppose n*52 belongs to . Then n belongs to *, hence A = t is true, which means that Y is true. And so if the Gödel number of Y is in , then Y is true, or what is the same thing, if Y is false, then its Gödel number does not belong to .
According to argument a and argument b, we see that if Y is true, then its Gödel number is in and if Y is false, then its Gödel number is not in . And so Y is a Gödel sentence for .
5 · Let A compute . Then BNA computes ’, where B is the bluebird and N is the negation bird. Reason: For any number n, BNA = N(A). If n belongs to ’ then n doesn’t belong to , hence A = f, hence N(A) = t, so BNA = t. If n doesn’t belong to ’, then n belongs to , hence A = t, hence N(A) = f, and so BNA = f. Therefore BNA computes ’.
6 · There certainly cannot be any Gödel sentence Y for the set ’, because if Y is true, then its Gödel number is in , not in ’, and if Y is false, its Gödel number is in ’, not in . Therefore there is no Gödel sentence for ’.
Now, if were computable, then ’ would be computable by Problem 5, hence by Problem 4 there would be a Gödel sentence for ’. Since there is no Gödel sentence for ’, then the set is not computable.
Epilogue
Inspector Craig arrived home not long afterward, and the first thing he did (after solving the case of the bat and the Norwegian maid) was to spend a long holiday weekend with his old friends McCulloch and the logician Fergusson.* He told them the entire story of his summer adventures.
“I have known nothing about combinatory logic till now,” said McCulloch, “and I must say that the subject intrigues me enormously. But I would like to know how, when, and why the field ever got started. What was the motivation, and are there any practical applications?”
“Many,” replied Fergusson (who was quite knowledgeable about all this). “Why, these days combinatory logic is one of the big things in computer science and artificial intelligence. The study of combinators started early in the twenties, pioneered by Shonfinkel. It is curious that schön in German means “beautiful,” and finkel means “bird,” hence Shönfinkel means “beautiful bird.” So perhaps there’s been a connection between birds and combinators all along! At any rate, the subject was further developed by Curry, Fitch, Church, Kleene, Rosser, and Turing, and in later years by Scott, Seldin, Hindley, Barandregt, and others. Their interests were purely theoretical; they were exploring the innermost depths of logic and mathematics. No one then could have dreamed of the impact the subject would one day have on computer science. In recent times, the subject has been put on a more solid foundation—largely through the efforts of the logician Dana Scott, who provided interesting models for the theory.”
“How is combinatory logic related to computer science?” asked Craig. “Professor Griffin didn’t say too much about that.”
“Why, in the constr
uction of programs,” replied Fergusson. “Computers run on programs, you know, and these days all computer programs can be written in terms of combinators. The essential idea is that, given any programs X and Y, we can obtain a new program by feeding Y as input to the computer whose program is X; the resulting output is the program XY. The situation is analogous to calling out the name of one of Griffin’s birds y to a bird x and getting the name of the bird xy as a response. The analogy is quite exact: Just as all combinatorial birds are derivable from the two birds S and K, so are all computer programs expressible in terms of the basic combinators S and K. We have here a case of what mathematicians call isomorphism, which in this instance means that the birds of Griffin’s forest can be put into a one-to-one correspondence with all computer programs in such a manner that if a bird x corresponds to a program X and a bird y corresponds to a program Y, then the bird xy will correspond to the program XY. This is what Griffin must have meant when he said that, given any computer, there is a bird in his forest which can match it.
“I can certainly see,” concluded Fergusson, “why Griffin has no need of computers: Because of the isomorphism of his forest of birds to the class of computer programs, it follows that any information a computer scientist can obtain from running his programs, Griffin can get just as surely by interrogating his birds. And yet Griffin’s ideals seem to contrast strangely with those of people working in artificial intelligence. The latter are trying to simulate the thinking of biological organisms. Griffin is now turning the tables by using biological organisms—birds, in this case—to do the work of clever mechanisms. I believe the two approaches cannot but supplement each other, and it should be extremely interesting to see the outcome of all this!”
Many years later, Craig did indeed return to the Master Forest. But that is another story.
* A complete account of McCulloch’s remarkable number machines and Fergusson’s logic machines can be found in The Lady or the Tiger? (Alfred A. Knopf, 1982).
Who’s Who Among the Birds
Bluebird Bxyz = x(yz)
Cardinal Cxyz = xzy
Dove Dxyzw = xy(zw)
Eagle Exyzwv = xy(zwv)
Finch Fxyz = zyx
Goldfinch Gxyzw = xw(yz)
Hummingbird Hxyz = xyzy
Identity bird Ix = x
Jay Jxyzw = xy(xwz)
Kestrel Kxy = x
Lark Lxy = x(yy)
Mockingbird Mx = xx
Owl Oxy = y(xy)
Queer bird Qxyz = y(xz)
Quixotic bird Q1xyz = x(zy)
Quirky bird Q3xyz = z(xy)
Robin Rxyz = yzx
Sage bird θx = x(θx)
Starling Sxyz = xz(yz)
Thrush Txy = yx
Turing bird Uxy = y(xxy)
Vireo Vxyz = zxy
Warbler Wxy = xyy
Converse warbler W1xy = yxx
Starred Birds
Cardinal once removed C*xyzw = xywz
Cardinal twice removed C**xyzwv = xyzvw
Warbler once removed W*xyz = xyzz
Warbler twice removed W**xyzw = xyzww
Derivations of Certain Birds from Others
From B
Dove Eagle
BB B(BBB)
From B and T
Robin BBT
Cardinal RRR—also B(T(BBT))(BBT).
Finch ETTET—also B(TT)(B(BBB)T).
Vireo BCT—also CF.
Queer bird CB
Quixotic bird BCB
Quirky bird BT
Goldfinch BBC
From B, T, and M
Double mockingbird BM
Lark QM
Warbler C(BMR)
Converse warbler BMR—also CW.
Hummingbird BW(BC)
Starling B(BW)(BBC)—also BW*G.
Owl QQW—also BWQ and SI.
Turing bird LO—also L(SI).
Starred Birds
C* BC
C** BC*
W* BW
W** BW*
Some Sage Birds
BML LO(LO) BM(BWM)
Q(QM)M W(QL(QL)) BM(RMB)
SLL W(M(QL)) BM(CBM)
UU WS(BWB)
To Mock a Mocking Bird Page 20