3 · Take d such that for all x and y, dxy = xty. We can specifically take d to be Tt, where T is the thrush. Then Ttxy = xty. The reader can verify that d is a disjunction bird by working out the four cases.
4 · Take i such that ixy = xyt. We can take i to be Rt, where R is the robin. The reader can verify that this bird i works.
5 · Take e to be such that for all x and y, exy = xy(Ny). We can take e to be CSN, where C is the cardinal, S is the starling, and N is the negation bird. The reader can easily verify that epq = p ↔ q.
24
Birds That Can Do Arithmetic
In this episode and the next, Craig found out the true wonders of Griffin’s forest.
Shortly before his departure, Craig visited Griffin in his study one late-summer day. The weather was beautiful, and all the windows of the study were open. Craig was quite surprised to see several birds perched on the windowsills engaged in lively conversation with Professor Griffin—all in bird language, of course. As the birds already there left, others would come.
“Ah yes!” said Griffin, after the last bird had departed. “I have been testing some of my arithmetical birds. Did you know that some of the birds here can do arithmetic?”
“Will you please explain that?” asked Craig.
“Well, I’d better start at the beginning,” replied Griffin. “We will work with the natural number series 0, 1, 2, 3, 4 … When I use the word ‘number’ I will always mean either 0 or one of the positive whole numbers. These numbers are called natural numbers. By the successor n+ of a number n, I mean n + 1. Thus 0+ = 1; 1+ = 2; 2+ = 3, and so forth.
“Now each number n is represented by some bird; I use the notation to mean the bird that represents n. Thus n is a number; is a bird—the bird that represents the number n. In the scheme I am about to show you for representing numbers by birds, the vireo V plays a major role: We will let σ be the bird Vf—which is V(KI)—and we will call σ the successor bird. For , we take the identity bird I. We take to be the bird σ; to be σ; to be σ, and so forth. Hence = I; = σ; = σ(σ); = σ(σ(σ)), and so forth. Thus = I; = VfI; = Vf(VfI); = Vf(Vf(VfI)), and so on.”
“Again, this choice strikes me as arbitrary,” said Craig. “What’s so special about the bird Vf?”
“You will see that shortly,” replied Griffin. “Actually there are many other possible choices. The first numerical scheme was proposed by Alonzo Church. The scheme I am using has several technical advantages over Church’s; the combinatorial logician Henk Barendregt is responsible for it. Anyway, I want to start explaining to you how birds here do arithmetic. First for some preliminaries:
“The birds , , , , and so on I call numerical birds—these are identified with the respective numbers 0, 1, 2, 3,… Now, if I call out a numerical bird to a bird A, A doesn’t necessarily respond by calling back a numerical bird; it might call back a nonnumerical bird. Well, a bird A is said to be an arithmetical bird of type 1 if for every numerical bird , the bird A is also a numerical bird. Loosely speaking, this means that A operating on a number gives you a number. A bird A is called an arithmetical bird of type 2 if for any numbers n and m, the bird A is a numerical bird. Equivalently, A is a numerical bird of type 2 if for every number n, the bird A is an arithmetical bird of type 1. Similarly, we define arithmetical birds of types 3, 4, 5, and so on. Thus, for example, if A is an arithmetical bird of type 4, then for any numbers a, b, c, and d, the bird A is a numerical bird.
“Now come some interesting things. There is a bird here called the addition bird, symbolized by , such that for any numbers m and n, is the sum of m and n—or rather, the numerical bird representing that sum. That is, = . Thus, for example, = ; = .
“Then we have a bird called a multiplication bird such that for any numbers n and m, is the bird . So, for example, = ; = .
“We also have an exponentiating bird such that for any numbers n and m, = , where k is the number nm—the result of multiplying n by itself m times. So, for example, = ; = ; = ; = .
“Having these birds,” continued Griffin,” we can easily combine them to form any arithmetical combination we want. For example, we can find a bird A such that for any numbers a, b, and c, A = , where d, say, is (3a2b + 4ca)5 + 7.
“In fact,” continued Griffin, in growing excitement, “given any numerical operation that can be performed by one of these modern electronic computers, there is a bird here that can perform the same operation! For any computer, there is a bird here that can match it!
“Do you realize what this means?” asked Griffin, waxing more excited still. “It means that the birds here could totally take over the job of the computers. Maybe one day the computers of the world will one by one be replaced by birds until there are no computers left—only birds! Wouldn’t that be a beautiful world?”
Craig thought this idea somewhat visionary, but intriguing, nevertheless.
“All this sounds most interesting,” said Craig, “but I am in the dark as to how you find even the basic arithmetic birds that add, multiply, and exponentiate. What birds are they?”
“I am coming to that,” replied Griffin, “but first for some preliminaries.”
• 1 •
“To begin with,” said Griffin, “we should be sure that the birds , , , ,… are all distinct—that is, for any numbers n and m, if n ≠ m, meaning n is unequal to m, then the bird is distinct from the bird . Can you see how to prove this?”
2 • The Predecessor Bird P
“For any positive number n,” said Griffin, “by its predecessor n− is meant the next lower number. That is, for any positive n, n− is the number n - 1. Of course, for any number n, the number n+ is positive and the predecessor of n+ is n.
“What we now need,” said Griffin, “is a bird that calculates predecessors. That is, we want a bird P such that for any number n, P = . Can you see how to find such a bird P?”
• 3 •
“We recall the propositional birds t and f. We now need a bird Z called a Zero-tester such that if is called out to Z, you will get the response t—meaning, ‘True, the number you called is 0’—whereas if you call out any number other than 0, you will get the response f—meaning, ‘False, the number is not 0.’ That is, we want a bird Z such that Z = t, but for any positive number n, Z = f. Can you find such a bird Z?”
• 4 •
“Let me ask you a question,” said Griffin. “Do you have any reason to believe that there is a bird A such that for any number n and any birds x and y, if n = 0, then Axy = x, but if n is positive, Axy = y? That is, is there a bird A such that Axy = x; Axy = y; Axy = y; Axy = y; and so forth?”
“Oh, of course!” replied Craig, after a moment’s thought.
How did Craig realize this?
“And now,” said Griffin, “we come to some of the more interesting birds. Before we consider the problem of finding an addition bird, let us consider a slightly simpler problem. Let us take any particular number—say 5. How can we find a bird A that adds 5 to any number that you call to it? That is, we want a bird A such that A = ; A = ; A = —and for any number n, A = .”
Craig thought about this, but could not find a solution.
“The idea is based on a principle known as the recursion principle,” said Griffin. “Suppose A is a bird such that the following two conditions hold:
1. A =
2. For every number n, A = σ(A).
“Do you see that such a bird A would do the required job?”
“Let us see now,” said Craig. “It is given that A = . What about A? Well, by the second condition, A = σ(A) = σ, since A = , and σ = . Therefore A = . Now that we know that A = , it follows that A = , because A = σ(A) = σ = . Yes, of course I see why it is that for every number n, A = . We successively prove A = , A = , A = , A = , and so forth!”
“Good!” said Griffin. “You have grasped the recursion principle.”
“I am still in the dark, though, about how one finds a bird A satisfying those conditions,” said Craig. “How does one
?”
“Ah, that’s the clever part,” said Griffin with a smile. “It is based on the fixed point principle, which I have already explained to you.”
“Really!” said Craig in amazement. “I can’t see any connection between the two!”
“I will now explain,” said Griffin. “First of all, do you see that Condition 2 can be alternately described as follows?
2’. For every number n greater than 0, A = σ(A(P)).”
“Yes,” said Craig, “because for any number n greater than zero, n = m +, where m is the predecessor of n. Therefore Condition 2’ says that = σ(A()), but since = , then Condition 2’ simply says that = σ(A()), or what is the same thing, A = σ(A(P)). But, of course, this holds only when n is positive.”
“Good!” said Griffin. “And so you see that what we want is a bird A such that A = if n = 0, and A = σ(A(P)) if n ≠ 0.”
“I see that,” said Craig.
“Well, we use the zero-tester Z,” said Griffin. “The bird Z(σ(A(P))) is if n = 0, and is σ(A(P)) if n ≠ 0, and so we want a bird A such that for every number n, A = Z(σ(A(P))). Well, by the fixed point principle, there is such a bird A—in fact, there is a bird A such that for any bird x, whether a numerical bird or not, Ax = Zx(σ(A(Px))). That solves the problem!
“In case you have forgotten,” added Griffin, “we can obtain the bird A by first taking a bird A1 such that for any birds x and y, A1yx = Zx(σ(y(Px))), and then you can take for A any bird of which A1 is fond—for example, we can take LA1(LA1) for A.”
“That is indeed clever!” said Craig in genuine admiration. “Who thought of it?”
“The idea of using the fixed point principle to solve problems like this is attributable to Alan Turing—the same logician who discovered the Turing bird. Turing has done some extremely clever things!”
• 5 •
“Of course,” said Griffin, “the number 5 has no special significance; I could have taken, say, 7, and asked for a bird A such that for all n, A = . However, we want something better than that. We want an arithmetic bird of type 2 such that for any two numbers n and m, = . Only a slight modification of what I have shown you is necessary. Can you see how to find such a bird ?”
• 6 •
“Next, can you see how to find a bird such that for any numbers n and m, = ? Of course, you are free to use the bird that you have just found.”
• 7 •
“Now that we have the birds and , can you find an exponentiating bird such that for any numbers n and m, = , where k = nm?”
PREPARATION FOR THE FINALE
“I understand you must leave this forest in a couple of days. Is that correct?” asked Griffin.
“Alas, yes!” replied Craig. “I have been called back home on a strange case involving a bat and a Norwegian maid.”
“That does sound strange!” remarked Griffin. “At any rate, tomorrow I would like to tell you one of the most interesting facts of all about this forest. This fact is related to Gödel’s famous incompleteness theorem, as well as to some results discovered by Church and Turing. But today, I must give you the necessary background. I must tell you more about arithmetical birds as well as something about property birds and relational birds.”
“What are they?” asked Craig.
• 8 •
“Well, by a property bird is meant a bird A such that for any number n, the bird A is a propositional bird—one of the two birds t or f. A set S of numbers is said to be computable if there is a property bird A such that A = t for every n in the set S, and A = f for every n not in the set S. Such a bird A is said to compute the set S. And a set S is called computable if there is a bird A that computes it.
“The nice thing about a computable set S is that given any number n, you can find out whether n belongs to the set or whether it doesn’t; you just go over to the bird A, which computes S, and call out . If A responds by calling out t, you know that n is in the set S; if A calls out f, you know that n is not in the set S.
“As an example, the set E of all even numbers is computable—there is a bird A such that A = t; a = f; A = t; A = f; and for every even number n, A = t, whereas for every odd number n, A = f. Can you see how to find A? You might try using the fixed point principle.”
9 • The Bird g
“By a relational bird—or more properly, a relational bird of degree 2—is meant a bird A such that for any numbers a and b, A = t or A = f.
“You are probably familiar with the symbol >, meaning ‘greater than,’ ” continued Griffin. “For any numbers a and b, we write a > b to mean that a is greater than b—so, for example, 8 > 5 is true; 4 > 9 is false; also 4 > 4 is false. We now need a relational bird that computes the relation ‘is greater than’—that is, we need a bird g such that for any numbers a and b, if a > b, then g = t, but if a ≤ b, meaning that a is less than or equal to b, then g = f. Can you see how to find such a bird?
“This is a bit tricky,” Griffin added, “so I had best point out the following facts. The relation a > b is the one and only relation satisfying the following conditions, for any numbers a and b:
1. If a = 0, then a > b is false.
2. If a ≠ 0, then:
a. If b = 0, then a > b is true.
b. If b ≠ 0, then a > b is true if and only if (a - 1) > (b - 1).
“Now, using the fixed point principle, do you see how to find the bird g?”
10 • The Minimization Principle
“Now comes an important principle known as the minimization principle,” said Griffin.
“Suppose that A is a relational bird such that for every number n, there is at least one number m such that A = t. Such a relational bird is sometimes called regular. If A is regular, then for every number n there is obviously the smallest number k such that A = t. Well, the minimization principle is that given any regular relational bird A, there is a bird A’, called a minimizer of A, such that for every number n, A’ = , when k is the smallest number such that A = t. So, for example, if A = f and A = f and A = f, but A = t, then A’ = 3. Can you see how to prove the minimization principle?”
Craig thought about this for some time.
“I’d better give you some hints,” said Griffin. “Given a regular bird A, first show how to find a bird A1 such that for all numbers n and m, the following two conditions hold:
1. If A = f, then A1 = A1
2. If A = t, then A1 = .
“Then take A’ to be CA1, where C is the cardinal, and show that A’ is a minimizer of A.”
11 • The Length Measurer
“By the length of a number n,” said Griffin, “we mean the number of digits in n, when n is written in ordinary base 10 notation. Thus the numbers from 0 to 9 have length 1; those from 11 to 99 have length 2; those from 100 to 999 have length 3, and so forth.
“We now need a bird l that measures the length of any number—that is, we want l to be such that for any number n, l = , when k is the length of n. So, for example, l = 1; l = ; l = . Can you see how to find the bird l?”
Craig thought about this for some time. “Ah!” he finally said. “I get the idea! The length of a number n is simply the smallest number k such that 10k > n.”
“Good!” said Griffin.
With this, the reader should have no trouble finding the bird l.
12 • Concatenation to the Base 10
“Now for the last problem of today,” said Griffin. “For any numbers a and b, by a*b we mean the number which, when written in base 10 notation, consists of a in base 10 notation, followed by b in base 10 notation. For example, 53*796 = 53796; 280*31 = 28031.”
“That’s a curious operation on numbers!” said Craig.
“It is an important one, as you will see tomorrow,” replied Griffin. “This operation is known as concatenation to the base 10. And now we need a bird that computes this operation—that is, we want to be such that for any numbers a and b, = . So you see how to find such a bird?”
SOLUTIONS
1 · We fir
st show that is different from all the birds , , ,… ,…
Well, suppose there were some number n such that = . Then I = Vf. Then IK = VfK = Kf = f. Hence we would have K = KI, since IK = K and f = KI, but we already know that K ≠ KI. Therefore ≠ .
We must next show that for any numbers n and m, if . = , then m = n. Well, suppose that = .. Then Vf = Vf. Hence Vff = Vff, so ff = ff, hence = , since ff = and ff =
Now that we know that ≠ . and that for every n and m, if = . then n = m, the proof that all the birds , , ,…, ,… are distinct proceeds exactly as in the solution to Problem 19, Chapter 22.
2 · Take P to be Tf, where T is the thrush and f is the bird KI, as in the last chapter. Then for any number n, P = Tf = f = Vff = ff = .
3 · Take Z to be Tt; T is the thrush, and t is the truth bird K. Then:
1. Z = TtI = It = t. So Z = t.
2. Now take any number n. Then Z = Tt = t = Vft = tf = f.
Note: Under the particular scheme used by Griffin for representing numbers by birds, the birds σ, P, and Z are relatively easy to find. This is the technical advantage to which Griffin referred. Any other scheme that would yield a successor bird, a predecessor bird, and a zero-tester would also work.
4 · The zero-tester Z is such a bird A! Reason: Zxy = txy, since Z = t, and txy = x, so Zxy = x. But for any n ≠ 0, Z = f, hence Zxy = fxy = y.
5 · The addition operation + is uniquely determined by the following two conditions, for any numbers n and m:
1. n + 0 = n
2. n + . = (n + m)+. That is, n plus the successor of m is the successor of n + m.
To Mock a Mocking Bird Page 18
