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

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

계산 이론

Church-Turing-These | Church–Turing thesis | Tesis de Church-Turing | Thèse de Church-Turing | Tesi di Church-Turing | Tiuringo tezė | Tese de Church-Turing | Тезис Чёрча — Тьюринга | 邱奇-图灵论题