클린의 T 술어

계산가능성 이론에서 수학자 스티븐 콜 클레인이 처음 연구한 T 술어는 산술의 형식 이론 내에서 계산 가능한 함수를 나타내기 위해 사용되는 자연수의 특정한 세 쌍의 집합이다.비공식적으로 T 술어는 특정 입력으로 실행할 때 특정 컴퓨터 프로그램이 중지되는지 여부를 알려주고, 프로그램이 정지하면 해당 U 함수를 사용하여 계산 결과를 얻는다.s정리와_mn 마찬가지로 클레네가 사용한 원래의 표기법도 개념의 표준용어가 되었다.^[1]

정의

T의₁ 통화 예시.첫 번째 인수는 계산 가능한 함수인 viz. Collatz 함수f의 소스 코드(Gödel numbere가 아닌 C로)를 제공한다.두 번째 주장은 f가 적용될 자연수 i를 준다.세 번째 인수는 (Gödel 시퀀스 번호가 아닌 방정식 체인으로) i에서 f의 평가를 시뮬레이션하는 연산 단계의 시퀀스 x를 제공한다.조건부 통화는 x가 실제로 통화 f(5)에 대한 정확한 계산 시퀀스이기 때문에 true로 평가되며, 더 이상 f를 포함하지 않는 표현으로 끝난다.시퀀스 x에 적용된 함수 U는 최종 표현식인 viz. 1을 반환한다.

이 정의는 계산 가능한 함수(Turing machine으로 주어짐)에 자연 숫자를 할당하는 적절한 괴델 번호 부여에 따라 달라진다.이 번호 매기는 계산 가능한 함수의 색인 및 함수에 대한 입력에 따라 해당 입력에 대한 함수 계산을 효과적으로 시뮬레이션할 수 있을 정도로 충분히 효과적이어야 한다. $T$ $T$ 술어는 $T$ 이 시뮬레이션을 공식화하여 얻는다.

3차 관계 $T_{1}(e,i,x)$ $T_{1}(e,i,x)$ , $T_{1}(e,i,x)$ , $T_{1}(e,i,x)$ ) $T_{1}(e,i,x)$ 은 세 개의 자연수를 인수로 취한다 $T_{1}(e,i,x)$ . $T_{1}(e,i,x)$ $i$ $i$ 을(를) 사용하여 실행할 때 $e$ x $x$ 이 $(가)$ $색인$ e $e$ 과 $i$ 와) 계산 가능한 함수의 계산 기록을 인코딩하고 $x$ 프로그램이 이 계산 기록의 마지막 단계로 중지되는 경우 $T_{1}(e,i,x)$ T $T_{1}(e,i,x)$ , i $T_{1}(e,i,x)$ , $T_{1}(e,i,x)$ ) ${\displaystylease true.$ 그것은

$T_{1}$ $T$ $T_{1}$ ${\$ }는 $x$ x {\ $displaystyle$ x}이 $($ 가) $입력$ i ${\$ $displaystyle$ i $}$ 에 대한 연산을 $e$ 실행하며, 인덱스 e {\ $displaystyle e}$ 이(가 $)$ 있는 튜링 시스템의 전체 구성의 $\langle x_{j}\rangle$ 유한 시퀀스 ⟨ $\langle x_{j}\rangle$ $\langle x_{j}\rangle$ ⟨ $\{\del}$ 의 $x$ Gödel 번호인지 묻는다 $i$
만일 $T_{1}$ 그렇다면, $T_{1}$ $T_{1}$ ${\$ 1} 이 시퀀스가 계산의 시작 상태에서 시작되며 시퀀스의 각 연속적인 요소가 튜링 머신의 단일 단계에 해당하는지 묻는다.
그렇게 되면 $T_{1}$ $T_{1}$ ${\$ }} $T_{1}$ 시퀀스 $\langle x_{j}\rangle$ x $\langle x_{j}\rangle$ $\langle x_{j}\rangle$ $\langle_{j}\angle }$ 이(가) 시스템이 중지 상태로 종료되는지 $\langle x_{j}\rangle$ 최종적으로 $T_{1}$ 묻는다.

이 세 문제 모두 긍정적인 답을 가지고 있다면, $T_{1}(e,i,x)$ $T_{1}(e,i,x)$ ( $T_{1}(e,i,x)$ , $T_{1}(e,i,x)$ , $T_{1}(e,i,x)$ ) $T_{1}(e,i,x)$ 이 진실이고 $T_{1}(e,i,x)$ , 그렇지 않으면 거짓이다.

$T_{1}$ $T_{1}$ ${\$ 술어는 $T_{1}$ , 술어에 대한 주어진 입력이 그러한 입력에 대한 술어의 진실 값을 정확하게 결정하는 원시 재귀 함수가 있다는 점에서 원시적인 재귀함수다.

$T_{1}(e,i,x)$ 원시 재귀 $함수$ U $U$ 이(가) 있으며, T $U$ $T_{1}(e,i,x)$ $T_{1}(e,i,x)$ $T_{1}(e,i,x)$ , x $T_{1}(e,i,x)$ ) ${\displaystyle T_{1}(e,i,x)$ 이 참이면 $T_{1}(e,i,x)$ $U(x)$ $U(x)$ ) $U(x)$ 이(가) $입력$ i ${\displaystystyle i}$ 에 $e$ 인덱스 $e$ ${\e}$ 과 함께 함수 출력을 반환한다 $U(x)$ $i$

클레네의 형식주의는 각 기능에 다수의 입력을 붙이기 때문에, $T_{1}$ $T_{1}$ 1 ${\$ }는 한 입력을 취하는 기능에만 사용할 $T_{1}$ 수 있다.여러 입력을 가진 함수에 대한 추가 술어가 있다. 관계

T_{k}(e,i_{1},\ldots,i_{k},x)

$x$ $x$ 이(가) 입력 $i_{1},\ldots ,i_{k}$ $i_{1},\ldots ,i_{k}$ , $i_{1},\ldots ,i_{k}$ i $i_{1},\ldots ,i_{k}$ ${\$ 에 인덱스 $e$ $e$ ${\displaystyle$ e $}$ 을(를) 사용하여 함수의 중지 연산을 인코딩하는 $x$ 경우 참입니다.

$T_{1}$ $T_{1}$ ${\$ }와 같이 모든 함수 $T_{k}$ $T_{k}$ ${\$ 는 원시 $T_{k}$ 재귀적이다 $T_{1}$ 이 때문에 모든 원시 재귀함수를 나타낼 수 있는 산술 이론은 $T$ ${\displaystyle$ T $}$ 와 $U$ ${\displaystyle$ U $}$ 를 나타낼 수 있다 $U$ 그러한 산술 이론의 예로는 로빈슨 산술과 페아노 산술과 같은 더 강한 이론이 있다.

정상형 정리

$T_{k}$ $T_{k}$ ${\$ 술어는 $T_{k}$ 계산 가능한 기능에 대한 클레네의 정상적인 형태 정리를 얻기 위해 사용할 수 있다(Soare 1987, 페이지 15; Kleene 1943, 페이지 52 -53).This states there exists a fixed primitive recursive function $U$ such that a function $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ is computable if and only if there is a number $e$ such that for all ${\displaystyle n_{1},\ldots ,n$ $_{k}}$ ①은 $n_{1},\ldots ,n_{k}$

{\displaystyle f(n_{1},\ldots,n_{k}\simeq

T_{k}(e,n_{1},\ldots,n_{k},x

여기서 μ는 μ 연산자( $\mu x\,\phi (x)$ $\mu x\,\phi (x)$ $\mu x\,\phi (x)$ $\mu x\,\phi (x)$ ) $\mu x\,\phi(x)$ 은 $\phi (x)$ ( $\phi (x)$ ) ${\$ $displaystyle \phi$ $(x)}$ 이 $($ 가) 참인 $\phi (x)$ 자연수 중 가장 작은 $\simeq$ 수이다 $\mu x\, \phi(x)$ $.$ 정리에 의해, 모든 일반 재귀 함수 f의 정의는 정상 형태로 다시 쓰여 μ 연산자가 단 한 번만 사용되도록 할 수 있다 $,$ viz. 가장 위쪽의 $U$ {\ $displaystyle U}$ 바로 밑에, 계산 가능한 $함수$ f $f$ 에 독립적이다 $f$

산술 계층 구조

계산가능성을 인코딩하는 것 외에도, T 술어는 산술적 계층 구조에서 완전한 집합을 생성하는 데 사용될 수 있다.특히 세트장에서는

K=\{e{\mbox{}}}}} {}}\mbox{}}}}\exists xT_{1}(e,0,x)\}}

정지 문제와 동일한 튜링 수준의 $\Sigma _{1}^{0}$ 1 $[\$ 완전한 $\Sigma _{1}^{0}$ 단일 관계(Soare 1987, 페이지 28, 41)이다.더 일반적으로, 세트

K_{n+1}=\\\langle e,a_{1},\ldots,a_{n}\ldots :\exists xT_{n}(e,a_{1},\ldots,a_{n}x)\}

$\Sigma _{1}^{0}$ $\Sigma _{1}^{0}$ $\Sigma _{1}^{0}$ ${\$ 완료 $\Sigma _{1}^{0}$ (n+1)-arry 술어다.따라서 일단 산술 이론에서_n T 술어의 표현을 얻으면 $\Sigma _{1}^{0}$ 1 $\Sigma _{1}^{0}$ ${\$ -완전한 $\Sigma _{1}^{0}$ 술어의 표현을 얻을 수 있다.

이 구성은 포스트의 정리(Hinman 2005, 페이지 397 비교)에서와 같이 산술적 계층 구조에서 더 높게 확장될 수 있다.예를 들어 $A\subseteq \mathbb {N} ^{k+1}$ A $A\subseteq \mathbb {N} ^{k+1}$ $A\subseteq \mathbb {N} ^{k+1}$ $A\subseteq \mathbb {N} ^{k+1}$ + 1 ${\$ n1}이(가) $\Sigma _{n}^{0}$ $\Sigma _{n}^{0}$ ${\$ 인 $A \subseteq \mathbb{N}^{k+1}$ 경우 집합이 $\Sigma _{n}^{0}$ 완료됨

\{\langle a_{1},\ldots,a_{k}\angle :\forall x(\langle a_{1},\landots,a_{k}x)\}}}}}

$\Pi _{n+1}^{0}$ + $\Pi _{n+1}^{0}$ $\Pi _{n+1}^{0}$ ${\$ 완료 $\Pi _{n+1}^{0}$ .

메모들

^ 여기서 서술한 술어는 (Kleene 1943)과 (Kleene 1952)에서 제시되었으며, 이것은 보통 "Kleene's T 술어"라고 불리는 것이다.(Kleene 1967)은 계산 가능한 기능과 관련된 다른 술어를 설명하기 위해 T자를 사용하지만, 클린의 정상적인 형태 정리를 얻는 데는 사용할 수 없다.

참조

피터 힌만, 2005년 수학논리의 기초, A K Peters. ISBN 978-1-56881-262-5
Stephen Cole Kleene (Jan 1943). "Recursive predicates and quantifiers" (PDF). Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.1090/S0002-9947-1943-0007371-8. The Underdicabled, Martin Davis, 1965년, 페이지 255–287에 재인쇄되었다.
—, 1952년, 노스-홀랜드의 메타매틱스 소개.2009년 이시 언론사에 의해 재인쇄된 ISBN 0-923891-57-9.
—, 1967.수학 논리학, 존 와일리2001년 도버에 의해 재인쇄된 ISBN 0-486-42533-9.
로버트 1세 Soare, 1987년, 반복적으로 셀 수 없는 집합과 학위, Perspects in Mathematical Logic, Springer.ISBN 0-387-15299-7

[1] 여기서 서술한 술어는 (Kleene 1943)과 (Kleene 1952)에서 제시되었으며, 이것은 보통 "Kleene's T 술어"라고 불리는 것이다.(Kleene 1967)은 계산 가능한 기능과 관련된 다른 술어를 설명하기 위해 T자를 사용하지만, 클린의 정상적인 형태 정리를 얻는 데는 사용할 수 없다.

[1]

Search

클린의 T 술어

네임스페이스

더

목차

정의

정상형 정리

산술 계층 구조

메모들

참조