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

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

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

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

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

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

править

И в λ-исчислении, и в комбинаторной логике для каждого терма   существует по крайней мере один терм   такой, что  . И более того, существует комбинатор   такой, что  

См. также

править

Литература

править