[FOM] Generalizing Kleene's O

[Paul Budnik]

Kleene's O is a set of integers that encode effective notations for 
every recursive ordinal. From one of these integers, notations for all 
smaller ordinals are recursively enumerable and those notations can be 
recursively ranked. Kleene's formulation uses total recursive functions 
on the integers to define notations for limit ordinals. Its extensions 
can define limit ordinal notations using recursive functions that are 
total on nonrecursively enumerable countable domains such as Kleene's 
O.  This approach gives rise to a typed functional hierarchy of 
recursive functions.

Turing Machines (TM)  provide a convenient way to represent this. They 
can output two labels specifying the type of inputs accepted and the 
type of the notation based on  the  Gödel number of this TM when used as 
an input. This encodes the types in the Gödel number of the TM. After 
writing these type labels, the TM accepts an input of the specified type 
and computes an output.

One advantage of this approach over relative recursion or TMs with 
oracles is the ability to partially construct these recursive functional 
hierarchies in computer code as an aid to mathematical intuition. A 
first cut at developing this approach is described in 
http://www.mtnmath.com/ord/kleeneo.pdf This paper provides a convenient 
theoretical basis for expanding the ordinal calculator ( 
http://www.mtnmath.com/ord ). It also partially formalizes the 
philosophical concept of objective logically determined mathematics  in 
an always finite but potentially infinite universe (see 
http://www.cs.nyu.edu/pipermail/fom/2010-May/014792.html ).


Paul Budnik
www.mtnmath.com

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20110922/5b54110f/attachment.html>