튜링 감소

계산가능성 이론에서 의사결정 $문제{\displaystyle }$ A ${\displaystyle$A}에서$$ 의사결정 $문제{\displaystyle }$ B$$${\displaystyle B}($ 1967, Soare 1987)에 대한 Oracle이 주어지는$$ 문제 $A{\displaystyle }$ ${\displaystyle A}$을(를) 결정하는 Oracle 시스템이다.$$ B를 해결하기 위한 서브루틴이 있었다면$$ $A{\displaystyle }$ ${\displaystyle A}$을(를) 해결하는 데 사용할 수 있는 알고리즘으로 이해할 수 있다. 그 개념은 기능 문제에 유사하게 적용될 수 있다.

A{A\displaystyle}에서 B{B\displaystyle}에 튜링 축소 존재하는데, 그 다음에 B{B\displaystyle}[를]를 위해 알고리즘 A{A\displaystyle}, B{B\displaystyle}을 위한 곳이 신탁 기계 A{\displaystyle 컴퓨팅 각 장소에 알고리즘을 삽입하여 알고리즘을 만드는데 사용될 수 있다. A}$$ $Oracle{\displaystyle }$ ${\displaystyle$ B$}$에 대해 Oracle을 쿼리하지만$,$ Oracle 시스템이 Oracle을 쿼리하는 횟수가 많기 때문에 결과 $알고리즘$이 B ${\displaystyle$ B$}$에 대한 $알고리즘$이나 Oracle$$$$시스템 컴퓨팅 A {\$displaystyle A$}보다 더 많은 시간을 무증상으로 요구할 수 있다$.$Acle 머신은 다항식 시간에 실행되며 Cook 감소로 알려져 있다.

상대적 계산능력에 대한 최초의 공식적 정의는 1939년 Alan Turing에 의해 신탁기계의 관점에서 제시되었다. 이후 1943년과 1952년 스테판 클린은 재귀적 기능의 측면에서 동등한 개념을 정의했다. 1944년에 에밀 포스트는 이 개념을 언급하기 위해 "Turing remedcability"라는 용어를 사용했다.

정의

두 세트 $A{\displaystyle }$ ,${\displaystyle B}$ ${\displaystyle \subseteq }$ ${\displaystyle N\mathbb{}}$ {\$displaystyle$ A$,B\subseteq \mathb$ {$N} }$을(를) 자연 숫자로 지정하면 $A{\displaystyle }$ ${\displaystyle A}$을(를) $B{\displaystyle }$ ${\displaystytle B$}(으)로 축소할$$ 수 있다고$$ 말하고 쓰십시오.

${\displaystyle A\leq _{T}B}$

오라클 B로 실행될 때 A의 특성 함수를 계산하는 오라클 머신이 있다면. 이 경우, 우리는 또한 A가 B-recursive이고 B-computable이라고 말한다.

오라클 B와 함께 실행할 때 도메인 A와 함께 부분 함수를 계산하는 오라클 머신이 있다면 A는 B-recursuriously 열거되며 B-computer로 열거된다고 한다.

We say ${\displaystyle A}$ is Turing equivalent to ${\displaystyle B}$ and write ${\displaystyle A\equiv _{T}B\,}$ if both ${\displaystyle A\leq _{T}B}$ and ${\displaystyle B\leq _{T}A.}$ The equivalence classes of Turing equivalent sets are called Turing degrees. 세트 $X{\displaystyle }$ ${\displaystyle X}$의 튜링 정도는 ${\displaystyle \mathbf{\text{dg}}}$( ${\displaystyle X}$) ${\displaystyle {\textbf {deg}(X)}$로 기록된다$.$

Given a set ${\displaystyle {\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )}$, a set ${\displaystyle A\subseteq \mathbb {N} }$ is called Turing hard for ${\displaystyle {\mathcal {X}}}$ if ${\displaystyle X\leq _{T}A}$ for all ${\displaystyle X\in {\mathcal$${X$ ${\displaystyle 추가적}$으로 A ${\displaystyle \in }$ X ${\$인 경우$,$ $X{\displaystyle \mathcal{}}${\$displaystyle${\$mathcal {X$에 대해 {\$displaystystyle A}$을(를) 튜링 완료라고 한다.

튜링 완전성과 계산적 보편성의 관계

위에서 정의한 것과 같이 튜링 완전성은 컴퓨팅 보편성의 관점에서 튜링 완전성에 부분적으로만 해당된다. 특히 튜링 기계는 정지 문제(즉, 최종적으로 정지하는 입력의 집합)가 다수 1이면 범용 튜링 기계다. 따라서 컴퓨터가 계산적으로 보편화되기 위해서는 필요하지만 불충분한 조건은 컴퓨터의 중지 문제가 반복적으로 열거된 $집합$의 X ${\$ {$X}$에 대해 튜링 완료라는 것이다. 기계에 의해 받아들여지는 언어 자체가 재귀적으로 열거되지 않는 경우가 있기 때문에 불충분하다.

예

$W{\displaystyle {}_{}}$ ${\displaystyle e_{}}$ ${\$는 인덱스 e가 있는 튜링 기계가 중지하는 입력 값 집합을 나타낸다$$. Then the sets ${\displaystyle A=\{e\mid e\in W_{e}\}}$ and ${\displaystyle B=\{(e,n)\mid n\in W_{e}\}}$ are Turing equivalent (here ${\displaystyle (-,-)}$ denotes an effective pairing function). A reduction showing ${\displaystyle A\leq _{T}B}$ can be constructed using the fact that ${\displaystyle e\in A\Leftrightarrow (e,e)\in B}$. Given a pair ${\displaystyle (e,n)}$, a new index ${\displaystyle i(e,n)}$ can be constructed using the s_mn theorem such that th$e{\displaystyle }$ (${\displaystyle e}$ , ${\displaystyle n}$) ${\displaystyle i(e,n)}$에 의해 코드화된 프로그램은 입력을 무시하고$$ 입력 n에 있는 인덱스 e로 기계의 계산을 시뮬레이션할 뿐이다. 특히 인덱스 $i{\displaystyle (e}$, ${\displaystyle n}$) ${\displaystyle i(e,n)}$이(가) 있는 시스템은 모든 입력에서 중지되거나 입력되지 않을 때 중지된다$$. 따라서 $i{\displaystyle }$( ${\displaystyle e}$, n${\displaystyle }$) ${\displaystyle \in }$ ${\displaystyle A}$ ${\displaystyle \iff }$( e${\displaystyle }$, ${\displaystyle n}$) ${\displaystyle \in }$ ${\displaystyle B}$ ${\displaystyle i(e,n)\in$ A$\Leftrightarrow (e,n)\in B}$은 e와 n을 모두 보유한다. 함수 I는 계산 가능하기 때문에 $B{\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ A ${\displaystyle B\leq _{T}A}$을(를) 보여준다$.$ 여기서 제시된 감소는 튜링 감소뿐만 아니라 아래에서 논의된 일대일 감소다.

특성.

• 모든 세트는 그것의 보완물과 동등한 튜링이다.
• 계산 가능한 모든 세트는 다른 모든 세트로 튜링 감소가 가능하다. 계산 가능한 세트는 오라클 없이 계산될 수 있기 때문에 주어진 오라클을 무시하는 오라클 머신에 의해 계산될 수 있다.
• The relation ${\displaystyle \leq _{T}}$ is transitive: if ${\displaystyle A\leq _{T}B}$ and ${\displaystyle B\leq _{T}C}$ then ${\displaystyle A\leq _{T}C}$. Moreover, ${\displaystyle A\leq _{T}A}$ holds for every set A, and thus the relation ${\dis$$Playstyle$ \$leq$_{$T}$는 사전 주문($A{\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ B$${\$displaystyle A\leq _${T$}B$$}$ 및 $B{\displaystyle }$ ${\displaystyle {}_{}}$ T ${\displaystyle A_{}}$ ${\displaystyle B\leq _{T}A}$가 $반드시{\displaystyle }$ ${\displaystyle A}$= B$${\$displaystystystyle A=B}$를 의미하지는 않기 때문에 부분 순서가 아니다).$$
• ${\displaystyle (}$A , B )${\디스플레이$ 스타일 $(A,B)}$ 세트 쌍이 있는데, A는$$ B로 튜링할 수 없고, B는 A로 튜링할 수 없다. 따라서 $\le {\displaystyle {}_{}}$ ${\displaystyle T_{}}$ ${\$는 전체 순서가 아니다$$.
• $\le {\displaystyle {}_{}}$ ${\displaystyle T_{}}$ ${\$에 따라 세트의 순서가 무한히 감소하므로 이러한 관계는 근거가 없다$.$
• 모든 세트는 튜링 점프 자체로 튜링 감소가 가능하지만, 세트의 튜링 점프는 원래 세트로 절대 튜링 감소가 가능하지 않다.

감액 사용

세트 $B{\displaystyle }$ ${\displaystyle$ $B$$}$에서 $세트{\displaystyle }$ A ${\displaystyle$ A$}($으)로$$ 한 요소를 축소할 때마다$$ 단 몇 번의 $단계$에서만$$단일 $요소$가 A {\$displaystyle$ A$}$에 있는지 확인해야 $하므로{\displaystyle }$$,$ $세트$ B {\$displaystyle$ B}에 대한 정보량만 정확하게 많은 구성원 정보를 조회할 수 있다$.$$\$$displaystyle A}$의 단일 비트 계산에 $사용되는 \displaystyle$ B}이(가) 논의되며$$, 이는 사용 함수에 의해 정밀하게 이루어진다. 형식적으로 $축소$의 사용은 각 자연수 $n{\displaystyle }$ {\displaystyle $n{\displaystyle }$}을$($를) A {\$displaystyle$ $A$에서 n ${\displaystyle n}$의 멤버십을 결정하면서 축소에 의해 쿼리된 가장$$ 큰 자연수 $m{\displaystyle }$ ${\displaystyle m}$에 보내는 기능이다.

더 강력한 감소

Turing 환원성보다 더 강력한 감소를 생성하는 두 가지 일반적인 방법이 있다. 첫 번째 방법은 오라클 질의 횟수와 방식을 제한하는 것이다.

• 요소 $n{\displaystyle }$ ${\displaystyle n}$이(가$$) $A{\displaystyle }$ ${\displaystyle A}$에 있는$$ 경우, $그리고{\displaystyle }$f (${\displaystyle n)}${\$displaystyle f(n)$가 B$${\$displaystyle$B$\}$에 있는 경우$$$,$ Set $A{\displaystyle }$ ${\$$displaystystyle$ $A}$을(가$$)로 일대일 수 있음$$. 이러한 $함수$를 사용할 수 있음.d turing 감소 생성($f{\displaystyle (n}$ )$${\$displaystyle f(n)}$ 계산, 오라클 쿼리$,$ 결과 해석)
• 진리 테이블 감소 또는 약한 진리 테이블 감소는 모든 오라클 쿼리를 동시에 제시해야 한다. 진실표 감소에서, 감소는 또한 부울함수(진실표)를 주는데, 이 부울함수(진실표)는 질의에 대한 답변이 주어졌을 때, 감소의 최종 답을 산출한다. 약한 진리표 감소에서, 감소는 주어진 해답에 따라 추가 계산을 위한 기초로 오라클 해답을 사용한다(그러나 오라클을 사용하지 않음). 동등하게, 약한 진리표 감소는 계산 가능한 함수에 의해 제한되는 것이다. 이러한 이유로, 약한 진리표 감소는 때때로 "경계 튜링" 감소라고 불린다.

더 강력한 환원성 개념을 만드는 두 번째 방법은 튜링 감소를 구현하는 프로그램이 사용할 수 있는 계산 자원을 제한하는 것이다. 이러한 감소의 계산 복잡성에 대한 한계는 P와 같은 부차적인 수업을 공부할 때 중요하다. 다항식으로 실행되는$$ $A{\displaystyle }$ ${\displaystyle A}$을(를) $B{\displaystyle }$ ${\displaystyle B}($으)로$$ Turing을 줄인 경우$$ 집합 A는 다항식 $시간{\displaystyle }$ B$${\$displaystyle B}$로 축소할 수 있다. 로그 공간 축소 개념도 비슷하다.

이러한 감소는 Turing 감소보다 동등성 등급에 대한 세부적인 구분을 제공하고 더 제한적인 요건을 충족한다는 점에서 더 강하다. 결과적으로, 그러한 감소는 찾기 어렵다. 같은 세트에 대한 튜링 감소가 존재하더라도 한 세트에서 다른 세트로 다원 감소를 구축할 방법이 없을 수 있다.

감소 약세

Church-Turing 논문에 따르면 튜링 감소는 효과적으로 계산할 수 있는 감소의 가장 일반적인 형태라고 한다. 그럼에도 불구하고, 더 약한 감소도 고려된다. Peano 산술 $공식$으로 B {\$displaystyle$ A$}$을(를$)$ 매개변수로 정의할$$ 수 있는$$ 경우$$ $Set{\displaystyle }$ A$${\$displaystyle$ $B$$}$은(는) $B{\displaystyle }$ ${\$$displaystyle$ $B$$}$에서 산술적이라고 한다$$. The set ${\displaystyle A}$ is hyperarithmetical in ${\displaystyle B}$ if there is a recursive ordinal ${\displaystyle \alpha }$ such that ${\displaystyle A}$ is computable from ${\displaystyle B^{(\alpha )}}$, the α-iterated Turing jump of ${\displaystyle B}$. 상대적 구성성의 개념은 집합 이론에서 중요한 축소 가능성 개념이다.

참고 항목

• 카르프 감소

메모들

참조

• 1965년 M. Davis, Ed. Undistibleabled(불해독성)—New York, Raven, Underable Problems(불해독성 제안), Underable Problems(불해독성 문제) 및 Computable Functions(계산 가능한 기능)에 관한 기본 문서. 2004년 도버의 재인쇄. ISBN0-486-43228-9.
• 1952년 S. C. Kleene. 메타매틱스 소개. 암스테르담: 노스홀랜드.
• S. C. Kleene과 E. L. Post, 1954. "재귀 불능성의 상위 반격" 수학 연혁 대 2 n 59, 379–407.
• Post, E. L. (1944). "Recursively enumerable sets of positive integers and their decision problems" (PDF). Bulletin of the American Mathematical Society. 50: 284–316. doi:10.1090/s0002-9904-1944-08111-1. Retrieved 2015-12-17.
• A. 튜링, 1939년 "서수자에 기초한 논리 체계" 런던수학협회의 의사진행, 2 v. 45, 페이지 161–228. 1965년 M. Davis Ed. "The Underdicabled"에서 다시 출판되었다.
• H. 로저스, 1967년 재귀함수와 유효 계산가능성의 이론. 맥그로힐
• R. 소어, 1987. 반복적으로 셀 수 있는 세트와 도, 스프링거.
• Davis, Martin (November 2006). "What is...Turing Reducibility?" (PDF). Notices of the American Mathematical Society. 53 (10): 1218–1219. Retrieved 2008-01-16.

외부 링크

• NIST 알고리즘 및 데이터 구조 사전: 튜링 감소