Рекурсивна функция (теория на изчислимостта)
Срок рекурсивна функция в теорията на изчислимостта се използва за означаване на три класа функции:
Последните съвпадат с класа на изчислимите функции на Тюринг. Определенията на тези три класа са силно свързани. Те бяха въведени от Кърт Гьодел, за да формализира понятието за изчислимост.
Много частично рекурсивни функции включват много общи рекурсивни функции, а общите рекурсивни функции включват примитивни рекурсивни функции. Частично рекурсивните функции понякога се наричат просто рекурсивни функции.
Съдържание
Определение
Определение на понятието примитивна рекурсивна функция е индуктивен. Състои се от задаване на клас основни примитивни рекурсивни функции и два оператора (суперпозиция и примитивна рекурсия), позволявайки да се изграждат нови примитивни рекурсивни функции въз основа на съществуващите.
Основните примитивни рекурсивни функции включват функции от следните три типа:
Операторите на заместване и примитивна рекурсия се дефинират както следва:
Много примитивни рекурсивни функции Е минимален набор, съдържащ всички основни функции и затворен под посочените оператори на заместване и примитивна рекурсия.
По отношение на императивното програмиране, примитивните рекурсивни функции съответстват на програмни блокове, в които се използват само аритметични операции, както и условен оператор и оператор на аритметичен цикъл (оператор на цикъл, в който броят на итерациите е известен в началото на цикъла ). Ако програмистът започне да използва оператора цикъл while, при който броят на итерациите не е известен предварително и по принцип може да бъде безкраен, тогава той преминава в класа на частично рекурсивните функции.
Нека посочим редица добре известни аритметични функции, които са примитивни рекурсивни.
Частично рекурсивна функция се дефинира подобно на примитивната рекурсия, само третият оператор се добавя към два оператора на суперпозиция и примитивна рекурсия - минимизиране на аргумента.