최소 고정점

이 글을 고정점(수학)으로 병합할 것을 제안하였다.(토론) 2022년 2월 이후 제안

f(x) = x² - 4 함수에는 파란색 선과의 교차로로 표시된 두 개의 고정 점이 있으며, 최소 한 점은 1/2 - -17/2이다.

순서론에서 수학의 한 분야, 부분 순서가 정해진 집합에서 그 자체로 함수의 최소 고정점(lfp 또는 LFP, 때로는 가장 작은 고정점)은 포셋의 순서에 따라 서로 고정점보다 적은 고정점이다.함수는 최소 고정점을 가질 필요는 없지만, 고정점을 가질 경우 최소 고정점은 고유하다.

예를 들어, 실제 숫자에 통상적인 순서가 있는 경우, 실제 함수 f(x) = x의² 최소 고정점은 x = 0(다른 고정점만 1과 0 < 1이기 때문에)이다.이와는 대조적으로 f(x) = x + 1은 고정점이 전혀 없으므로 최소점이 없고, f(x) = x는 고정점이 무한히 많지만 최소점이 없다.

예

$G{\displaystyle }$=${\displaystyle }$( ${\displaystyle V}$, ${\displaystyle A}$) ${\displaystyle G=(V,A)}$을(를) 지시된 그래프로 하고$$ $v{\displaystyle }$ ${\displaystyle v}$을(를) 꼭지점으로$$ 한다.The set of vertices accessible from ${\displaystyle v}$ can be defined as the least fixed-point of the function ${\displaystyle f:\wp (V)\to \wp (V)}$, defined as ${\displaystyle f(X)=X\cup \{v\}\cup \{x\in V:{\text{$$}}}w\in X{\text{}}}에 해당하는 }w{\text{}에서 }x\}$$까지의 호가 있다.$$}$ $v{\displaystyle }$ ${\displaystyle v}$에서 동시에 액세스할 수 있는 정점 집합은$$ 유사한 최소 고정점으로 정의된다$$.$v{\displaystyle }$ ${\displaystyle v}$의 강하게 연결된 구성 요소는 이 두 최소 고정점의 교차점이다.

Let $G{\displaystyle }$=${\displaystyle }$( V${\displaystyle }$, ${\displaystyle \mathrm{\sigma }}$, ${\displaystyle R}$, ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$) ${\displaystyle G=(V,\Sigma ,R,S_{0})$는 문맥이 없는 문법이다.The set ${\displaystyle E}$ of symbols which produces the empty string ${\displaystyle \varepsilon }$ can be obtained as the least fixed-point of the function ${\displaystyle f:\wp (V)\to \wp (V)}$, defined as ${\displaystyle f(X)=\{S\in V:S\in X\text{or}(S\to \epsilon )\in R\text{or}(S\to S^1\dots S^n)\in R\text{and}}$${\displaystyle f(X)=\{S\in$$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\}}$, where ${\displaystyle \wp (V)}$ denotes the power set of ${\displaystyle V}$.

적용들

많은 고정점 이론들은 최소 고정점을 찾기 위한 알고리즘을 산출한다.최소 고정점에는 임의 고정점에는 없는 바람직한 특성이 있는 경우가 많다.

변절 의미론

$Z{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$에 부분 순서

컴퓨터 과학에서, 변성 의미론 접근법은 주어진 프로그램 텍스트로부터 그것의 의미론이라고 불리는 상응하는 수학적 함수를 얻기 위해 최소한의 고정점을 사용한다.이를 위해 mathematical {\디스플레이 스타일$\bot$ $\}$인 인공수학 물체가 도입돼 '정의되지 않음'이라는 예외적 가치를 나타낸다.프로그램 데이터 유형과 같이 지정됨int, its mathematical counterpart is defined as ${\displaystyle \mathbb {Z} _{\bot }=\mathbb {Z} \cup \{\bot \};}$ it is made a partially ordered set by defining ${\displaystyle \bot \sqsubset n}$ for each ${\displaystyle n\in \mathbb {Z} }$ and letting any two different members ${\displaystyle n,m\in \mathbb{Z}}$${\displaystyle n,m\in \mathb {Z}}$은(는) 비교할 수 없는 w.r.t. $⊏{\displaystyle }${\$displaystyle \sqsubset$ 그림을 참조하십시오.

프로그램 정의의 의미론int f(int n){...}일부 수학 함수 $f{\displaystyle }$: ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$→ Z ${\displaystyle {}_{}}$ ${\displaystyle$ f$:\mathb {Z} _{\bot }\to \mathb {Z} _{\bot }}$ 프로그램 정의인 경우$$f일부 입력에 대해 종료되지 않음n, this can be expressed mathematically as ${\displaystyle f(n)=\bot .}$ The set of all mathematical functions is made partially ordered by defining ${\displaystyle f\sqsubseteq g}$ if, for each ${\displaystyle n,}$ the relation ${\displaystyle f(n)\sqsubseteq g(n)}$ holds, that is, i$f{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle f(n)}$이(${\displaystyle 가}$) $g{\displaystyle }$(${\displaystyle }$)${\displaystyle }$. ${\displaystyle g(n$)과 덜 정의되었거나 같음$.$$}$ 예$$: 표현식의 의미론x+x/x의 정의보다 적다x+1, 전자가 아니라 후자가 아닌 $0{\displaystyle \mathrm{}}$ ${\displaystyle 0}$을(를) $\perp {\displaystyle \mathrm{}}$, ${\displaystyle \bot$에 매핑하면, 그들은$$ 달리 동의한다.

일부 프로그램 텍스트 지정f, 그것의 수학 상대는 함수에서 "수치"에 의해 얻을 수 있는 함수에 이르는 일부 매핑의 최소 고정 지점으로 얻는다.f. 예를 들어, C 정의

인트로 사실의(인트로 n) { 만일 (n == 0) 그때 돌아오다 1; 다른 돌아오다 n * 사실의(n-1); } 

매핑으로 변환됨

${\displaystyle F:(\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot })\to (\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }),}$ defined as ${\displaystyle (F(f))(n)=\l$$eft\{\property{array}{ll}1&{{n1}.{n\cdot f(n-1)&{\text{}}{}n\n\neck \bot{}{}n=\bot \end{array}}\right.$$}$

매핑 $F{\displaystyle }$ ${\displaystyle F}$은(는) 비반복적인 방식으로 정의되지만$$fact재귀적으로 정의되었다.Under certain restrictions (see Kleene fixed-point theorem), which are met in the example, ${\displaystyle F}$ necessarily has a least fixed point, ${\displaystyle {\textit {fact}}}$, that is ${\displaystyle (F({\textit {fact}}))(n)={\textit {fact}}(n)}$ for all ${\displaystyle n\in {\mathbb{Z}}_{\mathrm{\perp }}}$${\displaystyle n\in \mathb {Z} _{\bot$ $\}\}.$^[1] 는 것을 보여줄 수 있다.

${\displaystyle {\textit}(n)=\left\{{\put{array}{ll}n!&{{{\n\geq 0\\\\bot &{\text{}}}}{}n<0\text{또는 }n=\bot \end{array}}\right.}$

$F{\displaystyle }$ ${\displaystyle F}$의 더 큰 고정점은 예$$: 함수 ${\displaystyle {\mathit{\text{팩트}}}_{}}$ ${\displaystyle 0_{\mathrm{}}}$ ${\displaystyle {\textit${fact$}_{0$}}에 의해 정의된다$$.

${\displaystyle {\textit}_{0}(n)=\left\{\put{array}{ll}n!&{{\text{}n\geq 0\\\0&{\text{}}}{}n<0\\bot &{\text{}}}}{n=\bot\\end{array}}}\right,}$

그러나 이 함수는 $음$의 n${\displaystyle ;}$ ${\displaystyle n;}($예$$: 통화)에 대해 위의 프로그램 텍스트의 동작을 올바르게 반영하지 않는다.fact(-1)돌아오기는커녕 아예 종지부를 찍지도 않을 것이다.0. 가장 덜 고정된 점${\displaystyle ,}$ $,$ {\$displaystyle${\$textit$ {$fact},}$만 수학 프로그램 의미로서 합리적으로 사용할 수 있다$$.

서술적 복잡성

임메르만과^[2][3] 바디는^[4] 독립적으로 선형 순서가 정해진 구조의 다항식 시간 계산 가능 특성이 FO(LFP)에서 정의 가능하다는 서술적 복잡성 결과를 보여주었다.그러나 FO(LFP)는 너무 약해서 주문되지 않은 구조물의 모든 다항식 시간 특성을 표현하지 못한다(예를 들어 구조물의 크기가 짝수인 경우).

최대 고정점

가장 큰 고정점 또한 결정될 수 있다.실수의 경우 정의는 최소 고정점과 대칭이지만 컴퓨터 공학에서는 최소 고정점보다 일반적으로 덜 사용된다.구체적으로는, 도메인 이론에서 발견되는 포지션은 대개 가장 큰 요소를 가지지 않기 때문에, 상호 비할 수 없는 복수의 최대 고정점이 있을 수 있으며, 가장 큰 고정점은 존재하지 않을 수도 있다.이 문제를 해결하기 위해 최적의 고정점은 다른 모든 고정점과 호환되는 가장 정의된 고정점으로 정의되었다.최적 고정점은 항상 존재하며, 가장 큰 고정점이 존재하는 경우 가장 큰 고정점이다.최적 고정점은 최소 고정점과 수렴하지 않는 재귀 및 코어커서 함수에 대한 공식적인 연구를 가능하게 한다.^[5]불행히도 효과적인 재귀적 정의의 최적 고정점은 계산 불가능한 함수일^[6] 수 있으므로 주로 이론적 관심사다.

참고 항목

• 크나스터-타르스키 정리
• 고정점 논리

메모들

참조

• 임머먼, 닐.기술 복잡성, 1999, Springer-Verlag.
• 리브킨, 레오니드.유한 모델 이론의 요소들, 2004, 스프링거.