[FOM] Question on Ordinal Notation

Dmytro Taranovsky 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.

Dmytro Taranovsky

More information about the FOM mailing list