처치-튜링 논제

처치-튜링 논제(Church-Turing thesis)는 계산 가능한 함수에 대한 논제(thesis)이다. 간단히 요약하면, 어떤 함수는 튜링 기계가 계산할 수 있으면, 그리고 그 때만 알고리즘으로 계산 가능하다는 명제이다. 알론조 처치와 앨런 튜링의 이름을 따 지어졌다. 튜링 기계는 모든 범용 프로그래밍 언어로 번역될 수 있으므로, 이것은 어떤 컴퓨터에게든 충분한 시간과 메모리가 주어진다면 존재하는 모든 알고리즘의 결과를 출력할 수 있다는 명제와 동치이다.

처음 이 명제가 나왔을 때에는 "효과적으로 계산할 수 있는 (effectively computable) 함수"와 같이 비형식적인 표현을 사용했기 때문에 이 명제를 논리적으로 증명하는 것은 불가능했다. 이후 수학자들은 모호한 말 대신 계산 가능한 함수를 사용한다.

실제로 증명되거나 반증된 적은 없으며, 영원히 증명할 수 없을 것이라고 주장하는 학자도 있다. 다만 현재까지 인간이 발명한 모든 종류의 계산법(양자 컴퓨터를 포함하여)이 적절한 형태의 튜링 기계로 표현될 수 있음이 알려져 있다.

같이 보기

• 추상 기계
• 결정가능성
• 하이퍼 계산
• 튜링 완전

외부 링크

• 처치-튜링 명제