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

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

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

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

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

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

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

См. также

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

Литература

• Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — М.: МИФИ, 1994. — 204 с.; 2-е изд., М.: АО «Центр ЮрИнфоР», 2003. — 336 с. ISBN 5-89158-101-9 .
• Mayer Goldberg, (2005) , BRICS Report RS-05-1, University of Aarhus
• . от 29 сентября 2007 на Wayback Machine .