[FOM] Question on Ordinal Notation

[Stephen Fenner]

Dmytro Taranovsky <dmytro at MIT.EDU> wrote:

>Is there a canonical ordinal notation system up to the recursive omega_1
>such that every proper initial segment is polynomial time computable?
>

Yes.  Steven Homer did work on this a long time ago.  He showed that every 
constructive alpha < omega_1^CK is order-isomorphic to a polynomial-time 
computable binary relation on omega.  I'm not sure if he answered your 
exact question, but it is reasonably clear from his work.  Sorry that I 
don't have an exact reference.

>In fact, there are ordinal notation systems for the recursive omega_1
>with the comparison relation polynomial time computable when restricted
>to any proper initial segment. However, they seem to depend on arcane
>details of the chosen enumeration of recursive functions.

These questions must depend on details of enumeration.  Whether or not 
these details are "arcane" is debatable.

Stephen A. Fenner
Computer Science and Engineering Department
University of South Carolina
Columbia, SC  29208  USA
Phone: 803.777.2596
FAX:   803.777.3767
Email: fenner at cse.sc.edu
Web:   http://www.cse.sc.edu/~fenner