처치-튜링 명제

처치-튜링 명제는 모든 유효한 절차(effective procedure)로 계산 가능한 함수는 튜링 기계로 계산 가능하다고 주장하며, 알고리즘에 대한 비형식적인 아이디어를 정밀한 수학적 모델과 동일시합니다.

Definition

처치-튜링 명제는 직관적으로 계산 가능한 함수가 튜링 기계, 람다 계산법 또는 일반 재귀 함수에 의해 계산 가능한 함수와 정확히 일치한다는 주장입니다. 직관적인 개념이 형식적으로 정의되지 않았기 때문에 정리(theorem)라기보다는 명제(thesis)입니다.

Scope

이 주제는 명제의 진술, 독립적으로 제안된 모델들로부터의 수렴적 증거, 유효 계산 가능성에 대한 원래 명제와 더 강력한 물리적 또는 복잡성 이론적 변형 간의 구별, 그리고 계산 가능성 이론에서 직관과 형식적 증명 사이의 다리로서 명제의 역할을 다룹니다.

Core questions

• 알고리즘의 비형식적 개념을 형식적 모델과 동일시한다는 것은 무엇을 의미하는가?
• 독립적인 모델들의 수렴이 왜 이 명제에 대한 강력한 증거로 받아들여지는가?
• 이 명제는 수학적 정리인가, 정의인가, 아니면 경험적 주장인가?
• 물리적 및 복잡성 이론적 버전은 원래의 진술을 어떻게 넘어서는가?

Key theories

계산 모델의 수렴

튜링 기계, 처치의 람다 계산법, 괴델과 허브란트(Herbrand)의 재귀 함수는 정확히 동일한 종류의 함수를 정의하는 것으로 나타났으며, 이러한 독립적인 일치는 이 명제에 대한 주요 증거로 제시됩니다.

정리가 아닌 명제로서의 지위

유효한 절차에 대한 직관적인 개념이 형식화되지 않았기 때문에, 이 주장은 증명될 수 없습니다. 이는 비형식적인 알고리즘적 주장이 형식적인 튜링 기계 구성물을 대신할 수 있도록 하는 근본적인 동일시로 받아들여집니다.

Clinical relevance

이 명제는 유효한 절차에 대한 합리적인 개념이 튜링 등가라고 가정되므로, 알고리즘을 튜링 기계로 표현하기보다는 고급 의사 코드(pseudocode)로 설명하는 일상적인 관행을 정당화합니다. 또한 물리적 또는 양자 장치가 튜링 계산 가능성을 넘어설 수 있는지에 대한 논쟁의 틀을 제공합니다.

History

1936년 처치는 유효 계산 가능성을 람다 정의 가능성과 동일시할 것을 제안했고, 튜링은 독립적으로 자신의 기계 모델을 주장했습니다. 그 후 튜링, 클레이니(Kleene) 등은 이들 모델과 재귀 함수가 동등함을 증명했습니다. 처음에는 회의적이었던 괴델(Gödel)은 튜링의 분석을 결정적인 것으로 받아들였고, 이 통합된 주장은 처치-튜링 명제로 알려지게 되었습니다.

Debates

물리적 계산이 튜링 한계를 넘어설 수 있는가?

원래의 명제는 유효한 절차에 관한 것이지만, 더 강력한 물리적 버전은 물리적으로 실현 가능한 어떤 장치도 튜링 계산 불가능한 함수를 계산할 수 없다고 주장합니다. 초계산(hypercomputation)에 대한 제안과 양자 역학의 함의는 이 확장된 주장을 논쟁의 여지가 있는 상태로 유지하며, 고전적인 명제는 본질적으로 이의가 제기되지 않고 있습니다.

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

왜 정리(theorem)가 아니라 명제(thesis)라고 불리는가?

이것은 형식적 모델을 유효한 절차라는 비형식적 아이디어와 연결하며, 그 비형식적 아이디어는 증명할 수 있는 수학적 정의가 없습니다. 강력한 증거는 계산을 형식화하려는 모든 독립적인 시도가 동일한 종류의 함수를 산출했다는 것이지만, 이러한 지지는 증명이라기보다는 개념적인 것입니다.

양자 컴퓨터가 처치-튜링 명제를 반박하는가?

아닙니다. 양자 컴퓨터는 일부 문제를 더 빠르게 해결할 수 있지만, 튜링 기계와 정확히 동일한 종류의 함수를 계산하므로, 계산 가능한 것에 대한 원래 명제는 유효합니다. 양자 컴퓨터는 계산 가능성보다는 효율성에 관련된 더 강력한 복잡성 이론적 버전에 영향을 미칩니다.