[알고리즘] 처치-튜링 명제(Church-Turing Thesis)

1930년대 중반의 Alan Turing과 다른 사람들로 하여금 튜링 명제(Turing thesis)라 불리는 유명한 추측(conjecture)를 만들어 내게 하였습니다. 이 가설은 기계적인 방법으로 수행될 수 있는 모든 계산은 어떤 튜링 기계에 의하여 실행될 수 있다는 것을 말합니다. 튜링 기계를 기계적인 계산에 대한 정의로 받아들이는 몇몇 논거는 다음과 같습니다.

 - 모든 존재하는 컴퓨터에서 수행될 수 있는 모든 일은 또한 튜링 기계에 의하여 수행될 수 있다.

 - 어느 누구도 아직 우리가 직관적 알고리즘이라 생각하는 것에 의하여 해결되지만, 튜링 기계 프로그램으로 해결될 수 없는 문제를 제시할 수 없었다.

 - 기계적인 계산에 대해 여러 다른 모델들이 제안되었지만, 그들 중 어느 것도 튜링 기계보다 더 강력하지 않다.

어떤 의미에서, 튜링 명제는 물리하고가 화학의 기본 원칙들이 하는 것처럼 컴퓨터 과학에서 같은 역할을 합니다. 예를 들어, 고전저긴 물리학은 주로 Newton의 운동법칙들에 근거를 두고 있습니다. 그러한 법칙들을, 비록 무용지물이 될 수는 있지만, 참이라고 증명될 수 없습니다. 어떤 법칙을 무력화하는 것에 대한 반복된 실패는 그 법칙에 대한 우리의 확신을 강하게 합니다. 이것이 튜링 명제에 대한 입장입니다. 따라서 우리가 이 명제를 컴퓨터 과학의 기본 법칙으로 생각하는 이유가 됩니다.

컴퓨터과학에서 Church-Truing thesis는 모든 효율적인 계산이나 알고리즘은 Turing machine에서 수행될 수 있다고 간단히 정의됩니다. 그것은 일반적으로 true인 것으로 가정되며 Church-Truing thesis, Church's thesis, Church's conjecture, Turing's thesis라고도 알여져 있습니다.

그 명제는 다시 말하면 논리와 수학에서 effective or mechanical method의 표기가 튜링기계(Turing Machine)로써 이루어질 수 있다는 것입니다. 그것은 대개 다음과 같은 요건을 만족해야 하는 것으로 가정됩니다.

1. 그 방법은 유한 갯수의 기호로서 묘사할 수 있는 간단하고 정밀한 명령어들의 유한 집합으로 구성된다.

2. 그 방법은 항상 유한 갯수의 step 내에 결과를 만들어낸다.

3. 그 방법은 주로 종이와 연필만으로도 인간에 의해 수행될 수 있다.

4. 그 방법의 수행시 명령어를 이해하고 실행하기 위해 필요한 것을 제외하고는 인간의 지능을 전혀 요구하지 않는다.

효율적인 방법이라는 표현은 직관적으로는 명확하지만 형식적으로는 정의되지는 않습니다. 왜냐하면 간단하고 정밀한 명령어란 무엇인가, 명령어를 수행하기 위해 요구되는 지능이란 것이 정확히 무엇인지가 명확하지가 않기 때문입니다.

튜링은 1936년 On Computable Numbers, with an Application to the Entscheidungsproblem 라는 논문에서 튜링기계를 소개하면서 이 표현을 공식적으로 사용했습니다. 그 논문에서 결정문제는 풀 수 없다는 것을 보여줍니다. 이보다 몇달 앞서서 Church는 그의 논문을 통해서 유사한 결과를 증명는데, 그는 효율적인 계산가능성을 표현하기 위해 재귀함수(Recursive Function)와 람다 계산법(Lambda Calculus)이라는 표현을 사용했습니다. 람다 계산법은 Church와 Stephen Kleene가 처음 사용했고, recursive fucntions는 괴델과 Jacques Herbarnd가 처음 사용했습니다. 이 두가지 표현은 Church와 Kleene이 이용한 functions of positive integers의 경우에서 알 수 있듯이 같은 종류의 함수를 표현하는 것입니다. Church의 제안을 들었을때 튜링은 실제로 그의 튜링기계와 같은 종류의 함수들로 표현된다는 것을 즉시 알 수 있었습니다.

그때부터 효율적인 계산가능성(effective computability)을 표현하는 많은 다른 방법들이 register machines, post systems, combinatoric logic, markov algorithm 과 같은 이름으로 발표되었습니다. 이러한 시스템들은 모두 튜링머신 같은 함수들을 잘 계산한다는 것을 보여주었고 이와 같은 시스템들은 Turing-complete라고 불리웁니다. 알고리즘의 개념을 표현하려는 이러한 여러가지 시도들이 동등한 결과를 보였기 때문에, 지금은 Church-Turing thesis는 옳다는 것이 일반적으로 받아들여집니다. 하지만 이 이론은 하나의 정리의 형태를 가지고 있지 않으며 증명될 수 없습니다. 하지만 그것은 상상가능한 것이며 효율적이지만 튜링머신 상에서 수행될수 없는 알고리즘이 존재한다고 하는 것과 같은 일반적으로 받아들여지는 방법을 보여줌으로써 반증될 수 있는 것 같지는 않습니다.

실제로 Church-Turing thesis는 성공적이며 지금은 거의 미제로 남아있습니다. 20세기 초반에 수학자들은 effectively computable이라는 비형식적인 표현을 사용했으며 따라서 그 개념의 정확한 표현(formalization)을 찾아내는 것이 중요합니다. 대신에 현대의 수학자들은 잘 정의된 용어인 Turing computable (or computable for short)을 사용합니다. 불명확한 용어가 사라지면서 그것을 어떻게 정의하느냐 하는 문제는 지금은 덜 중요하게 되었습니다.

hypercomputation, qubits, quantum hypercomputation...

http://www.aistudy.com/computer/church_turing_thesis.htm