Изменения
→Главная нумерация
Собственно, то, что с помощью главной нумерации мы можем легко получать номер композиции двух программ и является преимуществом главной нумерации относительно других.
Приведем пример вычислимой нумерации множества , не являющейся главной. Для этого достаточно сделать так, чтобы нигдене определённая функция имела единственный номер. Пусть <tex> \mathbb{Q}U(n,x)</tex>- произвольная вычислимая универсальная функция. Для этого упорядочим все дробиТеперь возьмем перечислимое множество <tex>D</tex> всех <tex>U</tex>-номеров всех функций таких, образующие все что их область определения непуста. Пусть функция <tex>d</tex> есть всюду определенная функция перечисляющая множество <tex> \mathbbD</tex>. Рассмотрим функцию <tex>V(i, x)</tex>, для которой <tex>V(0, x)</tex> не определено ни при каком <tex>x</tex>, а <tex>V(i+1, x) = U(d(i), x)</tex>. То есть, функция <tex>V_0</tex> нигде не определена, а функция <tex>V_{i+1}</tex> совпадает с <tex>U_{Qd(i)}</tex> по неубыванию суммы числителя . Очевидно, функция <tex>V</tex> вычислима и знаменателя. В случае равенства упорядочим универсальна (по увеличению числителяпостроению), а единственным <tex>V</tex>-номером нигде не определённой функции является число <tex>0</tex>. Полученная Тогда нумерация, очевидно, вычислимасоответствующая этой функции является неглавной.
== Литература ==
