Так как в исчислении все функции анонимны (без имен), то необходимо их вызов производить не по имени, а другим способом. Например, рассмотрим рекурсивную функцию, которая в качестве одного из аргументов имеет ссылку на себя:
а) - сложение всех целых чисел:
– если , то , иначе складываем (+) число с суммой для числа, меньшего на 1, чем , т.е. (1–) обозначает уменьшение на 1. Это была форма записи рекурсивной функции на языке Гильберта-Клини, а в форме абстракции: Осталось связать переменную со значением функции , чтобы сделать функцию анонимной. Это можно сделать с помощью специальной функции « комбинатор»:
.
Например, функция «» имеет бесконечное число «неподвижных» точек. Таким образом, в исчислении функция записывается так:
Проверим, например, должно быть равно 1.:
Определим «комбинатор» как
.
Проверим выполнение формы записи :
Чистое исчисление
Чистое исчисление получается при удалении констант и правил, так как в нем любые константы и функции можно построить атомарными термами, использующие только лишь переменные.
|
|
ПРИМЕРЫ:
а) ; б) ; в) .
Легко проверить, что выполняются следующие редукции:
1.
2.
3.
Нумерация Черча: представлять композицией , т.е. , т.е. повторяется раз. Для каждого натурального положим: ,
. Тогда «сложение» чисел определяется выражением:
.
Проверка:
Определение: Говорят, что частичная функция с аргументами определима термом , когда терм редуцируется к терму , если значение определено, и не имеет нормальной формы, если не определено.
Теорема Клини: Частичная функция частично-рекурсивна тогда и только тогда, когда она определима.