A discrete linear order with non-dense punctual degrees
Kai Jun Khoo, Heer Tern Koh, Keng Meng Ng · Theoretical Computer Science · 2025
This paper contributes to a systematic study of punctual structures , which are structures computable without delay. The (punctual) degree structure induced by treating “being primitive recursively isomorphic” as a reduction provides insight into the different speeds of enumerations of a given structure. In this paper, we work towards a classification of density of the punctual degrees for linear orders. More specifically, we construct a discrete linear order whose punctual degrees are not dense.