Комбинатор неподвижной точки
Комбина́тор неподви́жной то́чки (также, ошибочно, иногда встречаются термины оператор неподвижной точки, комбинатор фиксированной точки и Y-комбинатор) — функция высшего порядка (все комбинаторы являются функциями высшего порядка), вычисляющая неподвижную точку другой функции.
Наиболее известным комбинатором неподвижной точки является Y-комбинатор в λ-исчислении, введённый известным американским учёным Хаскеллом Карри как
<math>Y=\lambda f\,.(\lambda x\,. f(x\ x))\;(\lambda x\,. f(x\ x))</math>. Иногда имя этого комбинатора ошибочно используется для обозначения вообще всех комбинаторов неподвижной точки.
В языках программирования, поддерживающих механизм анонимных функций, комбинатор неподвижной точки позволяет использовать рекурсию анонимных функций без присвоения значения такой функции переменной.
Теорема о неподвижной точке
И в λ-исчислении, и в комбинаторной логике для каждого терма <math>X</math> существует по крайней мере один терм <math>P</math> такой, что <math>XP = P</math>. И более того, существует комбинатор <math>Y</math> такой, что <math>YX = X(YX)</math>
См. также
Напишите отзыв о статье "Комбинатор неподвижной точки"
Литература
- Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — М.: МИФИ, 1994. — 204 с.; 2-е изд., М.: АО «Центр ЮрИнфоР», 2003. — 336 с. ISBN 5-89158-101-9.
- Mayer Goldberg, (2005) [www.brics.dk/RS/05/1/BRICS-RS-05-1.pdf On the Recursive Enumerability of Fixed-Point Combinators], BRICS Report RS-05-1, University of Aarhus
- Matthias Felleisen. [www.ps.uni-sb.de/courses/sem-prog97/material/YYWorks.ps A Lecture on the Why of Y].
Отрывок, характеризующий Комбинатор неподвижной точки
Каким образом то русское войско, которое, слабее числом французов, дало Бородинское сражение, каким образом это войско, с трех сторон окружавшее французов и имевшее целью их забрать, не достигло своей цели? Неужели такое громадное преимущество перед нами имеют французы, что мы, с превосходными силами окружив, не могли побить их? Каким образом это могло случиться?История (та, которая называется этим словом), отвечая на эти вопросы, говорит, что это случилось оттого, что Кутузов, и Тормасов, и Чичагов, и тот то, и тот то не сделали таких то и таких то маневров.
Но отчего они не сделали всех этих маневров? Отчего, ежели они были виноваты в том, что не достигнута была предназначавшаяся цель, – отчего их не судили и не казнили? Но, даже ежели и допустить, что виною неудачи русских были Кутузов и Чичагов и т. п., нельзя понять все таки, почему и в тех условиях, в которых находились русские войска под Красным и под Березиной (в обоих случаях русские были в превосходных силах), почему не взято в плен французское войско с маршалами, королями и императорами, когда в этом состояла цель русских?
Объяснение этого странного явления тем (как то делают русские военные историки), что Кутузов помешал нападению, неосновательно потому, что мы знаем, что воля Кутузова не могла удержать войска от нападения под Вязьмой и под Тарутиным.
Почему то русское войско, которое с слабейшими силами одержало победу под Бородиным над неприятелем во всей его силе, под Красным и под Березиной в превосходных силах было побеждено расстроенными толпами французов?
