Введение

В теории порядка, ветви математики, наименьшая неподвижная точка (lfp или LFP, иногда также наименьшая неподвижная точка) функции из частично упорядоченного множества (сокращенно "посет") в себя — это неподвижная точка, которая меньше любой другой неподвижной точки относительно порядка, заданного на "посете". Функция не обязана иметь наименьшую неподвижную точку, но если она существует, то она единственна.

Примеры

При обычном порядке на вещественных числах наименьшая неподвижная точка вещественной функции f(x) = x² равна x = 0 (поскольку единственная другая неподвижная точка равна 1 и 0 < 1). В отличие от этого, f(x) = x + 1 не имеет неподвижных точек вовсе, следовательно, не имеет и наименьшей из них, а f(x) = x имеет бесконечно много неподвижных точек, но не имеет наименьшей. Пусть G – ориентированный граф, а v – вершина. Множество вершин, достижимых из v, можно определить как наименьшую неподвижную точку функции, определяемой как . Множество вершин, из которых можно достичь v, определяется аналогичной наименьшей неподвижной точкой. Сильно связная компонента – это пересечение этих двух наименьших неподвижных точек. Пусть G – контекстно-свободная грамматика. Множество символов, порождающих пустую строку, можно получить как наименьшую неподвижную точку функции, определяемой как , где P(S) обозначает булеан (или множество всех подмножеств) множества S.

Приложения

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

Наибольшие фиксированные точки

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