Комбинатор неподвижной точки

Запрос «Y-комбинатор» перенаправляется сюда; о венчурном фонде см. Y Combinator.

Комбина́тор неподви́жной то́чки (или оператор неподвижной точки) — функция высшего порядка, вычисляющая неподвижную точку другой функции.

Наиболее известным комбинатором неподвижной точки является Y-комбинатор в λ-исчислении, введённый известным американским учёным Хаскеллом Карри как

$Y=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx)).$

Иногда имя этого комбинатора ошибочно используется для обозначения вообще всех комбинаторов неподвижной точки.

Языки программирования, в которых допустим комбинатор неподвижной точки, позволяют использовать рекурсию анонимных функций без присвоения значения такой функции переменной.

Теорема о неподвижной точке

И в λ-исчислении, и в комбинаторной логике для каждого терма $X$ существует по крайней мере один терм $P$ такой, что $P=XP$. И более того, существует комбинатор $Y$ такой, что $YX=X(YX)$.

См. также

• Комбинаторная логика
• Лямбда-исчисление
• Функциональное программирование

Литература

• Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — М.: МИФИ, 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 Архивная копия от 29 сентября 2007 на Wayback Machine.