Наименьшая фиксированная точка

Наименьшая неподвижная точка функции из частично упорядоченного множества

Функция f ( x ) =  x ²  − 4 имеет две неподвижные точки, показанные как пересечение с синей линией; наименьшая из них находится при 1/2 −  √ 17 /2.

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

Примеры

При обычном порядке действительных чисел наименьшей неподвижной точкой действительной функции f ( x ) =  x ² является x  = 0 (поскольку единственной другой неподвижной точкой является 1 и 0 < 1). Напротив, f ( x ) =  x  + 1 не имеет неподвижных точек вообще, поэтому не имеет наименьшей одной, а f ( x ) =  x имеет бесконечно много неподвижных точек, но не имеет наименьшей одной.

Пусть будет направленным графом и будет вершиной. Множество вершин, доступных из, может быть определено как наименьшая неподвижная точка функции , определяемая как Множество вершин, которые являются содоступными из , определяется аналогичной наименьшей неподвижной точкой. Сильно связанный компонент является пересечением этих двух наименьших неподвижных точек. ${\displaystyle G=(V,A)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle f:\wp (V)\to \wp (V)}$ ${\displaystyle f(X)=\{v\}\cup \{x\in V:{\text{ for some }}w\in X{\text{ there is an arc from }}w{\text{ to }}x\}.}$ ${\displaystyle v}$ ${\displaystyle v}$

Пусть будет контекстно-свободной грамматикой . Набор символов, который производит пустую строку , может быть получен как наименьшая неподвижная точка функции , определяемая как , где обозначает множество степеней . ${\displaystyle G=(V,\Sigma ,R,S_{0})}$ ${\displaystyle E}$ ${\displaystyle \varepsilon }$ ${\displaystyle f:\wp (V)\to \wp (V)}$ ${\displaystyle f(X)=\{S\in V:\;S\in X{\text{ or }}(S\to \varepsilon )\in R{\text{ or }}(S\to S^{1}\dots S^{n})\in R{\text{ and }}S^{i}\in X{\text{, for all }}i\}}$ ${\displaystyle \wp (V)}$ ${\displaystyle V}$

Приложения

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

Денотационная семантика

Частичный заказ на ${\displaystyle \mathbb {Z} _{\bot }}$

В информатике подход денотационной семантики использует наименьшие фиксированные точки для получения из заданного текста программы соответствующей математической функции, называемой ее семантикой. Для этого вводится искусственный математический объект, , обозначающий исключительное значение «не определено». Например, если задан тип данных программы , его математический аналог определяется как частично упорядоченное множество путем определения для каждого и допуская, чтобы любые два различных члена были несравнимы относительно , ​​см. рисунок. ${\displaystyle \bot }$int ${\displaystyle \mathbb {Z} _{\bot }=\mathbb {Z} \cup \{\bot \};}$ ${\displaystyle \bot \sqsubset n}$ ${\displaystyle n\in \mathbb {Z} }$ ${\displaystyle n,m\in \mathbb {Z} }$ ${\displaystyle \sqsubset }$

Семантика определения программы int f(int n){...}представляет собой некоторую математическую функцию. Если определение программы не завершается для некоторого входного значения , это можно выразить математически как. Множество всех математических функций делается частично упорядоченным путем определения того, для каждой ли выполняется отношение , то есть, если менее определено или равно Например, семантика выражения менее определена, чем семантика , поскольку первое, но не второе, отображается в , и в остальном они согласуются. ${\displaystyle f:\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }.}$fn ${\displaystyle f(n)=\bot .}$ ${\displaystyle f\sqsubseteq g}$ ${\displaystyle n,}$ ${\displaystyle f(n)\sqsubseteq g(n)}$ ${\displaystyle f(n)}$ ${\displaystyle g(n).}$x+x/xx+1 ${\displaystyle 0}$ ${\displaystyle \bot ,}$

При наличии некоторого текста программы fего математический аналог получается как наименьшая фиксированная точка некоторого отображения функций в функции, которые могут быть получены путем "перевода" f. Например, определение C

int fact ( int n ) { если ( n == 0 ) вернуть 1 ; иначе вернуть n * fact ( n -1 ); }               

переводится в отображение

${\displaystyle F:(\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot })\to (\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }),}$определяется как ${\displaystyle (F(f))(n)={\begin{cases}1&{\text{if }}n=0,\\n\cdot f(n-1)&{\text{if }}n\neq \bot {\text{ and }}n\neq 0,\\\bot &{\text{if }}n=\bot .\\\end{cases}}}$

Отображение определено нерекурсивным способом, хотя было определено рекурсивно. При определенных ограничениях (см. теорему Клини о неподвижной точке ), которые выполняются в примере, обязательно имеет наименьшую неподвижную точку, , то есть для всех . ^[1] Можно показать, что ${\displaystyle F}$fact ${\displaystyle F}$ ${\displaystyle \operatorname {fact} }$ ${\displaystyle (F(\operatorname {fact} ))(n)=\operatorname {fact} (n)}$ ${\displaystyle n\in \mathbb {Z} _{\bot }}$

${\displaystyle \operatorname {fact} (n)={\begin{cases}n!&{\text{if }}n\geq 0,\\\bot &{\text{if }}n<0{\text{ or }}n=\bot .\end{cases}}}$

Более крупной фиксированной точкой является, например, функция, определяемая формулой ${\displaystyle F}$ ${\displaystyle \operatorname {fact} _{0},}$

${\displaystyle \operatorname {fact} _{0}(n)={\begin{cases}n!&{\text{if }}n\geq 0,\\0&{\text{if }}n<0,\\\bot &{\text{if }}n=\bot ,\end{cases}}}$

Однако эта функция не отражает правильно поведение приведенного выше текста программы для отрицательного значения, например, вызов не будет завершен вообще, не говоря уже о возврате . Только наименее фиксированная точка может быть разумно использована в качестве математической семантики программы. ${\displaystyle n;}$fact(-1)0 ${\displaystyle \operatorname {fact} ,}$

Описательная сложность

Иммерман ^{[2] [3]} и Варди ^[4] независимо друг от друга показали результат описательной сложности , что вычислимые за полиномиальное время свойства линейно упорядоченных структур определимы в FO(LFP) , т. е. в логике первого порядка с наименьшим оператором фиксированной точки. Однако FO(LFP) слишком слаб, чтобы выразить все свойства неупорядоченных структур за полиномиальное время (например, что структура имеет четный размер).

Наибольшие неподвижные точки

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

Смотрите также

• Теорема Кнастера–Тарского
• Логика с фиксированной точкой

Примечания

1. CA Gunter; DS Scott (1990). "Семантические домены". В Jan van Leeuwen (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Том B. Elsevier. С. 633–674. ISBN 0-444-88074-7.Здесь: стр. 636–638
2. Н. Иммерман, Реляционные запросы, вычислимые за полиномиальное время, Информация и управление 68 (1–3) (1986) 86–104.
3. Иммерман, Нил (1982). «Реляционные запросы, вычислимые за полиномиальное время». STOC '82: Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений . С. 147–152. doi :10.1145/800070.802187. Пересмотренная версия в Information and Control , 68 (1986), 86–104.
4. Варди, Моше Й. (1982). «Сложность реляционных языков запросов». STOC '82: Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений . стр. 137–146. doi :10.1145/800070.802186.
5. Charguéraud, Arthur (2010). "Оптимальный комбинатор неподвижных точек" (PDF) . Интерактивное доказательство теорем . 6172 : 195–210. doi :10.1007/978-3-642-14052-5_15 . Получено 30 октября 2021 г.
6. Шамир, Ади (октябрь 1976 г.). Неподвижные точки рекурсивных определений (диссертация на соискание степени доктора философии). Институт Вейцмана. OCLC  884951223.Здесь: Пример 12.1, стр. 12.2–3

Ссылки

• Иммерман, Нил . Описательная сложность , 1999, Springer-Verlag.
• Либкин, Леонид . Элементы теории конечных моделей , 2004, Springer.