Эта публикация цитируется в
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