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

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

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

Означення універсальної функціїРедагувати

Часткову  -місну функцію   називають універсальною для сім'ї δ всіх  -місних часткових функцій, якщо виконуються наступні умови:

  1. Для кожного фіксованого числа  , n-місна функція   належить δ.
  2. Для кожної функції   з δ, існує таке число  , що для всіх   справедливе співвідношення:

 

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

 .

Число   називають номером функції  .

ТеоремиРедагувати

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

Теорема 1. Для всіх   системи всіх  -місних примітивно-рекурсивних функцій не містить примітивно-рекурсивної універсальної функції.

Теорема 2. Система всіх  -місних загально-рекурсивних функцій не містить загально-рекурсивної універсальної функції  

Теорема 3. Для кожного   клас всіх  -місних примітивно-рекурсивних функцій містить  -місну загально-рекурсивну універсальну функцію.

Теорема 4. Для кожного   існує частково-рекурсивна функція   універсальна для класу всіх  -місних частково-рекурсивних функцій.

Див. такожРедагувати

ЛітератураРедагувати

Українською
  • Л. М. Клакович, С. М. Левицька. Теорія алгоритмів: Навчальний посібник. — Друге видання, доповнене. — Львів : Видавничий центр ЛНУ ім. Івана Франка, 2015. — 161 с. — ISBN 9786171002302.