Начальные сегменты вычислимых линейных порядков с вычислимыми естественными отношениями

В работе изучается алгоритмическая сложность естественных отношений на начальных сегментах вычислимых линейных порядков. Доказано, что существует вычислимый линейный порядок с вычислимым отношением плотности такой, что его $\Pi^0_1$-начальный сегмент не имеет вычислимого представления с вычислимым отношением плотности. Получены аналогичные результаты для отношений предельности справа и предельности слева.