- Комбинатор неподвижной точки
-
Комбина́тор неподви́жной то́чки (также, ошибочно, иногда встречаются термины оператор неподвижной точки, комбинатор фиксированной точки и Y-комбинатор) — функция высшего порядка, (все комбинаторы являются функциями высшего порядка) вычисляющая неподвижную точку другой функции.
Наиболее известным комбинатором неподвижной точки является Y-комбинатор в λ-исчислении, введённый известным американским ученым Хаскеллом Карри как
. Иногда имя этого комбинатора ошибочно используется для обозначения вообще всех комбинаторов неподвижной точки.
В языках программирования, поддерживающих механизм анонимных функций, комбинатор неподвижной точки позволяет использовать рекурсию анонимных функций без присвоения значения такой функции переменной.
Теорема о неподвижной точке
И в λ-исчислении, и в комбинаторной логике для каждого терма
существует по крайней мере один терм
такой, что
. И более того, существует комбинатор
такой, что
Литература
- Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — М.: МИФИ, 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.
См. также
Категории:- Лямбда-исчисление
- Комбинаторная логика
Wikimedia Foundation. 2010.