Універсальні рекурсивні функції

У кожній універсальній алгоритмічній системі повинен існувати універсальний алгоритм еквівалентний довільному, наперед заданому алгоритму.

Для системи НАМ і МТ такий алгоритм існує.

Означення універсальної функції

Часткову $(n+1)$-місну функцію ${\phi }_n(x_0,x_1,\dots ,x_n)$ називають універсальною для сім'ї δ всіх $n$-місних часткових функцій, якщо виконуються наступні умови:

1. Для кожного фіксованого числа $i$, n-місна функція ${\phi }_n(i,x_1,\dots ,x_n)$ належить δ.
2. Для кожної функції $f(x_1,\dots ,x_n)$ з δ, існує таке число $i$, що для всіх $x_1,\dots ,x_n$ справедливе співвідношення:

${\phi }_n(i,x_1,\dots ,x_n)=f(x_1,\dots ,x_n)$

Іншими словами, функція ${\phi }_n$ є універсальною для сім'ї δ, якщо всі функції з δ можна розташувати у наступній послідовності:

${\phi }_n(0,x_1,\dots ,x_n),{\phi }_n(1,x_1,\dots ,x_n),\dots ,{\phi }_n(i,x_1,\dots ,x_n),\dots$.

Число $i$ називають номером функції ${\phi }_n$.

Теореми

У теорії рекурсивних функцій доведені наступні теореми:

Теорема 1. Для всіх $n=1,2,\dots$ системи всіх $n$-місних примітивно-рекурсивних функцій не містить примітивно-рекурсивної універсальної функції.

Теорема 2. Система всіх $n$-місних загально-рекурсивних функцій не містить загально-рекурсивної універсальної функції $(n=1,2,\dots )$

Теорема 3. Для кожного $n=1,2,\dots$ клас всіх $n$-місних примітивно-рекурсивних функцій містить $(n+1)$-місну загально-рекурсивну універсальну функцію.

Теорема 4. Для кожного $n=1,2,\dots$ існує частково-рекурсивна функція ${\phi }_n^{n+1}(x_0,x_1,\dots ,x_n)$ універсальна для класу всіх $n$-місних частково-рекурсивних функцій.

Див. також

• Теза Черча
• Рекурсія
• Теорія обчислюваності
• Рекурсивна функція

Література

Українською

• Шаблон:Книга
• Шаблон:Роджерс.Теорія рекурсивних функцій