[FOM] Question on Ordinal Notation
dmytro at MIT.EDU
Sun Jun 26 11:09:01 EDT 2005
Is there a canonical ordinal notation system up to the recursive omega_1
such that every proper initial segment is polynomial time computable?
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.
More information about the FOM