교회 – 튜링 논문

Church–Turing thesis

교회-튜링 논문(Church–Turing technology)은 계산가능성 이론에서 계산가능한 함수의 성질에 관한 논문으로 튜링 이론, 튜링 이론,[1][2] 튜링 이론, 교회-튜링 추측, 교회 추측, 튜링 이론이라고도 합니다. 그것은 자연수에 대한 함수튜링 기계에 의해 계산될 수 있는 경우에만 효과적인 방법으로 계산될 수 있다고 말합니다. 이 논문의 이름은 미국 수학자 알론조 처치와 영국 수학자 알란 튜링의 이름을 따서 지어졌습니다. 계산 가능한 함수에 대한 정확한 정의 이전에, 수학자들은 종이와 연필 방법으로 계산 가능한 함수를 설명하기 위해 효과적으로 계산 가능한 비공식 용어를 자주 사용했습니다. 1930년대에 계산 가능성의 개념을 공식화하기 위한 몇 가지 독립적인 시도가 있었습니다.

  • 1933년, 쿠르트 괴델자크 헤르브란트와 함께 일반 재귀 함수의 클래스에 대한 정의를 공식화했습니다: 구성, 재귀, 최소화 하에서 닫히고 0, 계승 모든 사영을 포함하는 가장 작은 클래스의 함수입니다.
  • 1936년 알론조 교회는 λ-계산기라고 불리는 함수를 정의하는 방법을 만들었습니다. 그는 λ-계산기 안에서 처치 숫자라고 불리는 자연수의 부호화를 정의했습니다. 만약 교회 숫자에 해당하는 함수가 λ 계산기의 항으로 표현될 수 있다면, 자연수에 대한 함수는 λ 계산 가능 함수라고 불립니다.
  • 또한 Church의 연구를 배우기 전인 1936년,[6] Alan Turing은 현재 Turing machine이라고 불리는, 테이프에서 기호를 조작함으로써 입력으로부터 계산을 수행할 수 있는 기계에 대한 이론적인 모델을 만들었습니다. 자연수를 기호의 시퀀스로 적절한 인코딩이 주어지면, 일부 튜링 기계가 인코딩된 자연수에 대해 해당 함수를 계산하면 자연수에 대한 함수는 튜링 계산 가능하다고 불립니다.

Church, Kleene, Turing은 공식적으로 정의된 계산 가능한 함수의 세 가지 클래스가 일치한다는 것을 증명했습니다: 함수는 튜링 계산 가능한 경우에만 λ 계산 가능하고 일반 재귀적인 경우에만 가능합니다. 이것은 수학자들과 컴퓨터 과학자들이 계산 가능성의 개념이 이 세 가지 동등한 과정에 의해 정확하게 특징지어진다고 믿게 만들었습니다. 계산 가능성을 특성화하려는 다른 공식적인 시도들은 이후 이 믿음을 강화시켰습니다(아래 참조).

반면, Church–Turing 논문은 위의 세 가지 공식적으로 정의된 계산 가능 함수 클래스가 효과적으로 계산 가능한 함수의 비공식적 개념과 일치한다고 말합니다. 이 논문은 거의 보편적인 수용성을 가지고 있지만, 효과적인 계산 가능성의 개념이 비공식적으로만 정의되어 있기 때문에 공식적으로 증명될 수 없습니다.

처음 시작된 이래로, 우리 우주에서 컴퓨터에 의해 물리적으로 실현될 수 있는 것(물리적 교회-튜링 논문)과 효율적으로 계산될 수 있는 것(교회-튜링 논문(복잡성 이론)에 대한 진술을 포함하여 원래 논문에 대한 변형이 발생했습니다. 이러한 변형은 Church나 Turing에 의한 것이 아니라, 복잡도 이론과 디지털 물리학에서의 후기 작업에서 발생합니다. 이 논문은 마음의 철학(아래 참조)에도 시사점을 주고 있습니다.

Church's and Turing's words에서의 진술

J. B. Rosser(1939)는 "효과적인 계산 가능성"의 개념에 대해 다음과 같이 언급합니다. "CC와 RC(Church's and Rosser의 증명)의 존재는 분명히 '효과적'의 정확한 정의를 전제로 합니다. 여기서 '효과적인 방법'은 각 단계가 정확하게 미리 결정되고 유한한 단계에서 답을 생성할 수 있는 방법이라는 다소 특별한 의미로 사용됩니다."[12] 따라서 부사 "효과적"은 "1a: 결정된, 결정적인, 또는 원하는 효과를 생산하는 것"과 "결과를 생산할 수 있는 것"이라는 의미로 사용됩니다.[13][14]

다음에서 "효과적으로 계산 가능한" 단어는 "어떤 직관적으로 '효과적인' 수단에 의해 생산되는" 것을 의미하고 "효과적으로 계산 가능한" 단어는 "튜링 기계 또는 동등한 기계 장치에 의해 생산되는" 것을 의미합니다. 교회가 주관하는 1938년 박사학위 논문 '정규기초한 논리 체계'에서 튜링이 각주에서 제시한 '정의'는 사실상 같습니다.

우리는 기계에 의해 계산 가능한 함수를 의미하기 위해 "계산 가능 함수"라는 표현을 사용할 것이며, "효과적으로 계산 가능한" 것은 이러한 정의 중 하나와 특정한 식별 없이 직관적인 아이디어를 가리킬 것입니다.[15]

논문은 다음과 같이 말할 수 있습니다. 효과적으로 계산 가능한 모든 함수는 계산 가능한 함수입니다.[16] 처치는 또한 "어떤 계산 절차도 튜링 머신으로 표현될 수 없는 한 알고리즘으로 간주되지 않을 것"이라고 말했습니다.[citation needed] 튜링은 이렇게 말했습니다.

"어떤 함수의 값이 순수하게 기계적인 과정에 의해 발견될 수 있다면 효과적으로 계산할 수 있다"고 언급했습니다. 우리는 기계에 의해 수행될 수 있는 순수한 기계적 과정에 의해 이것을 문자 그대로 받아들일 수 있습니다. 전개가... 효과적인 계산 가능성을 가진 계산 가능성의 식별로 이어집니다. [는 위에서 인용한 각주입니다.][15]

역사

1930년대 논리학자들에게 중요한 문제 중 하나는 수학적 진실과 수학적 거짓을 분리하는 기계적 절차가 있는지를 묻는 [17]다비드 힐베르트빌헬름 아커만엔체이둥 문제였습니다. 이 탐색을 위해서는 "알고리즘" 또는 "효과적인 계산 가능성"이라는 개념을 고정시켜야 합니다. 적어도 탐색이 시작될 수 있을 정도로 잘 해야 합니다.[18] 그러나 처음부터 알론조 교회의 시도는 오늘날까지 계속되는 논쟁으로 시작되었습니다.[19] "효과적인 계산 가능성"의 개념은 (i) 공리적 체계에서 "축 또는 공리"가 될 것인가, (ii) 둘 이상의 명제를 "식별"하는 정의불과하였는가[clarify], (iii) 자연적 사건의 관찰에 의해 검증될 경험적 가설, 또는 (iv) 논증을 위한 제안에 불과하였는가(즉, "논문").

1930~1952년경

문제를 연구하는 과정에서 Church와 그의 제자 Stephen Kleene은 λ 정의 가능한 함수의 개념을 소개했고, 그들은 정수론에서 자주 접하게 되는 몇 가지 큰 클래스의 함수가 λ 정의 가능하다는 것을 증명할 수 있었습니다. 논쟁은 Church가 Gödel에게 "효과적으로 계산 가능한" 함수를 λ 정의 가능한 함수로 정의해야 한다고 제안하면서 시작되었습니다. 그러나 괴델은 이 제안을 납득하지 못했고 "매우 불만족스럽다"고 말했습니다.[21] 오히려 괴델은 Church(1934-1935)와의 서신에서 "효과적인 계산 가능성"의 개념을 공리화할 것을 제안했습니다.

당시 그의 [괴델]의 유일한 아이디어는 정의되지 않은 개념으로서 효과적인 계산 가능성의 관점에서 일반적으로 받아들여지는 이 개념의 특성을 구현하는 일련의 공리를 진술하고 그 기반 위에서 무언가를 하는 것이 가능할 수 있다는 것이었습니다.[22]

그러나 괴델은 더 이상의 지침을 주지 않았습니다. 결국 그는 괴델이 1934년 프린스턴 NJ에서 강의한 내용을 자세히 설명한 것을 헤르브란트의 제안으로 수정한 자신의 재귀를 제안했습니다. 그러나 그는 이 두 가지 아이디어가 "희석학적으로" 만족스럽게 식별될 수 있다고 생각하지 않았습니다.[23]

다음으로, 유효 계산 가능성이라는 두 가지 개념의 동등성을 확인하고 증명할 필요가 있었습니다. Church와 J. Barkley Rosser의 도움으로 Kleene은 λ-계산과 "일반적인" 재귀를 장착하고 두 계산이 동등하다는 것을 보여주는 증거를 (1933년, 1935년) 만들었습니다. Church는 이후 그의 방법을 Herbrand의 사용을 포함하도록 수정했습니다.괴델 재귀와 그 후 엔체이둥 문제가 해결되지 않는다는 것을 증명(1936)했습니다: 잘 형성된 공식베타 정규 형태를 갖는지 여부를 결정할 수 있는 알고리즘은 없습니다.[24]

수년 후, 괴델은 데이비스에게 보낸 편지(1965년경)에서 "이 [1934년] 강의 당시 그는 자신의 재귀 개념이 모든 가능한 재귀를 포함한다고 전혀 확신하지 못했습니다."[25]라고 말했습니다. 1963년부터 1964년까지 괴델은 헤르브란트를 거부했습니다.괴델 재귀와 튜링 기계를 "알고리즘" 또는 "기계적 절차" 또는 "공식 시스템"의 정의로 선호하는 λ-계산기.

자연법칙으로 이어지는 가설? 1936년 말 앨런 튜링의 논문(엔체이둥 문제가 해결되지 않는다는 것을 증명하기도 함)은 구두로 전달되었지만 아직 인쇄물에 등장하지 않았습니다.[27] 반면 에밀 포스트의 1936년 논문이 등장하여 튜링의 연구와 독립적으로 인증을 받았습니다.[28] 포스트는 λ 연산과 재귀를 이용한 효과적인 계산 가능성에 대한 처치의 "식별"에 강하게 동의하지 않았으며 다음과 같이 말했습니다.

실제로 교회와 다른 사람들이 이미 수행한 작업은 작업 가설 단계를 상당히 뛰어 넘습니다. 그러나 이 식별 정보를 정의에 따라 가리려면 지속적인 확인이 필요합니다.[29]

오히려 그는 "효과적인 계산 가능성"의 개념을 "정의나 공리"가 아니라 "자연법"에 대한 귀납적 추론으로 이어질 수 있는 "작업 가설"에 불과하다고 여겼습니다.[30] 이 아이디어는 Church에 의해 "날카롭게" 비판을 받았습니다.[31]

따라서 포스트는 1936년 논문에서 쿠르트 괴델이 1934-1935년에 교회에 논문을 공리 또는 일련의 공리로 표현할 수 있다고 제안한 것을 무시하고 있었습니다.[22]

튜링은 또 다른 정의를 추가하고, Rosser는 세 가지를 모두 동일시합니다. 짧은 시간 안에 튜링의 1936-1937년 논문 "계산 가능한 수에 대하여, 엔체이둥 문제에 적용하다"[27]가 나타났습니다. 그는 그의 a-기계(현재 튜링 기계 추상 계산 모델로 알려져 있음)의 도입과 함께 "효과적인 계산 가능성"이라는 또 다른 개념을 언급했습니다. 그리고 1936-1937년 그의 논문에 "부록"으로 추가된 증명 스케치에서 튜링은 λ-계산기와 튜링 기계에 의해 정의된 함수의 클래스가 일치한다는 것을 보여주었습니다. 처치는 튜링의 분석이 얼마나 설득력이 있는지 재빨리 알아차렸습니다. 튜링의 논문에 대한 그의 리뷰에서 그는 튜링의 개념이 "일반적인 (명시적으로 정의되지 않은) 의미에서 효과가 있는 식별을 즉시 명확하게" 만들었다는 것을 분명히 했습니다.[33]

튜링은 몇 년 후에 Church와 Kleene처럼 기계적 계산 에이전트에 대한 공식적인 정의가 올바른 것이라고 제안했습니다.[34] 따라서 1939년까지 Church(1934)와 Turing(1939)은 그들의 "공식 시스템"이 "효과적인 계산 가능성"의 정의가 되어야 한다고 개별적으로 제안했지만,[35] 그들의 진술을 논문으로 틀지는 않았습니다.

Rosser(1939)는 정의로서의 세 가지 개념을 공식적으로 확인했습니다.

가지 정의는 모두 동등하므로 어느 것을 사용하든 상관없습니다.[36]

Kleene논문 I 제안합니다. 이것은 Kleene에게 "논문"이라는 명백한 표현을 남겼습니다. 1943년 크린은 "논문 I"을 제안했습니다.[37]

이 휴리스틱 사실 [일반 재귀 함수는 효과적으로 계산 가능] ... Church는 다음과 같은 논문을 발표하도록 이끌었습니다. 튜링의 컴퓨터 기계에 대한 설명에도 같은 논제가 함축되어 있습니다.

논문 I. 효과적으로 계산 가능한 모든 함수(효과적으로 결정 가능한 술어)는 일반 재귀적이다 [클렌의 이탤릭체]

효과적으로 계산 가능한(효과적으로 결정 가능한) 용어에 대한 정확한 수학적 정의가 필요했기 때문에, 우리는 이 논문을 그것의 정의로 받아들일 수 있습니다.

...이 논문은 포스트와 교회가 강조하는 가설의 성격을 가지고 있습니다. 논문과 그 역을 정의로 본다면, 가설은 정의에서 발전된 수학 이론의 적용에 관한 가설입니다. 가설의 수용을 위해서는 우리가 제시한 것처럼 상당히 설득력 있는 근거들이 있습니다.

교회-튜링 논문: 스티븐 크린(Stephen Kleene)은 메타수학 개론에서 재귀적 실현 가능성에 대한 이론을 사용하여 마침내 "교회의 논문"과 "튜링의 논문"을 공식적으로 명명합니다. Kleene은 Church-Kleene 람다 정의 가능성의 용어에서 Gödel-Kleene 재발명성(부분 재귀 함수)의 용어로 그의 연구를 제시하는 것으로 전환했습니다. 이 전환에서 크린은 괴델의 일반 재귀 함수를 수정하여 E.J. 브루어의 직관주의에서 문제의 해결 불가능성을 증명할 수 있도록 했습니다. 그의 논리학 대학원 교재에는 "교회의 논문"이 소개되어 있고, 기초적인 수학적 결과는 실현 불가능하다는 것이 증명되어 있습니다. 다음으로, Kleene은 에밀 포스트의 작업에 기초한 튜링 기계의 단순화된 유도를 사용하여 결과가 계산 불가능한 것으로 나타난 "튜링의 논문"을 발표합니다. 이 두 가지 모두 "Theorem XXX"를 사용하여 동등함이 입증되었습니다.

논문 I. 효과적으로 계산 가능한 모든 함수(효과적으로 결정 가능한 술어)는 일반적으로 재귀적입니다.[38]

정리 XXX: 다음과 같은 클래스의 부분 함수는 공확장적입니다. 즉, (a) 부분 재귀 함수, (b) 계산 가능 함수...[39]

튜링의 논문: 당연히 계산 가능한 것으로 간주되는 모든 함수가 그의 정의에 따라 계산 가능하다는 튜링의 논문, 즉 그의 기계 중 하나에 의해 계산 가능하다는 논문은 정리 XXX에 의한 처치의 논문과 동등합니다.[39]

마지막으로 Kleene은 William Boon의 비평에서 요구한 Alan Turing의 논문 "The Word Problem in Semi-Groups with Cancellation"에서 개념을 명확히 하는 데 도움을 주는 섹션에서 "Church-Turing 논문"이라는 용어를 처음으로 사용합니다.[40]

후대의 발전

"효과적인 계산 가능성"의 개념을 이해하려는 시도는 1980년 Robin Gandy(튜링의 학생이자 친구)로 하여금 (튜링 기계에 의해 행동되는 인간의 계산과는 대조적으로) 기계 계산을 분석하도록 이끌었습니다. Gandy는 세포 오토마타(Conway의 삶의 게임을 포함), 병렬성 및 결정성 오토마타에 대한 호기심과 분석을 통해 4가지 "원칙(또는 제약)… 어떤 기계든 충족시켜야 한다는 주장"을 제안하게 되었습니다.[41] 그의 가장 중요한 네 번째, "인과성의 원리"는 "효과와 신호의 전파의 무한한 속도; 현대 물리학은 거리에서 순간적인 작용의 가능성을 거부"하는 것에 기반을 두고 있습니다.[42] 이러한 원리들과 몇 가지 추가적인 제약들로부터, (1a) 부품들의 선형 차원들에 대한 하한, (1b) 전파 속도(광속)에 대한 상한, (2) 기계의 이산 진행, 그리고 (3) 결정론적 행동에 대한 그는 "원리들을 만족하는 장치에 의해 계산될 수 있는 것"이라는 정리를 만들어냅니다.IV는 계산 가능합니다."[43]

1990년대 후반 윌프리드 지그는 "비공식적인 개념을 날카롭게 하고, 그 일반적인 특징을 공리적으로 공식화하고, 공리적인 틀을 조사하는" 목적으로 튜링과 간디의 "효과적인 계산 가능성" 개념을 분석했습니다.[44] Sieg는 1997년과 2002년의 연구에서 "기계적으로 진행되는 인간 컴퓨팅 에이전트"인 컴퓨터의 동작에 대한 일련의 제약을 제시합니다. 이러한 제약 조건은 다음과 같이 줄어듭니다.

  • "(B.1) (경계) 컴퓨터가 즉시 인식할 수 있는 기호 구성의 수에는 고정된 경계가 있습니다.
  • "(B.2) (경계) 컴퓨터가 들어갈 수 있는 내부 상태의 수에는 고정된 경계가 있습니다.
  • "(L.1) (Locality) 컴퓨터는 관측된 기호 구성의 요소만 변경할 수 있습니다.
  • "(L.2) (Locality) 컴퓨터는 한 기호 구성에서 다른 기호 구성으로 주의를 이동할 수 있지만, 새로 관찰된 구성은 바로 이전에 관찰된 구성의 제한된 거리 내에 있어야 합니다.
  • "(라)(결정권) 즉시 인식 가능한 (하위) 구성은 다음 계산 단계(및 id [즉시 설명])를 고유하게 결정합니다. 다른 방법으로 "관찰된 구성과 함께 컴퓨터의 내부 상태는 다음 계산 단계와 다음 내부 상태를 고유하게 고정합니다."[45]라고 말했습니다.

그 문제는 학계 내에서 활발한 논의가 계속되고 있습니다.[46][47]

정의로서의 논문.

그 논문은 평범한 수학적 정의에 불과하다고 볼 수 있습니다. 이 주제에 대한 괴델의 논평은 "기계적 계산 가능성에 대한 정확한 정의는 튜링에 의해 의심의 여지 없이 확립되었습니다"[48]와 같은 견해를 시사합니다. 논문을 정의에 불과한 것으로 보는 경우는 로버트 1세에 의해 명시적으로 이루어졌습니다. 또한 튜링의 계산 가능성에 대한 정의가 연속 함수의 엡실론-델타 정의보다 정확할 가능성이 낮다는 주장도 있습니다.[5]

논문의 성공여부

효과적인 계산 가능성/계산 가능성을 설명하기 위해 다른 형식론(재귀 에도 λ-계산기 및 튜링 기계)이 제안되었습니다. Kleene (1952)은 Kurt Gödel 1936의 "계 S에서1 무시할 수 있는" 함수를 목록에 추가하고, Emil Post (1943년, 1946년)의 "정규적인 [정상적인] 계"를 추가합니다.[49] 1950년대에 Hao WangMartin Davis는 단일 테이프 튜링 기계 모델을 크게 단순화했습니다(Post-Turing machine 참조). Marvin Minsky는 이 모델을 두 개 이상의 테이프로 확장하고 테이프를 "업다운 카운터"로 크게 단순화했으며, Melzak과 Lambek은 이를 통해 현재 카운터 머신 모델로 더욱 발전했습니다. 1960년대 말과 1970년대 초에 연구원들은 카운터 머신 모델을 컴퓨터의 현대적 개념에 가까운 사촌격인 레지스터 머신으로 확장했습니다. 다른 모델로는 조합 논리마르코프 알고리즘이 있습니다. 구레비치는 콜모고로프와 우스펜스키(1953, 1958)의 포인터 기계 모델을 추가했습니다: "그들은 단지 계산 가능한 함수의 개념을 확장할 방법이 없다는 것을 스스로 확신시키기를 원했습니다."[50]

이러한 모든 기여는 모델이 튜링 기계와 계산상 동등하다는 증거를 포함합니다. 그러한 모델은 튜링 완전하다고 합니다. "효과적인 계산 가능성/계산 가능성"의 개념을 공식화하려는 이 모든 다양한 시도들이 동등한 결과를 낳았기 때문에, 이제 일반적으로 교회-튜링 논문이 옳다고 가정됩니다. 사실 괴델(Gödel, 1936)은 이보다 더 강력한 것을 제안했습니다. 그는 "S에서1 무시할 수 있는" 개념에 "절대적인" 무언가가 있음을 관찰했습니다.

또한 시스템 Si 중 하나 또는 트랜스피니트 유형의 시스템에서도 계산 가능한 함수가 S에서1 이미 계산 가능한 ['무작위'라는 것을 보여줄 수 있습니다. 따라서 '계산 가능'['무작위']라는 개념은 어떤 확실한 의미에서 '절대'인 반면, 실질적으로 다른 모든 친숙한 메타수학적 개념(예: 증명 가능, 정의 가능 등)은 본질적으로 정의된 시스템에 따라 달라집니다.[51]

증명에 비공식적으로 사용

계산 가능성 이론의 증명은 종종 엄격하고 형식적인 증명과 관련된 (종종 매우 긴) 세부 사항을 피하면서 함수의 계산 가능성을 확립하기 위해 Church–Turing 논문을 비공식적인 방식으로 호출합니다.[52] 함수가 튜링 기계에 의해 계산 가능하다는 것을 확립하기 위해, 일반적으로 함수가 어떻게 효과적으로 계산될 수 있는지에 대한 비공식적인 영어 설명을 제공하고, 그 함수가 튜링 계산 가능하다는 것을 "교회-튜링 논문에 의해" 결론을 내리는 것으로 충분하다고 간주됩니다.

Dirk van Dalen은 Church-Turing 논문의 비공식적인 사용을 설명하기 위해 다음과 같은 예를 제시합니다.[53]

예제: 각 무한 RE 집합은 무한 재귀 집합을 포함합니다.

증명: A가 무한 RE가 되도록 합니다. 우리는 A의 원소들을 효과적으로 나열합니다, n0, n, n1, n23, ...

이 목록에서 증가하는 하위 목록을 추출합니다: m = n을 입력하고, 많은 단계를 거친 후 n > m, m = n과 같은 n을 찾습니다. 이 절차를 반복하여 m > m 등을 찾습니다. 그러면 부분 집합 B={m, m, m, ...의 효과적인 목록이 생성됩니다.} A의, 속성i m < mi+1.

주장. B는 결정적입니다. 의 경우, kin B를 검정하기 위해서는 어떤 i에 대하여 k = m인지 확인해야 합니다. m의i 수열이 증가하고 있기 때문에 우리는 목록에서 기껏해야 k+1개의 원소를 만들어서 k와 비교해야 합니다. 만약 그들 중 k와 동치인 것이 없다면, B에서 k는 아닙니다. 이 테스트는 효과적이므로 B는 결정 가능하며 Church의 논문에 의해 재귀적입니다.

위의 예를 완전히 엄격하게 만들려면 튜링 기계, 즉 λ 함수를 신중하게 구성하거나 재귀 공리를 신중하게 호출하거나 기껏해야 계산 가능성 이론의 다양한 정리를 영리하게 호출해야 할 것입니다. 그러나 계산가능성 이론가는 튜링 계산가능성이 효과적으로 계산될 수 있는 것을 정확하게 포착한다고 생각하고, 집합 B를 결정하기 위한 효과적인 절차를 영어로 설명하기 때문에 계산가능성 이론가는 이것을 집합이 실제로 재귀적이라는 증거로 받아들입니다.

변주곡

교회-튜링 논문의 성공으로 논문의 변형이 제안되었습니다. 예를 들어, 물리적 교회-튜링 논문은 "물리적으로 계산 가능한 모든 함수는 튜링 계산 가능하다"[54]: 101 고 말합니다.

Church–Turing 논문은 한 모델의 계산이 다른 모델을 시뮬레이션할 수 있는 효율성에 대해서는 언급하지 않습니다. 예를 들어, 모든 튜링 기계를 시뮬레이션할 때 (다중 테이프) 범용 튜링 기계는 로그 감속 요인만 겪는다는 것이 증명되었습니다.[55]

Church–Turing 논문의 변형은 임의적이지만 "합리적인" 계산 모델이 효율적으로 시뮬레이션될 수 있는지 여부를 다룹니다. 이것은 (고전적인) 복잡성-이론적 교회-튜링 논문 또는 확장된 교회-튜링 논문으로도 알려진 [56]타당성 논문이라고 불리는데, 이는 교회나 튜링 때문이 아니라 복잡성 이론의 발전에서 점진적으로 실현되었습니다. "[57]확률론적 튜링 기계는 현실적인 계산 모델을 효율적으로 시뮬레이션할 수 있습니다." 여기서 '효율적으로'라는 단어는 최대 다항 시간 단축을 의미합니다. 이 논문은 원래 Ethan Bernstein과 Umesh Vazirani(1997)에 의해 계산 복잡도-이론적 교회-튜링 논문이라고 불렸습니다. 따라서 복잡성-이론적 교회-튜링 논문은 모든 '합리적인' 계산 모델이 다항식 시간에 계산될 수 있는 동일한 종류의 문제를 산출한다는 것을 가정합니다. 확률론적 다항 시간(BPP)이 결정론적 다항 시간(P)과 동일하다고 가정할 때, 복잡성-이론적 교회-튜링 논문에서 '확률론적'이라는 단어는 선택 사항입니다. 불변성 논문이라고 불리는 비슷한 논문이 Cees F에 의해 소개되었습니다. 슬롯과 피터 반 엠데 보아스. 다음과 같이 기술되어 있습니다: "'합리적인' 기계는 시간적으로는 다항식으로 제한된 오버헤드와 공간적으로는 상수 요인 오버헤드 내에서 서로 시뮬레이션할 수 있습니다."[58] 이 논문은 원래 STOC'84의 논문에 등장했는데, 이 논문은 튜링 기계에서 랜덤 액세스 머신의 시뮬레이션을 위해 다항 시간 오버헤드와 상수 공간 오버헤드가 동시에 달성될 수 있음을 보여주는 최초의 논문이었습니다.[59]

BQPBPP의 엄격한 수퍼세트인 것으로 나타나면 복잡성-이론적 교회-튜링 논문을 무효화할 것입니다. 즉, 효율적인 확률적 알고리즘이 없는 작업을 수행하는 효율적인 양자 알고리즘이 존재할 것입니다. 그러나 양자 컴퓨터는 항상 튜링 기계에 의해 시뮬레이션될 수 있기 때문에 이것은 원래의 교회-튜링 논문을 무효화하지 않을 것이지만 효율성 이유로 고전적인 복잡성-이론적 교회-튜링 논문을 무효화할 것입니다. 결과적으로, 양자 복잡성-이론적 교회-튜링 논문은 "양자 튜링 기계는 어떤 현실적인 계산 모델도 효율적으로 시뮬레이션할 수 있습니다."[57]라고 말합니다.

유진 에버바흐(Eugene Eberbach)와 피터 웨그너(Peter Wegner)는 교회-튜링(Church-Turing) 논문이 때때로 너무 광범위하게 해석된다고 주장하며, "튜링 기계는 알고리즘의 행동을 표현하지만, 알고리즘이 계산 가능한 것을 정확하게 포착한다는 광범위한 주장은 타당하지 않습니다."[60]라고 말합니다. 그들은 논문에 포착되지 않은 계산 형태가 오늘날 관련이 있다고 주장하며, 이를 그들은 슈퍼 튜링 계산이라고 부릅니다.

철학적 함의

철학자들은 교회-튜링 논문이 마음의 철학에 시사하는 바가 있다고 해석해왔습니다.[61][62][63] B. Jack Copeland는 장기적으로 튜링 기계에 의한 시뮬레이션을 배제하는 실제 결정론적 물리적 과정이 있는지에 대한 열린 경험적 질문이라고 말하고, 나아가 그러한 과정이 인간의 뇌의 작동에 관여하는지에 대한 열린 경험적 질문이라고 말합니다.[64] 또한 교회-튜링 논문과 물리학 사이의 관계와 하이퍼컴퓨팅의 가능성을 다루는 몇 가지 중요한 오픈 질문이 있습니다. 이 논문은 물리학에 적용될 때 다음과 같은 몇 가지 가능한 의미를 갖습니다.

  1. 우주는 튜링 기계와 동등하므로 비재귀적 기능을 계산하는 것은 물리적으로 불가능합니다. 이것은 강력한 Church–Turing 논문, 또는 Church–Turing–Deutsch 원리라고 불리며, 디지털 물리학의 기초입니다.
  2. 우주는 튜링 기계와 동등하지 않지만(즉, 물리 법칙은 튜링 계산 가능하지 않습니다), 계산 불가능한 물리적 사건은 하이퍼 컴퓨터의 구성을 위해 "흔들림 가능"하지 않습니다. 예를 들어, 물리학이 계산 가능한 실수와 달리 임의의 실수를 포함하는 우주는 이 범주에 속할 것입니다.
  3. 우주는 하이퍼 컴퓨터이며 이 속성을 활용하고 비재귀적 기능을 계산하기 위한 물리적 장치를 구축할 수 있습니다. 예를 들어, 양자 튜링 기계와 같은 엄격한 모델은 결정론적 튜링 기계와 동등하다고 알려져 있지만, 모든 양자 역학 이벤트가 튜링 계산 가능한지는 미해결 문제입니다. (그들은 반드시 효율적으로 동등하지는 않습니다. 위를 참조하십시오.) 존 루카스(John Lucas)와 로저 펜로즈(Roger Penrose)는 인간의 마음이 일종의 양자역학적으로 강화된 "비알고리즘" 계산의 결과일 수 있다고 제안했습니다.[65][66]

이 세 가지 범주의 외부 또는 중간에 속하는 다른 많은 기술적 가능성이 있지만 이러한 가능성은 개념의 범위를 설명하는 데 도움이 됩니다.

물리적 컴퓨터와 생물학적 컴퓨터 모두에 관한 논문의 철학적 측면은 Odifreddi의 1989년 반복 이론 교과서에서도 논의됩니다.[67]: 101–123

계산 불가능한 함수

계산할 수 없는 함수를 공식적으로 정의할 수 있습니다. 이러한 기능의 잘 알려진 예로는 바쁜 비버 기능이 있습니다. 함수는 입력 n을 사용하여 n개의 상태를 가진 튜링 기계가 입력 없이 실행될 때 정지하기 전에 인쇄할 수 있는 가장 많은 수의 기호를 반환합니다. 바쁜 비버 함수에서 상한을 찾는 것은 튜링 기계가 해결할 수 없다고 알려진 문제인 정지 문제를 푸는 것과 같습니다. 바쁜 비버 함수는 튜링 기계에 의해 계산될 수 없기 때문에, Church–Turing 논문은 이 함수가 어떤 방법으로도 효과적으로 계산될 수 없다고 말합니다.

여러 계산 모델을 통해 (교회-튜링) 계산 불가능 함수를 계산할 수 있습니다. 이것들은 하이퍼컴퓨터라고 알려져 있습니다. Mark Burgin은 귀납적 튜링 기계와 같은 초재귀적 알고리즘이 교회-튜링 논문을 반증한다고 주장합니다.[68][page needed] 그의 주장은 일반적인 것보다 더 넓은 알고리즘의 정의에 의존하므로 일부 귀납적 튜링 기계에서 얻은 계산 불가능 함수를 계산 가능이라고 합니다. 교회-튜링 논문의 이러한 해석은 위에서 논의된 계산가능성 이론에서 일반적으로 받아들여지는 해석과 다릅니다. 초재귀적 알고리즘이 실제로 교회-튜링 논문의 의미에서 알고리즘이라는 주장은 계산 가능성 연구계 내에서 광범위한 수용을 찾지 못했습니다.[citation needed]

참고 항목

각주

  1. ^ Robert Soare, "오라클 머신, 온라인 컴퓨팅 계산 가능성 이론의 세 가지 변위 교육"
  2. ^ Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. Event occurs at 9:36. Retrieved 2021-12-05.
  3. ^ 맥스 뉴먼과 알론조 교회 논문의 교신
  4. ^ Turing, Alan (2004). The essential Turing : seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life, plus the secrets of Enigma (PDF). Oxford: Clarendon Press. p. 44. ISBN 9780198250791. Retrieved 2021-12-06.
  5. ^ a b Soare, Robert I. (September 1996). "Computability and Recursion". Bulletin of Symbolic Logic. 2 (3): 284–321. CiteSeerX 10.1.1.35.5803. doi:10.2307/420992. JSTOR 420992. S2CID 5894394.
  6. ^ 처치의 논문은 1935년 4월 19일 미국 수학 학회에 발표되었고 1936년 4월 15일에 발표되었습니다. 자신의 결과물을 작성하는 데 상당한 진전을 이루었던 튜링은 출판과 동시에 교회의 증명을 알게 되어 실망했습니다.[3][4] 튜링은 빠르게 논문을 완성하여 출판을 시작했습니다. 1936년 5월 28일 런던 수학회 회보에 의해 접수되었고, 1936년 11월 12일에 읽혀졌고, 시리즈 2인 42권(1936-1937)으로 출판되었습니다. 1936년 11월 30일에 발행된 제3부(230-240쪽)와 제4부(241-265쪽)로 나뉘어 출판되었습니다. 1936년 12월 23일 발행된 튜링은 43권(1937년), 544-546쪽에서 수정 사항을 추가했습니다.[5]: 45
  7. ^ 1936년 교회
  8. ^ 크린 1936년
  9. ^ 튜링 1937a
  10. ^ 크린 1936년
  11. ^ 튜링 1937b. p에 증명 개요. 153: [10]
  12. ^ Roser 1939 in Davis 1965:225.
  13. ^ "effective". Merriam Webster's New Collegiate Dictionary (9th ed.).
  14. ^ "효과적"에 대한 이러한 정의도 참조하십시오. 첫 번째는 "효과적"이라는 단어의 의미 "1a"에 대한 정의이고, 두 번째는 "효과적"이라는 단어의 의미 "1a"에 대한 정의입니다. 그리고 두 번째는 "효과적"에 대한 동의어 논의의 일부입니다. (서론 부분에서, 여기서는 "효과적", "효과적", "효율적", "효과적" 단어의 의미 간 유사성을 요약합니다.
  15. ^ a b Turing, A. M. (1938). Systems of Logic Based on Ordinals (PDF) (PhD). Princeton University. p. 8. Archived from the original (PDF) on 2012-10-23. Retrieved 2012-06-23.
  16. ^ Gandy(1980:123)는 다음과 같이 말합니다. 효과적으로 계산 가능한 것은 계산 가능합니다. 그는 이것을 "교회의 논문"이라고 부릅니다.
  17. ^ 다비드 힐베르트와 빌헬름 아커만: 독일 베를린의 그룬쥐게데르 테레티스헨 로지크, 스프링어, 1928년 1일. (6판 1972, ISBN 3-540-05843-5) 영어 번역: 데이비드 힐버트와 빌헬름 아커만: 수학적 논리의 원리, AMS 첼시 출판, 프로비던스, 미국 로드 아일랜드, 1950.
  18. ^ 데이비스의 1936년 교회 이전 논평 데이비스의 초등수론의 해결할 수 없는 문제 1965:88 교회는 100ff 페이지에 "효과적인 계산 가능성"이라는 단어를 사용합니다.
  19. ^ Adam Olszewski et al. 2006에 의해 편집된 70년 후의 교회의 논문에 대한 그의 리뷰에서, Peter Smith의 무라스프스키와 Wolenski의 논문에 대한 비판은 교회-튜링 논문의 지위에 대해 (1) 경험적 가설 (2) 공리 또는 정리, (3) 정의, (4) 설명의 4가지 "선"을 제시합니다. 하지만 스미스는 (4)가 (3)과 구별할 수 없다고 생각합니다. 스미스 (2007-07-11) 70년 후 교회의 논문 http://www.logicmatters.net/resources/pdfs/CTT.pdf
  20. ^ cf. 1936a 교회에서 각주 3 데이비스초등수 이론의 해결할 수 없는 문제 1965:89.
  21. ^ 도슨 1997:99.
  22. ^ a b Sieg 1997:160.
  23. ^ Sieg 1997: Church가 Kleene에게 쓴 1935년 편지에서 인용, cf. 괴델 1934의 데이비스 1965:44 각주 3.
  24. ^ cf. 1936년 데이비스 교회 1965:105ff..
  25. ^ 1934년 괴델 이전 데이비스의 해설 1965:40.
  26. ^ 괴델이 튜링의 기계를 계산 모델로 채택한 것에 대한 자세한 논의는 다음을 참조하십시오.
  27. ^ a b 튜링 1937a.
  28. ^ cf. Post 1936 유한 조합 과정의 편집자각주. 데이비스에서 공식 I. 1965:289.
  29. ^ 1936년 데이비스 포스트 1965:291, 각주 8.
  30. ^ 1936년 데이비스 포스트 1952:291.
  31. ^ Sieg 1997:171와 176–177.
  32. ^ 튜링 1936-1937 데이비스 1965:263ff..
  33. ^ 1937년 교회.
  34. ^ 데이비스의 튜링 1939:160.
  35. ^ cf. 교회 1934 in Davis 1965:100, 또한 튜링 1939 in Davis 1965:160.
  36. ^ "로저 1939년 데이비스에서 1965:226"라는 이탤릭체가 덧붙여졌습니다.
  37. ^ 크린 1943, 데이비스의 60쪽 1965:274. 각주가 생략되었습니다.
  38. ^ Kleene 1952:300.
  39. ^ a b Kleene 1952:376.
  40. ^ 크리네 1952:382,536
  41. ^ Gandy 1980:123ff.
  42. ^ 간디 1980:135
  43. ^ 간디 1980:126
  44. ^ Sieg 1998-1999 in Sieg, Sommer & Talcott 2002:390ff.; 또한 Sieg 1997:154ff.
  45. ^ 각주에서 지그는 포스트의 1936년(B)을 (B.1)과 (B.2)로, (L)을 (L.1)과 (L.2)로 나누고 (D)를 다르게 설명합니다. 제안된 Gandy 기계와 관련하여 그는 나중에 LC.1, LC.2, GA.1 및 GA.2를 추가합니다. 이는 복잡합니다. Sieg 1998-1999의 Sieg, Sommer & Talcott 2002:390ff를 참조하십시오.
  46. ^ 논문집은 Olszewski, Wole ński & Janusz(2006)에서 찾을 수 있습니다. 또한 이 컬렉션에 대한 리뷰:
  47. ^ 참고 항목
  48. ^ Gödel, Kurt (1995) [193?]. "Undecidable Diophantine Propositions". In Feferman, Solomon (ed.). Collected Works. Vol. 3. New York: Oxford University Press. p. 168. ISBN 978-0-19-507255-6. OCLC 928791907.
  49. ^ 크리네 1952:320
  50. ^ 구레비치 1988:2
  51. ^ Davis의 『언데커블』(1936) 번역 83쪽, Kleene(1952) 321쪽.
  52. ^ 올슈프스키의 호르스텐,ń스키 & 야누스 2006:256
  53. ^ Gabbay 2001:284
  54. ^ Piccinini, Gualtiero (January 2007). "Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy" (PDF). Synthese. 154 (1): 97–120. CiteSeerX 10.1.1.360.9796. doi:10.1007/s11229-005-0194-z. S2CID 494161. Archived (PDF) from the original on 2008-04-24.
  55. ^ Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. 섹션 1.4, "현으로서의 기계와 보편적 튜링 기계" 및 1.7, "정리의 증명 1.9".
  56. ^ "Official Problem Description" (PDF). Archived from the original (PDF) on 2005-11-24.
  57. ^ a b Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2007). An introduction to quantum computing. Oxford University Press. pp. 5–6. ISBN 978-0-19-857049-3.
  58. ^ van Emde Boas, Peter (1990). "Machine Models and Simulations". Handbook of Theoretical Computer Science A. Elsevier. p. 5.
  59. ^ Slot, C.; van Emde Boas, P. (December 1984). On tape versus core: an application of space efficient perfect hash functions to the invariance of space. STOC.
  60. ^ Eberbach & Wegner 2003, 페이지 287.
  61. ^ Abramson, Darren (2011). "Philosophy of mind is (in part) philosophy of computer science". Minds and Machines. 21 (2): 203–219. doi:10.1007/s11023-011-9236-0. S2CID 32116031.
  62. ^ Copeland, B. Jack (2017-11-10). "The Church-Turing Thesis". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
  63. ^ 원본 논문을 접할 수 있는 좋은 장소는 다음을 참조하십시오.
  64. ^ Copeland, B. Jack (2004). "Computation". In Floridi, Luciano (ed.). The Blackwell guide to the philosophy of computing and information. Wiley-Blackwell. p. 15. ISBN 978-0-631-22919-3.
  65. ^ cf. Penrose, Roger (1990). "Algorithms and Turing machines". The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford: Oxford University Press. pp. 47–49. ISBN 978-0-19-851973-7. OCLC 456785846.
  66. ^ 또한 "수학적 통찰력의 비알고리즘적 성격"에 대한 설명,
  67. ^ Piergiorgio Odifreddi (1989). Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics. Vol. 125. Amsterdam, Netherlands: North Holland.
  68. ^ Burgin, Mark (2005). Super-Recursive Algorithms. Monographs in Computer Science. New York: Springer. ISBN 978-0-387-95569-8. OCLC 990755791.

참고문헌

외부 링크