반투명함수

계산가능성 이론에서 반투명함수는 부분함수 ${\displaystyle f\mathbb{}}$: Q${\displaystyle }$→ ${\displaystyle R\mathbb{}}$ ${\$ f$:\mathb {Q} \rightarrow \mathb {R}}$이며$,$ 계산가능함수에 의해 위 또는 아래에서 근사하게 추정할 수 있다.

More precisely a partial function ${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$ is upper semicomputable, meaning it can be approximated from above, if there exists a computable function ${\displaystyle \phi (x,k):\mathbb {Q} \times \mathbb {N} \rightarrow \mathbb {Q} }$, where ${\displaystyle x}$${\displaystyle x}$은(는${\displaystyle )}$ ${\displaystyle f(x)}$에 대해 원하는 매개 변수이고$$ $k{\displaystyle }$ ${\displaystyle k}$은(는) 근사치 수준이며$$ 다음과 같다.

• ${\displaystyle \lim _{k\오른쪽 화살표 \infit }\phi(x,k)=f(x)}$
• ${\displaystyle \forall k\in \mathb {N} :\phi (x,k+1)\leq \phi (x,k)}$

Completely analogous a partial function ${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$ is lower semicomputable if and only if ${\displaystyle -f(x)}$ is upper semicomputable or equivalently if there exists a computable function ${\displaystyle \phi (x,k)}$ such that:

• ${\displaystyle \lim _{k\오른쪽 화살표 \infit }\phi(x,k)=f(x)}$
• ${\displaystyle \forall k\in \mathb {N} :\phi (x,k+1)\geq \phi (x,k)}$

부분 함수가 상한과 하한 세미콤퍼팅이 모두 가능한 경우 계산가능하다고 한다.

참고 항목

• 계산성 이론

참조

• 밍 리와 폴 비타니, 콜모고로프 복잡성과 그것의 적용에 대한 소개, 1997년 스프링거, 페이지 37–38.

이 수학적 논리 관련 논문은 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t