처치-튜링 명제

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

처음 이 명제가 나왔을 때에는 "효율적으로 계산할 수 있는 함수"와 같이 비형식적인 표현을 사용했고, 따라서 명제를 논리적으로 증명하는 것은 불가능했다. 따라서 수학자들은 이와 같은 모호한 단어 대신 계산가능한 함수를 사용한다.

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

바깥 고리[편집]