src/HOL/ex/Primrec.thy

recdef requires theory Recdef;

(*  Title:      HOL/ex/Primrec
    ID:         $Id$
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1997  University of Cambridge

Primitive Recursive Functions

Proof adopted from
Nora Szasz, 
A Machine Checked Proof that Ackermann's Function is not Primitive Recursive,
In: Huet & Plotkin, eds., Logical Environments (CUP, 1993), 317-338.

See also E. Mendelson, Introduction to Mathematical Logic.
(Van Nostrand, 1964), page 250, exercise 11.

Demonstrates recursive definitions, the TFL package
*)

Primrec = Main +

consts ack  :: "nat * nat => nat"
recdef ack "less_than ** less_than"
    "ack (0,n) =  Suc n"
    "ack (Suc m,0) = (ack (m, 1))"
    "ack (Suc m, Suc n) = ack (m, ack (Suc m, n))"

consts  list_add :: nat list => nat
primrec
  "list_add []     = 0"
  "list_add (m#ms) = m + list_add ms"

consts  zeroHd  :: nat list => nat
primrec
  "zeroHd []     = 0"
  "zeroHd (m#ms) = m"


(** The set of primitive recursive functions of type  nat list => nat **)
consts
    PRIMREC :: (nat list => nat) set
    SC      :: nat list => nat
    CONST   :: [nat, nat list] => nat
    PROJ    :: [nat, nat list] => nat
    COMP    :: [nat list => nat, (nat list => nat)list, nat list] => nat
    PREC    :: [nat list => nat, nat list => nat, nat list] => nat

defs

  SC_def    "SC l        == Suc (zeroHd l)"

  CONST_def "CONST k l   == k"

  PROJ_def  "PROJ i l    == zeroHd (drop i l)"

  COMP_def  "COMP g fs l == g (map (%f. f l) fs)"

  (*Note that g is applied first to PREC f g y and then to y!*)
  PREC_def  "PREC f g l == case l of
                             []   => 0
                           | x#l' => nat_rec (f l') (%y r. g (r#y#l')) x"

  
inductive PRIMREC
  intrs
    SC       "SC : PRIMREC"
    CONST    "CONST k : PRIMREC"
    PROJ     "PROJ i : PRIMREC"
    COMP     "[| g: PRIMREC; fs: lists PRIMREC |] ==> COMP g fs : PRIMREC"
    PREC     "[| f: PRIMREC; g: PRIMREC |] ==> PREC f g: PRIMREC"
  monos      lists_mono

end