Рекурсивная функция

[Профессор Снэйп]

Xaositect в сообщении #298036 писал(а):

Надо для каждого $\mu$-оператора в описании функции доказать, что его значение всегда определено.

Кстати, это некорректное замечание.

Если каждый $\mu$-оператор в выводе функции даёт всюду определённую функцию, то функция, которая выводится, называется общерекурсивной. Рекурсивная же функция --- это всюду определённая частично рекурсивная функция, при этом в выводе могут фигурировать функции, которые не всюду определены.

Есть теорема о том, что каждая рекурсивная функция является общерекурсивной. Другими словами, для произвольной рекурсивной функции вывод, в котором участвуют только всюду определённые функции, всегда можно придумать. Но не факт, что если дан какой-то конкретный вывод рекурсивной функции, то все функции, участвующие в этом выводе, будут всюду определены. То есть функция может оказаться рекурсивной, но не пройти предложенный Вами тест (при каком-то данном конкретном выводе).

-- Чт мар 18, 2010 13:07:26 --

P. S. Для любой частично рекурсивной функции можно предложить вывод, в котором участвует не более одного $\mu$-оператора, причём если $\mu$ оператор в выводе есть, то он находится на последнем либо предпоследнем месте.