s
Section 5.4 Functions
407
c. Prove that c A (x) = 1 − c A′ (x).
d. Is it true that for any set S and any subsets A and B of S, c A c B (x) = c A (x) + c B (x)? Prove or give a
counterexample.
42. Ackermann’s function
1
, mapping N
2
to N, is a recursive function that grows very rapidly. It is given by
A(0, n) = n + 1 for all n [ N
A(m, 0) = A(m − 1, 1) for all m [ N, m > 0
A(m, n) = A(m − 1, A(m, n − 1)) for all m [ N, n [ N, m > 0, n > 0
a. Compute (show all steps) the value of A(1, 1).
b. Compute (show all steps) the value of A(2, 1).
c. The value of A(4, 0) = 13 = 2
2
2 − 3, still a small value. But A(4,1) = 2
2
2 2 − 3. Compute this value.
d. Write a likely expression for the value of A(4, 2).
43. Another rapidly growing function is the Smorynski function, which also maps N
2
to N. The definition is
S(0, n) = n
n
for all n [ N
S(m, n) = S(m − 1, S(m − 1, n)) for all m [ N, n [ N, m > 0
a. How does S(0, n) compare to A(0, n)? (See Exercise 40.)
b. Find (show all steps) an expression for the value of S(1, n).
c. A googolplex is a very large number, which if written in standard form (such as 1,000,000 … ), even
in 1-point font, would take more room to write than the diameter of the known universe. Look up the
definition of the googolplex and write it as S(m, n) for a specific value of m and n.
44. The Dwyer function also maps N
2
to N and grows very rapidly, but it has a closed-form definition:
D(m, n) = n! c
(2m + 1)!
2
m
m!
d
n
a. Compute the values of D(1, 1), D(2, 1), D(3, 1) and D(4, 1).
b. Verify that D(2, 1) = (2*1 + 3)D(1, 1), that D(3, 1) = (2*2 + 3)D(2, 1), and that D(4, 1) 5
(2*3 + 3)D(3, 1).
c. Verify that D(m, 1) satisfies the recurrence relation
D(m + 1, 1) = (2m + 3) D (m, 1) with D(0, 1) = 1
(Hint: When you evaluate D(m + 1, 1) and D(m, 1) do not divide the denominator factorial into the numerator factorial. Instead, think of the numerator factorial as a product of even and odd factors.
d. Find (use a spreadsheet) the smallest value of m for which
D(m, 1) < m
m
1 This is the most common of several versions of Ackermann’s function, all of which are recursive with extremely rapid growth rates. To watch the
tedious recursiveness of computations of Ackermann’s function, go to http://www. gfredericks.com/sandbox/arith/ackermann
Section 5.4 Functions
407
c. Prove that c A (x) = 1 − c A′ (x).
d. Is it true that for any set S and any subsets A and B of S, c A c B (x) = c A (x) + c B (x)? Prove or give a
counterexample.
42. Ackermann’s function
1
, mapping N
2
to N, is a recursive function that grows very rapidly. It is given by
A(0, n) = n + 1 for all n [ N
A(m, 0) = A(m − 1, 1) for all m [ N, m > 0
A(m, n) = A(m − 1, A(m, n − 1)) for all m [ N, n [ N, m > 0, n > 0
a. Compute (show all steps) the value of A(1, 1).
b. Compute (show all steps) the value of A(2, 1).
c. The value of A(4, 0) = 13 = 2
2
2 − 3, still a small value. But A(4,1) = 2
2
2 2 − 3. Compute this value.
d. Write a likely expression for the value of A(4, 2).
43. Another rapidly growing function is the Smorynski function, which also maps N
2
to N. The definition is
S(0, n) = n
n
for all n [ N
S(m, n) = S(m − 1, S(m − 1, n)) for all m [ N, n [ N, m > 0
a. How does S(0, n) compare to A(0, n)? (See Exercise 40.)
b. Find (show all steps) an expression for the value of S(1, n).
c. A googolplex is a very large number, which if written in standard form (such as 1,000,000 … ), even
in 1-point font, would take more room to write than the diameter of the known universe. Look up the
definition of the googolplex and write it as S(m, n) for a specific value of m and n.
44. The Dwyer function also maps N
2
to N and grows very rapidly, but it has a closed-form definition:
D(m, n) = n! c
(2m + 1)!
2
m
m!
d
n
a. Compute the values of D(1, 1), D(2, 1), D(3, 1) and D(4, 1).
b. Verify that D(2, 1) = (2*1 + 3)D(1, 1), that D(3, 1) = (2*2 + 3)D(2, 1), and that D(4, 1) 5
(2*3 + 3)D(3, 1).
c. Verify that D(m, 1) satisfies the recurrence relation
D(m + 1, 1) = (2m + 3) D (m, 1) with D(0, 1) = 1
(Hint: When you evaluate D(m + 1, 1) and D(m, 1) do not divide the denominator factorial into the numerator factorial. Instead, think of the numerator factorial as a product of even and odd factors.
d. Find (use a spreadsheet) the smallest value of m for which
D(m, 1) < m
m
1 This is the most common of several versions of Ackermann’s function, all of which are recursive with extremely rapid growth rates. To watch the
tedious recursiveness of computations of Ackermann’s function, go to http://www. gfredericks.com/sandbox/arith/ackermann