튜링 정도

컴퓨터 과학과 수학 논리학에서 튜링 정도(Alan Turing의 이름을 따서 명명) 또는 자연수 집합의 불능성의 정도는 집합의 알고리즘 불능성의 수준을 측정한다.

개요

튜링 정도의 개념은 계산가능성 이론에서 기본이며, 여기서 자연수 집합은 종종 의사결정 문제로 간주된다. 튜링 정도는 집합과 관련된 의사결정 문제, 즉 임의의 숫자가 주어진 집합에 있는지 여부를 결정하는 것이 얼마나 어려운지를 나타내는 척도다.

두 세트는 동일한 레벨의 불능성을 가진 경우 튜링 등가물이다. 각 튜링 등급은 튜링 등가 세트의 집합이므로 튜링 등가물이 아닐 때 정확히 다른 튜링 등급에 있다. 또한 튜링 도수는 부분적으로 정렬되어 세트 X의 튜링 정도가 세트 Y의 튜링 도보다 작을 경우, 숫자가 Y에 있는지 여부를 정확하게 결정하는 모든 (컴퓨팅 불가능한) 절차를 X에 있는지 여부를 정확하게 결정하는 절차로 효과적으로 변환할 수 있다. 이러한 의미에서 세트의 튜링 정도는 알고리즘 불능성의 수준에 해당된다.

튜링 학위는 에밀 레온 포스트(1944년)에 의해 도입되었으며, 스테판 콜 클레네와 포스트(1954년)에 의해 많은 근본적인 결과가 확립되었다. 튜링 학위는 그 이후로 강도 높은 연구의 한 분야였다. 그 지역의 많은 증명서들은 우선법이라고 알려진 증명기법을 사용한다.

튜링 당량

이 글의 나머지 부분에서는 단어 집합이 자연수 집합을 가리킬 것이다. Y의 멤버십을 위해 오라클이 주어졌을 때 X의 멤버십을 결정하는 오라클 튜링 머신이 있다면 세트 X는 세트 Y로 축소 가능하다고 한다. X ≤_T Y라는 표기법은 X가 Y로 튜링할 수 있음을 나타낸다.

X가 Y로 Turing할 수 있고 Y가 X로 Turing할 수 있는 경우 X와 Y가 Turing 등가물로 정의된다. X ≡_T Y라는 표기법은 X와 Y가 튜링 등가임을 나타낸다. 관계 ≡_T은 모든 집합에 대해 X, Y, Z를 의미하는 동등성 관계라고 볼 수 있다.

• X ≡_T X
• X ≡_T Y는 Y ≡_T X를 의미한다.
• X _Ty Y와 Y _Tz Z이면 X ≡_T Z이다.

튜링 학위는 관계 of의 동등성 등급이다._T 표기법 [X]는 집합 X를 포함하는 등가 등급을 나타낸다. 튜링 도 전체 컬렉션이 $D{\displaystyle \mathcal{}}$ ${\$로 표시됨$.$

튜링 도에는 X order Y인 경우에만 [X] ≤_T [Y]가 되도록 부분 순서 ≤이 정의되어 있다. 계산 가능한 모든 세트를 포함하는 독특한 튜링 정도가 있으며, 이 정도는 다른 모든 도보다 적다. 포셋 $D{\displaystyle \mathcal{}}$ ${\$의 최소 원소이기 때문에 0 (0)으로 표기한다.(Turing 도에 대해서는 세트와 구별하기 위해 굵은체 표기법을 사용하는 것이 일반적이다$.$ [X]와 같이 혼동이 일어날 수 없는 경우에는 대담한 얼굴이 필요하지 않다.)

X와 Y 세트의 경우, X y Y로 표기된 X join Y는 {2n : n ∈ X} 및 {2m+1 : m ∈ Y} 세트의 조합으로 정의된다. 튜링도 X ⊕ Y는 X와 Y의 도 중 가장 낮은 상한이다. 따라서 $D{\displaystyle \mathcal{}}$ ${\$은(는) 조인-세밀래티스(join-semilatice)이다$$. a와 b의 최소 상한은 ∪ b로 표시된다. $D{\displaystyle \mathcal{}}$ ${\$는 하한선이 가장 큰 도 쌍이 있으므로 격자가 아닌$$ 것으로 알려져 있다.

X 세트의 경우 X 표기법 X는 X를 Oracle로 사용할 때 중지되는(입력으로 인덱스를 지정한 경우) Oracle 시스템의 인덱스 세트를 나타낸다. 세트 X′는 X의 튜링 점프라고 불린다. 정도[X]의 튜링 점프는 정도[X′]로 정의된다. 이는 X′ ≡_T Y 때마다 X′ ≡_T Y′이기 때문에 유효한 정의다. 주요 예는 정지 문제의 정도인 0′이다.

튜링도의 기본 특성

• 모든 튜링 도수는 셀 수 없이 무한하다. 즉, 정확히 ${\displaystyle {0\mathrm{}}_{}}$ 0${\$세트를$$ 포함한다.
• $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\aleph {\mathrm{}}_{}}^{}}$ ${\displaystyle {{0\mathrm{}}_{}}^{}}$ ${\$ 구별$$ 튜링도가 있다.
• 각 도에 대해 < a′은 엄격한 불평등을 가지고 있다.
• 각 도 a에 대해 a 미만의 도 세트는 셀 수 있다. a보다 큰 도 세트는 크기가 ${\displaystyle {{2\mathrm{}}_{}}^{}}$ ${\displaystyle {\aleph {\mathrm{}}_{}}^{}}$ 0 ${\$ 2$^{\aleph _{0}}$이다$.$

튜링도의 구조

튜링 학위 구조에 대해 많은 연구가 진행되었다. 다음 조사에서는 알려진 많은 결과 중 일부만 나열한다. 이 연구에서 도출할 수 있는 한 가지 일반적인 결론은 튜링 학위의 구조가 극도로 복잡하다는 것이다.

주문 속성

• 최소한의 정도가 있다. a가 0이 아니고 0과 a사이에 도수가 없으면 a도는 최소다. 따라서 학위에서의 순서 관계는 밀도가 높은 순서가 아니다.
• 튜링 도수는 ≤_T에 의해 선형적으로 순서가 정해지지 않는다.
• 사실, 0도가 아닌 모든 도에 대해 a와 비교할 수 없는 정도가 있다.
• $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {{\aleph \mathrm{}}_{}}^{}}$ 0$${\$displaystyle$ 2$^{\aleph _{0}$ 쌍으로$$ 비교할 수 없는 튜링 도수가 세트로 되어 있다.
• 가장 큰 하한선이 없는 한 쌍의 학위가 있다. 따라서 $D{\displaystyle \mathcal{}}$ ${\$은 격자가 아니다$$.
• 부분적으로 정렬된 모든 카운트 가능한 세트는 튜링 도에 포함될 수 있다.
• 무한하지 않고 엄격하게 증가하는 도 순서는 최소 상한선을 가진다.

점프와 관련된 속성

• 모든 학위에는 a와 a의 학위가 엄격하게 있다. 사실, a와 a와 비교할 수 없는 수준의 쌍끌이 가족이 있다.
• 점프 뒤집기: a는 0˚ a일 경우에만 b′형이다.
• 어느 정도나 a 도 b는 < b와 b′ = a′>와 같은 도 b가 있고, 그러한 도 b는 a에 비해 낮은 도라고 한다.
• 각 i에 대해 a′_i+1 a_i a가 a일 정도로 무한정 a의_i 순서가 있다.
• 포스트의 정리, 산술적 계층 구조와 빈 집합의 정밀하게 반복된 튜링 점프 사이에 밀접한 일치성을 확립한다.

논리 속성

• 심슨(1977)은 언어 $language$, = ⟩, ⟩ 또는 ⟨, ′, ′, =, = =, =, =의 D ${\$의 1차 이론이 진정한 2차 산술 이론에 상당하는 것을 보여주었다. $이것$은 D ${\$의 구조가 극도로 복잡하다는$$ 것을 나타낸다.
• 쇼어와 슬라만(1999)은 $D{\displaystyle \mathcal{}}$ ${\$의 1차 구조에서 점프 운영자가 ⟨, = ⟩이라는 언어를 사용하여$$ 정의할 수 있음을 보여주었다.

반복적으로 열거된 튜링 도

학위가 재귀적으로 열거할 수 있는 집합을 포함하는 경우를 재귀적으로 열거할 수 있는(즉, 재귀적으로 열거할 수 있는)이라고 한다. 모든 r. 즉, 도수가 0°이하인 것은 아니지만, 0° 이하가 모두 r.e.

• (G. E. Sacks, 1964년) r.e.도는 밀도가 높으며, 두 r.e.도 사이에 세 번째 r.e.도가 있다.
• (A. H. Lachlan, 1966a 및 C. E. E. M. Yates, 1966) 두 개의 r. 즉, r.e. 도에 가장 큰 하한이 없는 r.도가 있다.
• (A. H. Lachlan, 1966a 및 C. E. E. M. Yates, 1966) 0도가 아닌 한 쌍의 r. 즉, 하한이 0인 한 쌍이 있다.
• (A. H. 라클란, 1966b) 최대 하한이 0이고 최소 상한 값이 0인 r.e. 도 쌍은 없다. 이 결과를 비공식적으로 비아모논드 정리라고 한다.
• (S. K. Thomason, 1971) 모든 유한 분배 격자는 r.e. 도에 삽입될 수 있다. 사실, 셀 수 있는 원자 없는 부울 대수학은 우월성과 이피마를 보존하는 방식으로 내장될 수 있다.
• (A. H. Lachlan과 R. I. Soare, 1980) 모든 유한 격자가 (우월성과 인피마를 보존하는 임베딩을 통해) r. 즉, 도에 내장될 수 있는 것은 아니다. 특정한 예가 오른쪽에 보여진다.
• (L. A. 해링턴과 T. A. 슬라먼, 니, 쇼어, 슬라먼(1998)을 보라. ⟨ 0, ≤, = ⟩의 언어에서 r.e. 도에 대한 1차 이론은 진정한 1차 산술 이론에 상당하는 다대다.

게시물의 문제 및 우선 순위 방법

에밀 포스트는 r.e.를 연구했다. 튜링 도표를 하고 r. 즉, 0과 0 사이의 정도가 있는지 물었다. 그런 학위(또는 존재하지 않는다는 것을 보여주는 것)를 구성하는 문제는 포스트의 문제로 알려지게 되었다. 이 문제는 1950년대에 프리드버그와 무치니크에 의해 독자적으로 해결되었는데, 그는 이 중간 정도의 학위가 존재한다는 것을 보여주었다. 그들의 증명서는 각각 r.즉, 학위를 구성하는 동일한 새로운 방법을 개발했는데, 이것이 우선 순위법으로 알려지게 되었다. 우선 순위 방법은 이제 r.e. 집합에 대한 결과를 설정하는 주요 기법이 된다.

집합 X를 구성하기 위한 우선순위 방법의 아이디어는 X가 충족해야 하는 요건들의 카운트 가능한 순서를 나열하는 것이다. 예를 들어, X 설정 값을 0과 0 사이에 구성하려면 각 자연수 e에 대한 요구사항 A와_e B를_e 충족하기에 충분하며, 여기서 A는_e 인덱스 e를 가진 오라클 머신이 X에서 0을 계산하지 않고, B를_e 계산하지 않으면 인덱스 e를 가진 튜링 머신이 X를 계산하지 않아도 된다. 이러한 요구사항은 우선순위에 배치되며, 이는 요구사항과 자연수의 명시적 편향이다. 증명서는 각각의 자연수에 대해 하나의 단계를 통해 귀납적으로 진행된다. 이러한 단계는 집합 X가 열거되는 시간의 단계로 생각할 수 있다. 각 단계에서 요구 사항을 충족하기 위해 X에 숫자를 넣거나 X에 입력하는 것을 영구히 방지할 수 있다(즉, X가 모두 열거된 경우 X를 보유하도록 강제). 때로는 하나의 요건을 충족시키기 위해 X에 숫자를 열거할 수 있지만, 이렇게 하는 것은 이전에 충족된 요건을 만족시키지 못하게 한다(즉, 부상을 당하게 된다). 요건의 우선순위는 이 경우 어느 요건을 충족해야 하는지를 결정하는 데 사용된다. 비공식적인 아이디어는 비록 모든 우선 순위 논쟁에 이 특성이 있는 것은 아니지만, 요건이 손상되면, 모든 상위 우선 순위 요건이 부상되는 것을 멈춘 후에 결국 부상당하는 것을 멈출 것이라는 것이다. 전체 집합 X는 r. 즉, 모든 요구사항을 만족한다는 주장이 있어야 한다. 우선 순위 주장은 r. 집합에 대한 많은 사실들을 입증하기 위해 사용될 수 있다. 사용된 요건들과 그것들이 충족되는 방법은 요구되는 결과를 도출하기 위해 신중하게 선택되어야 한다.

참고 항목

• 마틴 치수

참조

모노그래프(하위 수준)

• 쿠퍼, S.B. 계산가능성 이론. Chapman & Hall/CRC, Boca Raton, FL, 2004. ISBN1-58488-237-9
• 커틀랜드, N. 연산성. 캠브리지 대학 출판부, 1980년 뉴욕. ISBN 0-521-22384-9; ISBN 0-521-29465-7

모노그래프 및 조사 기사(원급)

• 암보스-스파이, K.와 Fejer, P. Degree of Unolvability. 게시되지 않음. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Lerman, M. Degree of Volvability. Lerman, M. Degree of Volibility 수학 논리의 관점. 1983년 베를린 스프링거-베를라크. ISBN 3-540-12155-2
• Odifreddi, P. G. (1989), Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, vol. 125, Amsterdam: North-Holland, ISBN 978-0-444-87295-1, MR 0982269
• Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, Amsterdam: North-Holland, ISBN 978-0-444-50205-6, MR 1718169
• 로저스, H. MIT 출판사의 재귀적 기능과 유효 계산가능성 이론. ISBN 0-262-68052-1, ISBN 0-07-053522-1
• 색스, 제럴드 E. Princeton Unsolvability(Annals of Mathical Studies), Princeton University Press. ISBN 978-0-6910-7941-7
• S. S. S. Department of Volvability: 결과의 조사. 수리논리편람, North-Holland, 1977, 페이지 631–652.
• 쇼엔필드, 조셉 R. 불능도, 노스홀랜드/엘세비에르, ISBN 978-0-7204-2061-6.
• Shore, R. (1993). "The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond". In Univ. Nac. del Sur, Bahía Blanca (ed.). Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992). Notas Lógica Mat. Vol. 38. pp. 61–70.
• Soare, R. 반복적으로 셀 수 있는 세트와 도. 수학 논리의 관점. 1987년 베를린 스프링거-베를라크 ISBN 3-540-15299-7
• 소어, 로버트 1세 반복적으로 셀 수 있는 세트와 도. 황소. 아머. 수학. Soc. 84 (1978), 6, 1149–1181. MR508451

연구논문

• Kleene, Stephen Cole; Post, Emil L. (1954), "The upper semi-lattice of degrees of recursive unsolvability", Annals of Mathematics, Second Series, 59 (3): 379–407, doi:10.2307/1969708, ISSN 0003-486X, JSTOR 1969708, MR 0061078
• Lachlan, A.H. (1966a), "Lower Bounds for Pairs of Recursively Enumerable Degrees", Proceedings of the London Mathematical Society, 3 (1): 537–569, CiteSeerX 10.1.1.106.7893, doi:10.1112/plms/s3-16.1.537.
• Lachlan, A.H. (1966b), "The impossibility of finding relative complements for recursively enumerable degrees", J. Symb. Log., 31 (3): 434–454, doi:10.2307/2270459, JSTOR 2270459.
• Lachlan, A.H.; Soare, R.I. (1980), "Not every finite lattice is embeddable in the recursively enumerable degrees", Advances in Mathematics, 37: 78–82, doi:10.1016/0001-8708(80)90027-4.
• Nies, André; Shore, Richard A.; Slaman, Theodore A. (1998), "Interpretability and definability in the recursively enumerable degrees", Proceedings of the London Mathematical Society, 77 (2): 241–291, CiteSeerX 10.1.1.29.9588, doi:10.1112/S002461159800046X, ISSN 0024-6115, MR 1635141
• Post, Emil L. (1944), "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, 50 (5): 284–316, doi:10.1090/S0002-9904-1944-08111-1, ISSN 0002-9904, MR 0010514
• Sacks, G.E. (1964), "The recursively enumerable degrees are dense", Annals of Mathematics, Second Series, 80 (2): 300–312, doi:10.2307/1970393, JSTOR 1970393.
• 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, ISSN 1073-2780, MR 1739227
• Simpson, Stephen G. (1977), "First-order theory of the degrees of recursive unsolvability", Annals of Mathematics, Second Series, 105 (1): 121–139, doi:10.2307/1971028, ISSN 0003-486X, JSTOR 1971028, MR 0432435
• Thomason, S.K. (1971), "Sublattices of the recursively enumerable degrees", Z. Math. Logik Grundlag. Math., 17: 273–280, doi:10.1002/malq.19710170131.
• Yates, C.E.M. (1966), "A minimal pair of recursively enumerable degrees", Journal of Symbolic Logic, 31 (2): 159–168, doi:10.2307/2269807, JSTOR 2269807.

인라인 인용구