Ackermann' function was conceived in 1928 as a function
that cannot be computed with first-order primitive
recursion. It has type nat->nat->nat and is defined with
three equations.

(*

ack 0 n = S n

ack (S m) 0 = ack m 1

ack (S m) (S n) = ack m (ack (S m) n)

*)

The equations define a function since they are
exhaustive and terminating (either the first argument is
decreased, or the first argument stays the same and the
second argument is decreased). However, Coq will not accept
this definition since it is not by structural recursion.
But we can still use the equations to specify Ackermann's
function.

Definition ackermann f := forall m n,

f 0 n = S n /\

f (S m) 0 = f m 1 /\

f (S m) (S n) = f m (f (S m) n).

Proposition Equivalence: forall f g,

ackermann f -> ackermann g ->

forall m n, f m n = g m n.

Proof. intros f g F G.

induction m.

intro n. elim (F 0 n). elim (G 0 n). intuition. congruence.

induction n.

elim (F m 0). elim (G m 0). intuition. rewrite IHm in * |-. congruence.

elim (F m n). elim (G m n). intuition. rewrite IHm in * |-. congruence.

Qed.

Coq no knows when a procedure computes Ackermann's
function. But we still have to construct such a
procedure. To do, we take the specify equations and write a
recursive procedure acker that takes the first argument
and returns a recursive procedure that takes the second
argument.

Fixpoint acker m := match m with

| O => S

| S m => (fix acker' f n := match n with

| O => f 1

| S n => f (acker' f n)

end)

(acker m)

end.

Since both recursions are structural, Coq accepts this
definition. The proof that acker computes Ackermann's
function is straightforward.

Goal ackermann acker.

unfold ackermann. simpl. auto.

We now unfold the nested recursion into a stand-alone
procedure.

Fixpoint ack' f n := match n with

| 0 => f 1

| S n => f(ack' f n)

end.

Fixpoint ack m := match m with

| 0 => S

| S m => ack' (ack m)

end.

Note that the auxiliary procedure ack' is higher-order
(i.e., takes a procedure as argument.) The correctness
proof is again straightforward.

Goal ackermann ack.

unfold ackermann. simpl. auto.

We now formulate primitive recursion in Coq by
means of the function iter.

Fixpoint iter X (f:X->X) n x := match n with

O => x

| S n' => f(iter X f n' x)

end.

We will show that we can compute Ackermann with
iter (i.e., primitive recursion) and without further
structural recursion. We first show how iter can
compute ack and ack'.

Goal forall f n, ack' f n = iter nat f n (f 1).

induction n. reflexivity. simpl. rewrite IHn. reflexivity.

Goal forall n, ack n = iter (nat->nat) ack' n S.

induction n. reflexivity. simpl. rewrite IHn. reflexivity.

By inlining the iter formulation of ack' into the
iter formulation of ack we obtain a pure iter
formulation of the Ackermann function.

Goal ackermann (fun m => iter (nat->nat) (fun f n => iter nat f n (f 1)) m S).

unfold ackermann. simpl. auto.

We now know that Ackermann's function can be computed
with higher-order primitive recursion (the outer iter is
at nat->nat).

This page has been generated by coqdoc