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

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

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

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

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

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

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

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

${\displaystyle \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 }$.

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

Теореми

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

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

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

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

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

Див. також

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

Література

Українською

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