WikiSort.ru - Не сортированное

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

Наиболее известным комбинатором неподвижной точки является Y-комбинатор в λ-исчислении, введённый известным американским учёным Хаскеллом Карри как
${\displaystyle Y=\lambda f\,.(\lambda x\,.f(x\ x))\;(\lambda x\,.f(x\ x))}$ . Иногда имя этого комбинатора ошибочно используется для обозначения вообще всех комбинаторов неподвижной точки.

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

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

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

См. также

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

Литература

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