- Комбинатор неподвижной точки
-
Комбина́тор неподви́жной то́чки (также, ошибочно, иногда встречаются термины оператор неподвижной точки, комбинатор фиксированной точки и 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.