Рекурсивні функції: відмінності між версіями

Рекурсивні функції, виступаючи як еквівалент поняття ефективно рекурсивних функцій з моментамоменту їх введення піддавались інтенсивному дослідженюдослідженню.

Перш за все, в класі рекурсивних функцій були виделенівиділені та вивчені підкласи простіших функцій — примітивно рекурсивних, елементаринхелементарних за [[Кальмар Л.|Л. Кальмару]]. Доведено, що клас загальнорекурсивних функцій ширшеширший класакласу примітивно рекурсивний: існують загальнорекурсивні функції, що не є примітивно рекурсивними. Очевидно, що клас частково ширшеширший класу загальнорекурсивних функцій.

Де <math>\phi</math> і <math>f</math> — примітивно рекурсивні функції, тобто, для отримання будь-якої частково рекурсинвоїрекурсивної функції оператор &mu; можна застосувати не більше одного разу.

Робились спроби класифікації рекурсивних функцій. Класифікацію примітивно рекурсивних функцій здійснив польський математик А. Гжегорчик, а класифікацію, основаніосновану на понятті [[сводимістьзвідність|сводимостіЗвідності]] (в [[теорія алгоритмів|теорії алгоритмів]]), виконав американський математик [[Пост Еміль|Е. Пост]].

Доведено, що всі одномістніодномісні примітивно рекурсивні фукнціїфункції, і лише вони можуть бути отримані із функцій <math>s(x)</math>, <math>g(x)</math> скінченною кількістю операцій додавання, суперпозиції та ітерації.

Аналогічно, кожну загальнорекурсивну функцію можна отримати із функцій <math>s(x)</math>, <math>g(x)</math> скінченною кількістю операцій додавання суперпозиції та обернення, при чому останню виконують лише тоді, коли її результатом є всюди визначена функція. Якщо зняти це обмеження, тоді можна отримати всі одномістніодномісні частково рекурсивні функції.

де <math>F_{pr}</math>, <math>F_{cr}</math> та <math>F_{gr}</math> — множини всіх одномістниходномісних примітивно рекурсивних, частково рекурсивних та загальнорекурсивних функцій. Досліджувались найприродніші питання: наявність скінченних базисів, приклади підалгебр, описання максимальних підалгебр, тобто, таких підалгебр, які не містяться в жодних інших підалгебрах самих алгебр, [[ізоморфізм]]и та автоморфізми підалгебр, конгруеціїконгруенції на підалгебрах, питання скінченної визначеності алгебри, тощо.