Універсальна функція
Менш формально, для універсальної функції має виконуватися таке: «перетин» функції [math] U_n [/math] є функцією, що обчислюється, і всі обчислювані функції одного аргументу зустрічаються серед [math]U_n[/math] (звідси універсальність). Універсальна функція потрібна, наприклад, для того, щоб показати, що існує перерахована нерозв'язна множина (насправді це безліч таких [math] n [/math] , для яких [math] U(n, n) [/math] визначено) .
Аналогічно визначається універсальна функція для класу всюди певних обчислюваних функцій одного аргументу.
Універсальну функцію зручно представляти як інтерпретатор, якому на вхід подають функцію та її аргумент, а він виконує функцію на даному аргументі та повертає результат.
Зазначимо, що функція [math]u(n) = U(n, n)[/math] називається діагональною (звідси пішла назва методу).
За допомогою головної нумерації можна пронумерувати всі програми. Також, використовуючи головну нумерацію не складно визначити номер програми, що є композицією двох програм (тобто складається з двох підпрограм та основної функції, що повертає результат композиції вихідних програм). Нехай нам необхідно за номерами функцій [math]p[/math] та [math]q[/math] визначити номер функції-композиції [math]p[/math] та [math]q[/math]
Власне те, що за допомогою головної нумерації ми можемо легко отримувати номер композиції двох програм і є перевагою головної нумерації щодо інших.
Покажемо, що якби ця множина була розв'язана, то будь-яка перелічена множина була б розв'язана (що не так). Нехай [math]W-[/math] довільне перелічене нерозв'язне безліч. Введемо функцію [math]V[/math] від двох аргументів таку, що [math]V(n,x) = 0[/math] якщо [math] n \in W [/math], і невизначену інакше. Ця функція має перерізи двох типів: перетин є нульова функція, або ніде не певна функція. Оскільки [math] U [/math] відповідає головній нумерації, існує обчислювана всюди певна функція [math]s[/math] така, що [math]V(n, x) = U(s(n), x)[ /math] для будь-яких [math]n[/math] і [math]x[/math] , тобто [math]V_n = U_[/math].
Тоді при [math] n \in W [/math] значення [math]S_n[/math] є [math]U[/math] -номер нульової функції, інакше [math]U[/math] -номер ніде не визначеної функції. Тому якби безліч [math]U[/math] -номерів ніде не певної функції дозволялося б деяким алгоритмом, то застосовуючи цей алгоритм до [math]s(n)[/math] ми могли б дізнатися належність [math]n[/ math] до множини [math]W[/math] . Тобто безліч [math]W[/math] було б розв'язаним у протиріччі з нашим припущенням.
Також ми можемо зробити висновок, що ніде не певна функція має безліч номерів у будь-якій головній нумерації (множина номерів ніде не певної функції нерозв'язна, а будь-яка кінцева безліч можна розв'язати). А також відзначимо, що безліч номерів ніде не певної функції не тільки не можна розв'язати, а й не перерахувати. Його доповнення [math]-[/math] безліч усіх номерів усіх функцій з непустою областю визначення - перерахуємо (При обчисленні [math]U(n,x)[/math] для всіх [math]n, x[/math] ми можемо друкувати ті [math]n[/math] , котрим знайшло [math]x[/math] таке, що [math]U(n,x)[/math] визначено). А якщо доповнення нерозв'язної множини перелічимо, то саме безліч неперелічимо.
Тепер наведемо приклад нумерації, що обчислюється, яка не є головною. Для цього достатньо зробити так, щоб ніде не певна функція мала єдиний номер. Нехай[math]U(n,x)[/math] - довільна обчислювана універсальна функція. Тепер візьмемо безліч [math]D[/math] всіх [math]U[/math] -номерів усіх функцій таких, що їх область визначення непуста. Нехай функція [math]d[/math] є всюди певна функція перелічує безліч [math]D[/math]. Розглянемо функцію [math]V(i, x)[/math] , на яку [math]V(0, x)[/math] не визначено ні при якому [math]x[/math] , а [math]V (i+1, x) = U(d(i), x)[/math] . Тобто, функція [math]V_0[/math] ніде не визначена, а функція [math]V_[/math] збігається з [math]U_[/math]. Вочевидь, функція [math]V[/math] обчислювана і універсальна (по побудові), а єдиним [math]V[/math] -номером ніде не визначеної функції є число [math]0[/math] . Тоді нумерація, що відповідає цій функції, є неголовною.