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

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

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

${\displaystyle Y=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx)).}$

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

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

И в λ-исчислении, и в комбинаторной логике для каждого терма ${\displaystyle X}$ существует по крайней мере один терм ${\displaystyle P}$ такой, что ${\displaystyle P=XP}$. И более того, существует комбинатор ${\displaystyle Y}$ такой, что ${\displaystyle 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.