src/CCL/ex/Nat.thy
author paulson
Mon Dec 07 18:26:25 1998 +0100 (1998-12-07)
changeset 6019 0e55c2fb2ebb
parent 3837 d7f033c74b38
child 17456 bcf7544875b2
permissions -rw-r--r--
tidying
clasohm@1474
     1
(*  Title:      CCL/ex/nat.thy
clasohm@0
     2
    ID:         $Id$
clasohm@1474
     3
    Author:     Martin Coen, Cambridge University Computer Laboratory
clasohm@0
     4
    Copyright   1993  University of Cambridge
clasohm@0
     5
clasohm@0
     6
Programs defined over the natural numbers
clasohm@0
     7
*)
clasohm@0
     8
clasohm@0
     9
Nat = Wfd +
clasohm@0
    10
clasohm@0
    11
consts
clasohm@0
    12
clasohm@0
    13
  not              :: "i=>i"
clasohm@0
    14
  "#+","#*","#-",
clasohm@0
    15
  "##","#<","#<="  :: "[i,i]=>i"            (infixr 60)
clasohm@0
    16
  ackermann        :: "[i,i]=>i"
clasohm@0
    17
clasohm@0
    18
rules 
clasohm@0
    19
clasohm@0
    20
  not_def     "not(b) == if b then false else true"
clasohm@0
    21
wenzelm@3837
    22
  add_def     "a #+ b == nrec(a,b,%x g. succ(g))"
wenzelm@3837
    23
  mult_def    "a #* b == nrec(a,zero,%x g. b #+ g)"
wenzelm@3837
    24
  sub_def     "a #- b == letrec sub x y be ncase(y,x,%yy. ncase(x,zero,%xx. sub(xx,yy))) 
clasohm@1149
    25
                        in sub(a,b)"
wenzelm@3837
    26
  le_def     "a #<= b == letrec le x y be ncase(x,true,%xx. ncase(y,false,%yy. le(xx,yy))) 
clasohm@1149
    27
                        in le(a,b)"
clasohm@0
    28
  lt_def     "a #< b == not(b #<= a)"
clasohm@0
    29
clasohm@1149
    30
  div_def    "a ## b == letrec div x y be if x #< y then zero else succ(div(x#-y,y)) 
clasohm@1149
    31
                       in div(a,b)"
clasohm@0
    32
  ack_def    
clasohm@1149
    33
  "ackermann(a,b) == letrec ack n m be ncase(n,succ(m),%x. 
wenzelm@3837
    34
                          ncase(m,ack(x,succ(zero)),%y. ack(x,ack(succ(x),y))))
clasohm@1149
    35
                    in ack(a,b)"
clasohm@0
    36
clasohm@0
    37
end
clasohm@0
    38