[FOM] Generalizing Kleene's O
Paul Budnik
paul at mtnmath.com
Thu Sep 22 13:23:16 EDT 2011
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>
More information about the FOM
mailing list