Cтраница 1
Нумерации семейства 35, сводимые к нумерации а, называются а-вычисли-мыми. Семейство 35 называется а-вычислимым, если оно обладает хотя бы одной а-вычислимой нумерацией. [1]
Таким образом, нумерационные эквивалентности вычислимых нумераций семейств р.п.м. имеют класс V3 по классификации Клини. F ( х, г /, и) 0), или вид fix fiy 4Ф VM ( F ( я, г /, и) 0), где F ( х, у, и) - подходящая о.р.ф. В первом случае совокупность пар я, z /), для которых fix - fiy, рекурсивно перечислимая и нумерация Р называется позитивной. Во втором случае нумерация Р называется негативной. При негативной нумерации рекурсивно перечислимой оказывается совокупность пар ( х, z /), для которых fix fiy. Нумерация Р разрешимая, если она одновременно позитивная и негативная. [2]
С другой стороны, теорема 6.1 очевидным путем переносится на любые вычислимые нумерации вычислимых семейств функций, а теорема 6.2 непосредственно переносится на главные нумерации любых проективных семейств функций. [3]
Разумеется, теорема 17 была бы прямым следствием теоремы 16, если бы было показано, что каждая главная нумерация со-плотного семейства эффективно главная. [4]
Инвариантность множества всех вполне перечислимых систем относительно перехода к эквивалентным нумерациям позволяет рассматривать структуру указанного множества в качестве характеристики заданной нумерации семейства. [5]
С другой стороны, теорема 6.1 очевидным путем переносится на любые вычислимые нумерации вычислимых семейств функций, а теорема 6.2 непосредственно переносится на главные нумерации любых проективных семейств функций. [6]
Поэтому все вычислимые нумерации семейств общерекурсивных функций негативны. Обычная нумерация семейства всех п.р.ф. [3] может служить типичным примером неразрешимой негативной нумерации. [7]
Если рекурсивно перечислимое множество А есть совокупность значений функции К ( п х) для некоторого п, то число п назовем постовским номером множества А и обозначим А пп пп. У - семейство всех рекурсивно перечислимых множеств, называется постовской нумерацией семейства ЗР. [8]
Однако подобного рода нумерации можно строить не только для систем всех ч.р.ф. или рекурсивно перечислимых множеств ( р.п.м.), но и для некото рых частей этих систем. В связи с изложенным, А. Н. Колмогоровым ( см. [3]) была выдвинута программа систематического изучения свойств вычислимых нумераций семейств функций и множеств. [9]
Поэтому все вычислимые нумерации семейств общерекурсивных функций негативны. Обычная нумерация семейства всех п.р.ф. [3] может служить типичным примером неразрешимой негативной нумерации. [10]