[FOM] Question on Ordinal Notation
fenner at cse.sc.edu
Mon Jun 27 13:08:26 EDT 2005
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
Email: fenner at cse.sc.edu
More information about the FOM