Примитивни рекурсивна функция, математика, фендъм задвижвани от Wikia
определени права
Определението на примитивни рекурсивни функции е индуктивен. Състои се от уточняване клас от първоначалните примитивни рекурсивни функции и двама оператори (за замяна и примитивна рекурсия), което позволява да се изградят нови примитивни рекурсивни функции на базата на вече съществуващите.
Сред първите примитивни рекурсивни функции са функции на следните три типа:
- Нулевата функция на една променлива, определя всяко естествено число 0.
- наследник функция на една променлива, за асоцииране всяко естествено число непосредствено след естествено число за него.
- Функция, където наш променливи на асоцииране на всеки последователен набор от положителни числа числа на този комплект.
Операторите на заместване и примитивна рекурсия са определени, както следва:
- Нека е - примитивно рекурсивни функции на м променливи и G1. GM - подреден набор от примитивни рекурсивни функции на наш променливи всяка. Тогава в резултат на замяната на функциите GK с функция F е функция часа на наш променливи, възлага всеки последователен набор от цели числа, числа
- Нека е - примитивна рекурсивна функция на п променливи, и г - примитивна рекурсивна функция на N + 2 променливи. След това в резултат на прилагането на оператора да чифт примитивен рекурсия от е и г е функция на Н N + 1 от променлива типа
примери Редактиране
Нека посочим редица добре познати аритметични функции, които могат да бъдат считани за един примитивен рекурсивно.
- Добавянето на две числа може да се разглежда като примитив рекурсивна функция на две променливи, които са получени чрез прилагане на функции примитивен рекурсия оператор и е, вторият от които се получава чрез заместване на основните функции в основната функция:
- Размножаване на две числа може да се разглежда като примитив рекурсивна функция на две променливи, които са получени чрез прилагане на функции примитивен рекурсия оператор и е, вторият от които се получава чрез заместване на основните функции и добавяне на функцията:
- Симетричната разликата (абсолютна стойност на разликата) на две числа може да се разглежда като примитив рекурсивна функция на две променливи, които са получени чрез прилагане на следните замествания и примитивни рекурсии:
Границите на концепцията на закона
Всяко примитивен рекурсивна функция е рекурсивно. т. е. Водещ стойност, съответстваща на произволен брой аргументи на функцията набор от естествени числа. Съответно, рекурсивна функция. обща рекурсивни не са известни, че са свързани с броя на примитивни рекурсивни функции. Известен също рекурсивни функции, които не са примитивно рекурсивни. Стандартен пример е функцията Ackermann.
Трябва да се отбележи обаче, че произволно рекурсивна функция на п променливи могат да бъдат получени от примитивни рекурсивна функция на N + 1 променливи използват минимизира оператор.