Рекурсивная функция (теория вычислимости): различия между версиями

м
оформление, стилевые правки
м (оформление, стилевые правки)
'''Частично рекурсивная функция''' определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента.
 
* '''Оператор минимизации аргумента'''. Пусть <math>f</math> — функция от ''n&nbsp;'' натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции <math>f</math> называется функция <math>h</math> от <math>n-1</math>&nbsp;переменной, задаваемая следующим определением:
: <math>h(x_1,\ldots, x_{n-1}) = \min (y)</math>, при условии <math>f(x_1,\ldots,x_{n-1},\,y)=0</math>
: То есть функция <math>h</math> возвращает минимальное значение последнего аргумента функции <math>f</math>, при котором её значение равно 0.
 
В терминах [[Императивное программирование|императивного программирования]] — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также [[Оператор ветвления|условный оператор]] и оператор арифметического цикла ([[Цикл (программирование)|оператор цикла]], в котором число итераций известно на момент начала цикла). Если же программист начинает использовать оператор цикла <code>while</code>, в котором число итераций заранее неизвестно и, в принципе, может быть бесконечным, то он переходит в класс частично рекурсивных функций.
 
Частично рекурсивные функции для некоторых значений аргумента могут быть не определены, так как оператор минимизации аргумента не всегда корректно определён, так какпоскольку функция <math>f</math> может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и [[Исключение (программирование)|исключение]] или уход в бесконечный цикл, соответствующие неопределённому значению.
 
== Общерекурсивная функция ==<!-- используется для перенаправления [[Общерекурсивная функция]] -->