Аннотация:
Изучаются вычислимые линейные порядки с вычислимыми предикатами соседства или блока. В частности, доказывается существование вычислимого линейного порядка с вычислимым предикатом соседства, имеющего $\Pi^0_1$-начальный сегмент, который не изоморфен никакому вычислимому порядку с вычислимым предикатом соседства. С другой стороны, любой $\Sigma^0_1$-начальный сегмент такого порядка имеет вычислимую копию с вычислимым предикатом соседства.
Аналогичные результаты устанавливаются для вычислимых линейных порядков с вычислимым предикатом блока вместо отношения соседства. Кроме того, с использованием полученных результатов находится более простое доказательство теоремы Колеса, Доуни и Хусаинова о существовании вычислимого линейного порядка с $\Pi^0_2$-начальным сегментом, не имеющим вычислимой копии.