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

Алгебра и логика, 2018, том 57, номер 4, страницы 426–447 (Mi al857)

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

Некоторые абсолютные свойства $A$-вычислимых нумераций

С. А. Бадаевa, А. А. Исаховab

a Казахский национальный ун-т им. аль-Фараби, пр. аль-Фараби, 71, г. Алма-Ата, 050040, КАЗАХСТАН
b Казахстанско-Британский техн. ун-т, ул. Толе би, 59, г. Алма-Ата, 050000, КАЗАХСТАН

Аннотация: Для произвольного множества натуральных чисел $A$ доказываются следующие утверждения: любое конечное семейство $A$-вычислимых множеств с наименьшим по включению элементом имеет $A$-вычислимую универсальную нумерацию; любое бесконечное $A$-вычислимое семейство всюду определенных функций имеет с точностью до $A$-эквивалентности либо одну, либо бесконечно много $A$-вычислимых фридберговых нумераций; любое $A$-вычислимое семейство всюду определенных функций, содержащее предельную функцию, не имеет $A$-вычислимых универсальных нумераций даже относительно $A$-сводимости.

Ключевые слова: $A$-вычислимая нумерация, $A$-вычислимая фридбергова нумерация, $A$-вычислимая универсальная нумерация, $A$-сводимость.

УДК: 510.54

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

DOI: 10.17377/alglog.2018.57.402


 Англоязычная версия: Algebra and Logic, 2018, 57:4, 275–288

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


© МИАН, 2024