튜링 점프

연산성 이론에서 Turing 점프 또는 Turing 점프 연산자는 Alan Turing의 이름을 딴 Turing 점프 또는 Turing 점프 연산자는 각 결정 문제 $X$ 에 $X$ 가 $Oracle$ for Oracle이 있는 Oracle 기계에 의해 결정 가능하지 않은 속성을 가진 연속적으로 더 어려운 결정 문제 $X$ 를 할당하는 연산이다.

연산자는 문제 $X$ 의 튜링 정도를 증가시키기 때문에 점프 연산자라고 불린다.즉, $X'$ 문제는 $X$ 로 튜링 축소할 수 없다.포스트의 정리는 튜링 점프 연산자와 자연수 집합의 산술적 계층 구조 사이의 관계를 설정한다.^[1]비공식적으로 문제가 주어진 튜링 점프는 문제를 해결하는 오라클에 대한 액세스 권한이 주어지면 중지되는 튜링 머신 세트를 반환한다.

정의

X의 튜링 점프는 X에 대한 오라클이 있는 오라클 머신의 정지 문제에 대한 오라클이라고 생각할 수 있다.^[1]

형식적으로 X-computable 함수의 $X$ 와 Gödel 번호 매기기 $φ$ 에_i^X 따라 $X$ 의 Turing 점프 $X'$ 를 다음과 같이 정의한다.

X'=\{x\mid \varphi _{x}^{X}(x)\\\\mbox{is 정의}}}

n번째 튜링 점프 $X$ 는⁽ⁿ⁾ 다음과 같이 유도적으로 정의된다.

X^{(0)=X,

X^{{(n+1)}=(X^{(n)})''이다.

$X$ 의 $Ω$ 점프 $X$ 는^(ω) $n$ ∈ $N$ :에 대한 X $세트 (n)$ 시퀀스의 유효 결합이다.

X^{(\omega )}=\{p_{i}^{k}\mid i\in \mathb {N} {\text{ 및 }}}}X^{(i)}\}}

$여기$ 서_i p는 ith preme을 의미한다.

$0$ $'$ 또는 uring jump이라는 표기법은 빈 세트의 튜링 점프에 자주 사용된다.그것은 제로점프 혹은 때때로 제로프라임으로 읽힌다.

마찬가지로 $0$ 은⁽ⁿ⁾ 빈 세트의 n번째 점프다.유한 $n$ 의 경우, 이러한 집합은 산술 계층 구조와 밀접한 관련이 있다.

점프는 트랜스피니트 서수로 반복될 수 있다. 여기서 Ω은 Church-Kleene 서수형인 $α 1 CK$ < $Ω$ 의₁^CK $집합$ 은^(α) 초산술 서열과 밀접하게 관련되어 있다.^[1] $Ω$ 을₁^CK 초과하면, 이 과정은 설정기상법(Hodes 1980)을 사용하여 구성 가능한 우주의 계수 가능한 서수들을 통해 계속 진행될 수 있다.이 개념은 헤아릴 수 없는 정규 추기경까지 확대되도록 일반화되었다(Lubarsky 1987).^[2]

예

빈 세트의 튜링 점프 $0$ 0은 정지 문제와 동등한 튜링이다.^[3]
각 $n$ 에 대해 산술적 계층 구조(Post의 정리 기준)의 $\Sigma _{n}^{0}$ 레벨 $\Sigma _{n}^{0}$ 0 $\Sigma _{n}^{0}$ {\ $displaystyle \Sigma _{n}^{0}}$ 에서 $세트 (n)$ 0은 m-완전이다.
$X$ 에 대한 술어가 있는 페이노 산술 언어의 참 공식의 괴델 숫자 집합은 $X$ 에서^(ω) 계산할 수 있다.^[4]

특성.

$X'$ 은 X-컴퓨터적으로 열거되지만 X-컴퓨터는 아니다.
$A$ 가 $B$ 와 튜링 등가라면 $A$ 는 $B$ 와 튜링 등가 $.$ 이 암시의 반대는 사실이 아니다.
(쇼어 및 슬라만, 1999) $X$ 에서 $X$ 까지의 함수 매핑은 튜링도의 부분 순서로 정의할 수 있다.^[3]

튜링 점프 운영자의 많은 속성은 튜링 도에 관한 기사에서 논의된다.

참조

^ ^a ^b ^c Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Degrees of Unsolvability", Handbook of the History of Logic, Elsevier, vol. 9, pp. 443–494, doi:10.1016/b978-0-444-51624-4.50010-1, ISBN 9780444516244.
^ Lubarsky, Robert S. (December 1987). "Uncountable master codes and the jump hierarchy". The Journal of Symbolic Logic. 52 (4): 952–958. doi:10.2307/2273829. ISSN 0022-4812. JSTOR 2273829.
^ ^a ^b Shore, Richard A.; Slaman, Theodore A. (1999). "Defining the Turing Jump". Mathematical Research Letters. 6 (6): 711–722. doi:10.4310/MRL.1999.v6.n6.a10.
^ Hodes, Harold T. (June 1980). "Jumping through the transfinite: the master code hierarchy of Turing degrees". The Journal of Symbolic Logic. 45 (2): 204–220. doi:10.2307/2273183. ISSN 0022-4812. JSTOR 2273183.

암보스-스파이, K.와 Fejer, P. Degree of Unolvability.게시되지 않음.http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
Hodes, Harold T. (June 1980). "Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees". Journal of Symbolic Logic. Association for Symbolic Logic. 45 (2): 204–220. doi:10.2307/2273183. JSTOR 2273183.
Lerman, M. (1983). Degrees of unsolvability: local and global theory. Berlin; New York: Springer-Verlag. ISBN 3-540-12155-2.
Lubarsky, Robert S. (Dec 1987). "Uncountable Master Codes and the Jump Hierarchy". Journal of Symbolic Logic. Vol. 52, no. 4. pp. 952–958. JSTOR 2273829.
Rogers Jr, H. (1987). Theory of recursive functions and effective computability. MIT Press, Cambridge, MA, USA. ISBN 0-07-053522-1.
Shore, R.A.; Slaman, T.A. (1999). "Defining the Turing jump" (PDF). Mathematical Research Letters. 6 (5–6): 711–722. doi:10.4310/mrl.1999.v6.n6.a10. Retrieved 2008-07-13.
Soare, R.I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. ISBN 3-540-15299-7.

[:0-1] Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Degrees of Unsolvability", Handbook of the History of Logic, Elsevier, vol. 9, pp. 443–494, doi:10.1016/b978-0-444-51624-4.50010-1, ISBN 9780444516244.

[2] Lubarsky, Robert S. (December 1987). "Uncountable master codes and the jump hierarchy". The Journal of Symbolic Logic. 52 (4): 952–958. doi:10.2307/2273829. ISSN 0022-4812. JSTOR 2273829.

[:1-3] Shore, Richard A.; Slaman, Theodore A. (1999). "Defining the Turing Jump". Mathematical Research Letters. 6 (6): 711–722. doi:10.4310/MRL.1999.v6.n6.a10.

[4] Hodes, Harold T. (June 1980). "Jumping through the transfinite: the master code hierarchy of Turing degrees". The Journal of Symbolic Logic. 45 (2): 204–220. doi:10.2307/2273183. ISSN 0022-4812. JSTOR 2273183.

[1]

[2]

[3]

[4]

Search

튜링 점프

네임스페이스

더

목차

정의

예

특성.

참조