Theory of Computation

1.7  RECURSIVE DEFINITIONS OF FUNCTIONS

We often encounter a definition of a function over the natural numbers such as

f (0, m) = 0

f (n + 1, m) = f (n, m) + m

Is this a legitimate definition? That is, is there really a function that satisfies the above two equalities for all n and m? And if so, is there only one such function, or is the definition ambiguous? We address this question in this section through a somewhat more general related question.

  1.7.0.24 Example. Let us look at a simpler question than the above and see if we can produce a good answer. First off, is there a function g given by the following two equalities for all values of n?

g(0) = 1

g(n + 1) = 2^g(n)

Well, let’s see: By induction on n we can show that g(n) ↓ for all n: Indeed, this is true for n = 0 by the first equality. Taking the I.H. that g(n) ↓ (for a fixed unspecified n) we can compute g(n + 1) so indeed

g(n) ↓ for all n

We can say then that the function g exists; right?

Wrong! A function is a set, in this case an infinite table of pairs (if we take its existence for granted). We did not show that it exists as a table of pairs; rather we have only shown that

If a g satisfying the given equalities exists, then it is total.⁴⁵

We can however prove that any two functions satisfying the equalities must be equal. That is, if h is another such function, then h = g or, on an input by input basis,

Note that we ...