UTM 정리

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정확한 인용문을 도입하여 개선해 주시기 바랍니다. (2019년 8월) (템플릿 메시지 삭제 방법 및 삭제 시기 확인)

계산가능성 이론에서, 정리 또는 보편적 튜링 기계 정리는 계산 가능한 함수 집합의 괴델 번호 매기기들에 대한 기본적인 결과이다.그것은 다른 모든 계산 ^[1]가능한 함수를 계산할 수 있는 계산 가능한 범용 함수의 존재를 확인합니다.유니버설 함수는 유니버설 튜링 기계의 추상적인 버전이며, 따라서 정리의 이름입니다.

로거의 등가정리는 s정리와_mn UTM정리의 관점에서 계산가능함수의 괴델번호부여의 특성을 제공한다.

정리

두 변수의 부분 계산 가능 함수 u는 한 변수의 모든 계산 가능 함수 f에 대해 f${\displaystyle }$(${\displaystyle x}$ )${\displaystyle u}$u (${\displaystyle e}$ ,${\displaystyle x}$ $)\displaystyle$ f$(x)\simeq$u (e$, x$ )}가$$ 모든 x에 대해 $존재$하도록 존재합니다.즉, 각 x에 대해 f(x)와 u(e,x)가 모두 정의되어 있고 동일하거나 정의되어 ^[2]있지 않습니다.

따라서 이 정리는 θ_e(x)를 u(e, x)로 정의할 때, 시퀀스 θ₁, θ₂, …가 부분 계산 가능 함수의 열거임을 보여준다.정리문에 있는 $함수$u를$$ 범용함수라고 한다.

레퍼런스

• Rogers, H. (1987) [1967]. The Theory of Recursive Functions and Effective Computability. First MIT press paperback edition. ISBN 0-262-68052-1.
• Soare, R. (1987). Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-15299-7.

이 수학논리 관련 기사는 스텁이다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.

• v
• t