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

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

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

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

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

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

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

Литература

См. также


Wikimedia Foundation. 2010.

Поможем написать реферат

Полезное


Смотреть что такое "Комбинатор неподвижной точки" в других словарях:

  • Лямбда-исчисление — (λ исчисление)  формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости. λ исчисление может рассматриваться как семейство прототипных языков программирования. Их основная… …   Википедия

  • Y Combinator (компания) — У этого термина существуют и другие значения, см. Комбинатор неподвижной точки. Y Combinator …   Википедия

  • Теория алгоритмов — Теория алгоритмов  наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач,… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»