Комбина́тор неподви́жной то́чки (или оператор неподвижной точки) — это комбинатор, нерекурсивная функция высшего порядка , создающая неподвижную точку другой функции высшего порядка , так что
Введение Языки программирования, в которых допустим комбинатор неподвижной точки, позволяют использовать рекурсию анонимных функций без необходимости присвоения значения такой функции какой-либо переменной. В общем виде, имея функционал, описывающий «один шаг» рекурсивного вычисления,
где обозначает «остаток вычислений», — соответствующая рекурсивная функция
где вызов будет происходить в зависимости от значения . Но получает как значение , и таким образом базисный вычислительный шаг будет повторяться снова и снова, по мере необходимости, без ограничений, как определено значением аргумента:
Y-комбинатор Наиболее известным комбинатором неподвижной точки является Y-комбинатор в λ-исчислении, часто приписываемый известному американскому учёному Хаскеллу Карри, хотя он был впервые опубликован Паулем Розенблюмом:
Иногда имя этого комбинатора ошибочно используется для обозначения вообще всех комбинаторов неподвижной точки.
Другие комбинаторы неподвижной точки Существует бесконечно много комбинаторов неподвижной точки, напримерfixed-point combinator in nLab.
и т. д. Здесь — это комбинатор Тьюринга, это комбинатор фиксированной точки Клоппа, и - комбинатор от Р. Статмана. Как опубликовано Джоном Тромпом, насколько известно, из всех возможных комбинаторов фиксированной точки, выражается наикратчайшей строкой комбинаторов.
Теорема о неподвижной точке И в λ-исчислении, и в комбинаторной логике для каждого терма существует по крайней мере один терм такой, что . И более того, существует комбинатор такой, что .
См. также Комбинаторная логика Лямбда-исчисление Функциональное программирование
Примечания
Литература Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — М.: МИФИ, 1994. — 204 с.; 2-е изд., М.: АО «Центр ЮрИнфоР», 2003. — 336 с. ISBN 5-89158-101-9. Mayer Goldberg, (2005) On the Recursive Enumerability of Fixed-Point Combinators, BRICS Report RS-05-1, University of Aarhus Matthias Felleisen. A Lecture on the Why of Y .
Категория:Лямбда-исчисление Категория:Комбинаторная логика