When is every recursive linear ordering of type μ recursively isomorphic to a polynomial time linear ordering over the natural numbers in binary form?
Jeffrey B. Remmel · Birkhäuser Boston eBooks · 1990
The main purpose of this paper is to answer a question raised by Grigorieff in [4]. In [4], Grigorieff proved that every infinite recursive linear ordering L is isomorphic to realtime linear ordering L ′ whose universe is the binary representation of the natural numbers. Grigorieff’s proof involved two steps. First he showed that if a recursive linear ordering L has the property that L has a recursive sequence S = s 0 L u 1 > L … such that U is coinitial in L or U has an infimum in L , then L is recursively isomorphic to a realtime linear ordering L ′ whose universe is the binary representation of the natural numbers. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.