У кожній універсальній алгоритмічній системі повинен існувати універсальний алгоритм еквівалентний довільному, наперед заданому алгоритму.
Для системи НАМ і МТ такий алгоритм існує.
Означення універсальної функції
Часткову -місну функцію називають універсальною для сім'ї δ всіх -місних часткових функцій, якщо виконуються наступні умови:
- Для кожного фіксованого числа , n-місна функція належить δ.
- Для кожної функції з δ, існує таке число , що для всіх справедливе співвідношення:
Іншими словами, функція є універсальною для сім'ї δ, якщо всі функції з δ можна розташувати у наступній послідовності:
.
Число називають номером функції .
Теореми
У теорії рекурсивних функцій доведені наступні теореми:
Теорема 1. Для всіх системи всіх -місних примітивно-рекурсивних функцій не містить примітивно-рекурсивної універсальної функції.
Теорема 2. Система всіх -місних загально-рекурсивних функцій не містить загально-рекурсивної універсальної функції
Теорема 3. Для кожного клас всіх -місних примітивно-рекурсивних функцій містить -місну загально-рекурсивну універсальну функцію.
Теорема 4. Для кожного існує частково-рекурсивна функція універсальна для класу всіх -місних частково-рекурсивних функцій.
Див. також
Література
- Українською