Эта публикация цитируется в
11 статьях
О начальных сегментах вычислимых линейных порядков с дополнительными вычислимыми предикатами
М. В. Зубков НИИ матем. мех. им. Н. Г. Чеботарёва,
Казанский гос. ун-т, г. Казань, РОССИЯ
Аннотация:
Изучаются вычислимые линейные порядки с вычислимыми предикатами соседства или блока. В частности, доказывается существование вычислимого линейного порядка с вычислимым предикатом соседства, имеющего
$\Pi^0_1$-начальный сегмент, который не изоморфен никакому вычислимому порядку с вычислимым предикатом соседства. С другой стороны, любой
$\Sigma^0_1$-начальный сегмент такого порядка имеет вычислимую копию с вычислимым предикатом соседства.
Аналогичные результаты устанавливаются для вычислимых линейных порядков с вычислимым предикатом блока вместо отношения соседства. Кроме того, с использованием полученных результатов находится более простое доказательство теоремы Колеса, Доуни и Хусаинова о существовании вычислимого линейного порядка с
$\Pi^0_2$-начальным сегментом, не имеющим вычислимой копии.
Ключевые слова:
вычислимость, рекурсивность, линейный порядок, начальный сегмент.
УДК:
510.53+
512.562 Поступило: 24.01.2008
Окончательный вариант: 20.03.2009