Church-Turing Thesis

 

.......... Church-Turing thesis, Church's thesis, Church's conjecture, Turing's thesis 는 모두 같은 것이다 .........

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

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

컴퓨터과학에서 Church-Turing thesis 는 모든 효율적인 (effective) 계산이나 알고리즘은 Turing machine 에서 수행될수 있다 고 간단히 정의된다. 그것은 일반적으로 true 인 것으로 가정되며 Church-Turing thesis, Church's thesis, Church's conjecture, Turing's thesis 라고도 알려져 있다 (★★★). (Alan Turing 과 Alonzo Church 의 이름에서 붙인 명칭이다)

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

  1. 그 방법은 유한 갯수의 기호로서 묘사할 수 있는 간단하고 정밀한 명령어들의 유한 집합으로 구성된다.
  2. 그 방법은 항상 유한 갯수의 step 내에 결과를 만들어낸다.
  3. 그 방법은 주로 종이와 연필만으로도 인간에 의해 수행될 수 있다.
  4. 그 방법의 수행시 명령어를 이해하고 실행하기 위해 필요한 것을 제외하고는 인간의 지능을 전혀 요구하지 않는다.

그러한 방법의 한 예가 두 자연수의 최대공약수 (greatest common divisor) 를 결정하기 위한 Euclidean algorithm 이다.

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

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

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

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

Church-Turing thesis 는 심리철학에 심오한 함축을 보여준다. 또한 Church-Turing thesis 와 물리학의 관계, 그리고 hypercomputation 의 가능성에 대한 몇가지 중요하면서 잘 알려진 의문점들이 있다. 물리학에 적용시켜보면 Church-Turing thesis 는 몇가지 중요한 의미를 포함한다.  

  1. 우주는 튜링머신이다 (그래서 non-recursive functions를 계산하는 것은 물리적으로 불가능하다). 이것은  strong Church-Turing thesis 라고 불리운다.
  2. 우주는 튜링머신이 아니다 (즉 물리법칙은 Turing-computable 하지 않다). 그러나 계산불가능한 물리적 사건들을 hypercomputer 의 구축을 위해 이용할 수는 ("harnessable") 없다. 예를들면 물리학이 계산가능한 실수 (computable reals) 와 반대되는 실수 (real numbers)를 포함하는 하나의 우주는 이 영역으로 빠질 것이다.
  3. 우주는 hypercomputer 이며 이러한 성질을 이용하여 non-recursive functions를 계산하는 물리적 장치를 구축하는 것이 가능하다. 예를들면, 비록 qubits 밖에서 구축된 어떤 시스템도 기껏해야 Turing-complete 이라는 것이 증명되어 왔지만, 모든 quantum mechanical events 가 Turing-computable 인지에 대한 잘 알려진 의문이 있다. John Lucas (그리고 유명한 Roger Penrose) 는 비록 인식론적으로 모호하기는 하지만, 인간의 마음이 quantum hypercomputation 의 결과일 것이라고 제안했다. 이러한 단계에서는 물리학이 활용가능한 hypercomutation을 받아들일 것 같지는 않다.

(이러한 3 영역 사이에 또는 그 이상에 존재하는 많은 기술적 가능성들이 실제로 존재하지만, 이러한 것들은 그 개념을 실증하는데 도움을 줄 것이다) .............. (Wikipedia : Church-Turing Thesis)

term :

처치-튜링 명제 (Church-Turing Thesis)    Alan Turing    Alonzo Church    튜링기계 (Turing Machine)   튜링 명제 (Turing Thesis)   계산가능성 이론 (Computability Theory)   계산 (Computation)   마르코프 알고리즘 (Markov Algorithm)    재귀함수 (Recursive Function)   람다 계산법 (Lambda Calculus)   포스트 시스템 (Post Systems)   결정문제 (Entscheidungsproblem)

site :

Wikipedia : Church-Turing Thesis

Church-Turing Thesis : Stanford encyclopedia of philosophy

paper :

튜링 명제 : Peter Linz

계산가능성 이론 형성에서의 Church's Thesis 와 Turing's Thesis : 현우식, 한국수학사학회, 1998

타르스키 정리, 처치 정리, 그리고 괴델 정리 : 김영정, 한국철학회 , 1987

video :

The Church-Turing Thesis : Story and Recent Progress : GoogleTech Talks : 2009/06/12