History log of /seL4-l4v-10.1.1/HOL4/examples/computability/primrecfnsScript.sml
Revision Date Author Comments
# 66d88b8c 29-Jul-2016 Michael Norrish <Michael.Norrish@nicta.com.au>

Fix computability thy's in light of pat_assum rename


# a2328149 23-Sep-2011 Anthony Fox <anthony.fox@cl.cam.ac.uk>

Adopt ML-style syntax for case expressions and use freed up "||" for bitwise-or. See issue #24.


# 88e3ff89 19-Apr-2011 Michael Norrish <Michael.Norrish@nicta.com.au>

Improved version of the 'Ackermann not p.r.' proof.

Nicer because it no longer has to use MAX, among other things.


# bd446296 14-Jan-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Export 'strong' primrec indn; and move num-list theorems back to prnlistTheory.


# 3277cf9e 14-Jan-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Moved Pr1 constant from prterm to primrecfns, allowing some simpler proofs.


# acabd2dd 05-Jan-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Show that "is an abstraction" and "is in beta-normal form" are prim rec.

In both case, these are computable functions over numbers encoding de
Bruijn terms.


# 01bf91f7 05-Jan-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Recast tri, invtri, npair, nfst and nsnd to use pr1 and pr2 lifiting functions.


# 14b89c51 04-Jan-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Use pr1 and pr2 "lifting" functions to remove need for some constants.

For example, pr_add is now (pr2 $+), and pr_mult is (pr2 $*). Haven't
quite finished this process (want to do the numeric pairing functions
similarly).


# 63570e67 03-Jan-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Start of an effort to lessen the need for explicit prim. rec definitions.

Instead, the theory is that I will show theorems like

|- primrec (pr2 $+) 2
|- primrec (pr2 $*) 2
|- primrec (pr2 $DIV) 2

and then I'll be able to use (pr2 $+) everywhere instead of pr_add,
saving on excess constants. Of course, to show the primrec theorems,
I will have to express the given functions using the primitive
recursive building blocks.


# 3a1a1979 01-Jan-2010 Michael Norrish <Michael.Norrish@nicta.com.au>

Prove that numeric pairing (via calculation of triangular numbers) is prim rec.


# be761bf3 06-Dec-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Prim. rec. functions now do something reasonable with lists of wrong size


# 6fdeb17f 05-Dec-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Recast theory to have the primitive recursive functions act on lists
of numbers, rather than single numbers encoding lists of numbers.


# f40eecb8 04-Dec-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Prove that div and mod are primitive recursive.


# 2572f382 20-Nov-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Add a comment attributing my Ackermann Proof (to Gregory Taylor).


# c86b76a5 20-Nov-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Complete proof that Ackermann's function grows faster than any
primitive recursive function.


# 568457f8 19-Nov-2009 Michael Norrish <Michael.Norrish@nicta.com.au>

Start of a theory of primitive recursive functions.
Almost finished proof that Ackermann's function is not prim. rec.