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

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

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

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

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

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

$\varphi _{n}(i,x_{1},\dots ,x_{n})=f(x_{1},\dots ,x_{n})$

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

$\varphi _{n}(0,x_{1},\dots ,x_{n}),\varphi _{n}(1,x_{1},\dots ,x_{n}),\dots ,\varphi _{n}(i,x_{1},\dots ,x_{n}),\dots$.

Число $i$ називають номером функції $\varphi _{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$ існує частково-рекурсивна функція $\varphi _{n}^{n+1}(x_{0},x_{1},\dots ,x_{n})$ універсальна для класу всіх $n$-місних частково-рекурсивних функцій.

Див. також

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

Література

Українською

• Л. М. Клакович, С. М. Левицька. Теорія алгоритмів: Навчальний посібник. — Друге видання, доповнене. — Львів : Видавничий центр ЛНУ ім. Івана Франка, 2015. — 161 с. — ISBN 9786171002302.
• Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)