RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2009, том 48, номер 5, страницы 564–579 (Mi al414)

Эта публикация цитируется в 11 статьях

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

М. В. Зубков

НИИ матем. мех. им. Н. Г. Чеботарёва, Казанский гос. ун-т, г. Казань, РОССИЯ

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

Ключевые слова: вычислимость, рекурсивность, линейный порядок, начальный сегмент.

УДК: 510.53+512.562

Поступило: 24.01.2008
Окончательный вариант: 20.03.2009


 Англоязычная версия: Algebra and Logic, 2009, 48:5, 321–329

Реферативные базы данных:


© МИАН, 2024