Оглавление
Наименьшая фиксированная точка
-
Определение и свойства фиксированной точки
- Фиксированная точка – это элемент, который остается неизменным при применении функции.
- Наименьшая фиксированная точка – это элемент, который меньше любого другого элемента в упорядоченном множестве.
- Наибольшая фиксированная точка – это элемент, который больше любого другого элемента в упорядоченном множестве.
-
Примеры и приложения
- Примеры включают функции, которые не имеют наименьшей фиксированной точки, такие как f(x) = x + 1.
- В информатике денотационная семантика использует наименьшую фиксированную точку для определения семантики программ.
- Наибольшие фиксированные точки используются реже, чем наименьшие, и могут быть не определены для некоторых функций.
-
Описательная сложность и оптимальная фиксированная точка
- Иммерман и Варди показали, что вычислимые свойства линейных упорядоченных структур могут быть выражены в логике первого порядка с оператором наименьшей фиксированной точки.
- Оптимальная фиксированная точка – это наиболее определенная фиксированная точка, совместимая со всеми другими фиксированными точками, и всегда существует, если существует наибольшая фиксированная точка.
-
Рекомендации
- Ссылки на книги Иммермана и Либкина для более детального изучения теории конечных моделей и описательной сложности соответственно.
Полный текст статьи: