처치-튜링 논제

2. 역사

1930년대 논리학자들에게 중요한 문제는 다비트 힐베르트와 빌헬름 아커만이 제기한 결정 문제였다.^[12] 이 문제는 수학적 진실과 거짓을 구별하는 기계적인 절차가 있는지 묻는 것이었다. 이를 위해 "알고리즘" 또는 "유효 계산 가능성"의 개념을 명확히 할 필요가 있었다.^[13]

이 문제를 연구하면서, 알론조 처치와 그의 제자 스티븐 콜 클리니는 λ-정의 가능 함수 개념을 도입했고, 수론에서 자주 접하는 여러 함수들이 λ-정의 가능하다는 것을 증명했다.^[15] 처치는 "효율적으로 계산 가능한" 함수를 λ-정의 가능 함수로 정의해야 한다고 쿠르트 괴델에게 제안했지만, 괴델은 이를 "전적으로 만족스럽지 않다"고 말했다.^[16] 괴델은 "효율적 계산 가능성" 개념을 공리화할 것을 제안했지만, 더 구체적인 지침은 제시하지 않았다.^[26]

이후 클리니는 처치와 J. 버클리 로서의 도움을 받아 λ-계산법과 "일반" 재귀, 두 계산법이 동등하다는 증거를 제시했다(1933, 1935).^[18] 처치는 자신의 방법을 수정하여 Herbrand-Gödel 재귀를 포함시켰고, 결정 문제가 풀 수 없다는 것을 증명했다.^[18] 1965년경 괴델은 1934년 당시 자신의 재귀 개념이 모든 재귀를 포함한다고 확신하지 않았다고 회고했다.^[19] 1963~1964년경 괴델은 튜링 기계를 선호하게 되었다.^[20]

1936년 말 앨런 튜링의 논문이 발표되었고, 에밀 포스트의 논문은 튜링의 연구와 독립적인 것으로 확인되었다.^[21][22] 포스트는 처치의 효율적 계산 가능성을 λ-계산법 및 재귀와 "동일시"하는 것에 반대하며, 이를 "작업 가설"로 간주했다.^[23][24] 그는 "효율적 계산 가능성"이라는 개념이 "정의 또는 공리"가 아니라 "귀납적 추론"에 의해 "자연 법칙"으로 이어질 수 있다고 보았다.^[24]

얼마 지나지 않아 튜링의 1936-1937년 논문이 발표되었고, 그는 튜링 기계 추상 계산 모델을 도입하여 "효율적 계산 가능성"에 대한 또 다른 개념을 제시했다.^[21] 튜링은 λ-계산법과 튜링 기계로 정의된 함수 클래스가 일치한다는 것을 보여주었다.^[27] 처치는 튜링의 분석이 설득력이 있다고 빠르게 인정했다.^[28]

1939년까지 처치(1934)와 튜링(1939)은 개별적으로 자신의 "형식적 시스템"이 "효율적 계산 가능성"의 ''정의''가 되어야 한다고 제안했다.^[30] J. 버클리 로서(1939)는 세 가지 개념을 정의로 공식적으로 동일시했다.^[31]

1943년 스티븐 콜 클리니는 "테제 I"을 제안했다.^[32] 클리니는 자신의 저서 "메타수학 입문"에서 "처치의 테제"와 "튜링의 테제"라는 용어를 공식적으로 명명했다. 그는 앨런 튜링의 논문 개념을 명확히 하는 데 도움을 주는 섹션에서 처음으로 "처치-튜링 테제"라는 용어를 사용한다.^[35]

2. 1. 1930년대 초: 계산 가능성 개념의 등장

2. 2. 1930년대 중반 ~ 1950년대 초: 처치-튜링 명제의 정립

2. 3. 1950년대 이후 ~ 현재: 처치-튜링 명제의 발전과 확장

• (B.1) (경계): 즉시 인식 가능한 기호 구성의 수에 고정된 경계가 있다.
• (B.2) (경계): 가질 수 있는 내부 상태의 수에 고정된 경계가 있다.
• (L.1) (지역성): 관찰된 기호 구성 요소만 변경할 수 있다.
• (L.2) (지역성): 주의를 다른 구성으로 옮길 수 있지만, 새롭게 관찰된 구성은 바로 이전에 관찰된 구성에서 경계 내 거리에 있어야 한다.
• (D) (결정론): 즉시 인식 가능한 (부분) 구성은 다음 계산 단계를 고유하게 결정한다.^[40]