Изменения

С помощью главной нумерации можно пронумеровать все программы. Также, используя главную нумерацию не сложно определить номер программы, являющуюся композицией двух программ (то есть состоящей из двух подпрограмм и основной функции, возвращающей результат композиции исходных программ). Пусть нам необходимо по номерам функций <tex>p</tex> и <tex>q</tex> определить номер функции-композиции <tex>p</tex> и <tex>q</tex>{{Теорема|statement=Существует такая функция <tex>c</tex>, которая всюду определена и которая по номерам функций <tex>p</tex> и <tex>q</tex> дает номер <tex>c(p, q)</tex> их композиций. То есть выполняется свойство <tex>U(c(p,q),x) = U(p, U(q,x))</tex>|proof=Возьмем некоторую функцию <tex>V([p,q],x)=U(p, U(q,x))</tex>. Исходя из определения главной нумерации существует такая вычислимая, всюду определенная функция <tex>S: V(n,x)=U(s(n),x)</tex> для всех <tex>n</tex> и <tex>x</tex>. А тогда <tex>V([p,q],x)=U(S(p,q), x)</tex>, что значит функция с, определяемая как <tex>c(p,q)=S([p,q])</tex>, будет искомой.}}Отметим, что при доказательстве существования функции-композиции мы пользуемся основным свойством главной нумерации, а значит для неглавных нумерации мы не сможем построить такую функций и не сможем найти номер функции-композиции двух функций.