AI Study
뉴턴의 운동 법칙에 비견되는 컴퓨터 과학의 제1원리 — 튜링 기계 · 람다 대수 · 재귀함수의 대통합과 AI 지능의 보편 경계

처치-튜링 명제 (Church-Turing Thesis)

AI(인공지능) 분야에서 처치-튜링 논제(Church-Turing Thesis) 는 "인간의 지능적 사고나 알고리즘으로 풀 수 있는 모든 문제는 튜링 기계(즉, 현대의 디지털 컴퓨터) 로도 계산하고 구현할 수 있다"는 이론적 토대이자 철학적 전제를 의미합니다.
알론조 처치(Alonzo Church) 와 앨런 튜링(Alan Turing) 이 1930년대에 정립한 이 개념은 원래 컴퓨터 과학의 '계산 가능성'에 관한 명제이지만, AI 의 탄생과 발전에 결정적인 역할을 했습니다 ... 즉 "알고리즘(기계적인 절차) 으로 계산할 수 있는 모든 문제는 튜링 기계(Turing Machine) 로도 계산할 수 있다"는 내용을 담고 있습니다. 현대의 모든 컴퓨터와 AI 모델 역시 수학적으로는 튜링 기계의 범주 안에 속합니다.
AI의 관점에서 이 명제가 가지는 핵심 의미는 크게 네 가지로 정리할 수 있습니다.

1. AI 구현의 이론적 토대 (계산주의)
  • 지능의 알고리즘화. 인간의 사고나 지능적 행동이 일정한 규칙과 계산 과정의 결과물이라면, 이를 프로그램으로 구현할 수 있다는 믿음의 근거가 됩니다.
  • 범용성의 보장. 딥러닝, 트랜스포머 등 아무리 복잡한 최신 AI 아키텍처라도 결국 기본적인 연산을 수행하는 튜링 기계 위에서 완벽하게 시뮬레이션할 수 있음을 뜻합니다.
2. AI 능력의 절대적 한계 (계산 불가능성)
  • 해결 불가능한 문제 존재. 처치-튜링 명제에 따르면 튜링 기계가 풀지 못하는 문제는 어떤 슈퍼컴퓨터나 미래의 AI가 등장하더라도 절대 풀 수 없습니다.
  • 대표적인 한계 사례. 프로그램이 스스로 무한 루프에 빠질지 멈출지를 사전에 완벽히 판별하는 정지 문제(Halting Problem) 는 계산 불가능한 영역입니다. 따라서 AI가 다른 AI의 모든 오류나 환각(Hallucination) 을 100% 완벽하게 검증하는 것은 이론적으로 불가능에 가깝습니다.
3. 물리적 처치-튜링 명제와 뇌의 모방
  • 인간 뇌의 계산 가능성. 이 명제를 물리학적으로 확장하면 "우주에서 물리적으로 일어나는 모든 과정(인간의 뇌 활동 포함)은 튜링 기계로 계산할 수 있다"는 해석으로 이어집니다.
  • 강인공지능(AGI)의 가능성. 만약 인간의 뇌가 물리 법칙을 따르는 생물학적 컴퓨터에 불과하다면, 충분한 연산 자원을 가진 AI가 인간의 모든 인지 능력을 복제할 수 있다는 논리의 핵심 전제가 됩니다.
4. 비계산적 지능에 대한 논쟁
  • AI 의 본질적 한계론. 물리학자 로저 펜로즈(Roger Penrose) 같은 학자들은 인간의 의식이나 직관이 단순한 알고리즘(튜링 기계)을 넘어서는 양자역학적 현상일 수 있다고 주장합니다.
  • AI 철학의 분기점. 이 주장이 맞다면 현재의 계산 기반 AI 는 인간과 같은 진정한 의식을 가질 수 없게 되며, 틀렸다면 AI는 이론상 인간과 완전히 동등하거나 그 이상의 지능에 도달할 수 있습니다.

처치-튜링 명제(Church-Turing Thesis)는 "인간이 종이와 연필로 수행할 수 있는 모든 직관적·기계적 알고리즘(Effective Method)은 튜링 기계(람다 계산법, 재귀함수와 동치)로 완전히 표현 및 실행할 수 있다"는 컴퓨터 과학의 근본 가설입니다. 이 명제는 현대 AI와 LLM이 인간의 지능적 추론을 디지털 실리콘 위에서 구현할 수 있는 이론적 근거(AGI 가능성)를 제공하는 동시에, 아무리 거대한 AI나 양자컴퓨터도 튜링 계산 가능성의 절대 경계를 넘지 못한다는 냉철한 한계선을 함께 그어줍니다.

SECTION 01

Church-Turing Thesis의 개념과 3대 핵심 의미

1930년대, 알론조 처치(Alonzo Church)는 함수 치환 기반의 람다 계산법을, 괴델·클리니는 수론 기반의 재귀함수를, 앨런 튜링(Alan Turing)은 테이프 기계인 튜링 기계를 각기 다른 곳에서 고안했습니다. 놀랍게도 이 완전히 다른 모델들이 계산할 수 있는 함수의 집합이 수학적으로 100% 일치함이 증명되었고, 이를 토대로 "직관적인 모든 알고리즘 계산은 튜링 기계로 수행 가능하다"는 처치-튜링 명제가 탄생했습니다.

의미 ① · 왜 '명제(Thesis)'인가?

수학적 증명이 아닌 컴퓨터과학의 제1원리

'인간의 직관적 알고리즘(Effective Method)' 자체가 비형식 개념이기 때문에, 이 명제는 수학 정리(Theorem)처럼 연역 증명할 수 없습니다. 하지만 Peter Linz의 비유처럼 뉴턴 역학의 법칙과 같아서, 90년간 제안된 어떤 계산 모델(프로그래밍 언어·세포자동자·포스트 시스템)도 이를 반증하지 못했습니다.

의미 ② · 확장 처치-튜링 명제 (속도)

고전 계산 vs 양자 컴퓨팅(BQP)의 도전

확장 처치-튜링 명제(Extended CT Thesis)는 "모든 물리적 컴퓨터는 확률적 튜링 기계로 다항 시간 내 시뮬레이션 가능하다"고 주장합니다. 양자 컴퓨터는 계산 가능성(원래 CT 명제)은 깨지 못하지만, 소인수분해(쇼어 알고리즘) 등에서 다항 시간 가속을 달성해 이 확장 명제(속도 경계)에는 강력한 도전을 제기합니다.

의미 ③ · 물리적 명제와 초월 계산

우주·인간의 뇌 ⇄ Hypercomputation 논쟁

강한/물리적 처치-튜링 명제는 "물리 우주와 인간 뇌의 작용마저 튜링 계산 가능하다"고 봅니다. 반면 로저 펜로즈 등은 인간의 의식이 양자 초월 계산(Hypercomputation)에 의존할 수 있다고 반론을 펴며, 현대 심리철학·AGI 논쟁의 핵심 쟁점이 되고 있습니다.

INFOGRAPHIC 01 · 처치-튜링 명제의 대통합과 3가지 변형(고전 · 확장 · 물리) 다양한 형식 모델이 하나의 보편 계산으로 합류하는 구조와 양자/초월 계산 경계
Church-Turing Thesis : 보편 계산의 대통합과 물리 · 양자 경계 "접근법은 전혀 달랐지만, 도달한 계산 능력의 끝은 모두 똑같았다 (Turing-Complete)" 고전 처치-튜링 명제 : 6대 형식 모델의 완전 동치 앨런 튜링 (1936) 튜링 기계 (테이프 · 상태 기반) 처치 · 클리니 (1936) 람다 계산법 (함수 치환 · 추상화) 괴델 · 에르브랑 (1934) 일반 재귀함수 (μ-연산자 수론) 포스트 · 마르코프 · 현대 언어 문자열 재작성 · Python · 레지스터 모두 정확히 동일한 집합 = Turing-Computable (Effective Method ≡ Turing Machine ≡ λ-Calculus ≡ μ-Recursive) 처치-튜링 명제의 3단계 스펙트럼 (유효성 ➔ 속도 ➔ 물리) 1. 고전 명제 (계산 가능성) : 여전히 견고함 (반증 사례 0건) "어떤 알고리즘·슈퍼컴·양자컴퓨터도 튜링 이상의 계산 가능성(정지문제 등) 돌파 불가" 2. 확장 명제 (다항 시간 효율) : 양자 BQP에 의해 도전받음 "시간·속도 면에서는 양자컴퓨터(쇼어 알고리즘)가 고전 튜링보다 지수적 가속 가능" 3. 물리적 명제 : "우주와 뇌는 튜링 머신인가?" (AGI · 펜로즈 논쟁) "인간 뇌가 물리적 계산체라면 AGI 가능 / 반면 Hypercomputation은 미검증 가설" 처치-튜링 명제가 보증하는 '컴퓨팅의 보편성(Universality)' ① 어떤 하드웨어(x86 · GPU · 광학칩 · 양자칩)와 어떤 언어(Python · LISP · SQL)를 쓰더라도 계산 '범위'는 동일 ② 그러므로 AI 모델이 '무엇을 계산할 수 있는가'의 한계는 하드웨어가 아닌 처치-튜링 경계가 결정 ③ 단, '얼마나 빠르게 계산하는가(효율성)'는 GPU 병렬·광학·양자 아키텍처 혁신에 따라 극적으로 달라짐!
SECTION 02 · DEEP RESEARCH

AI와 LLM에서 Church-Turing Thesis가 가지는 5대 심층 의미

최신 대규모 언어 모델(LLM)과 에이전트 AI가 코딩을 하고 수학 정리를 증명하는 오늘날, 처치-튜링 명제는 "LLM의 아키텍처별 계산 능력의 등가성", "AGI 가능성의 철학적 근거", "양자 AI 및 신형 반도체의 한계", 그리고 "LLM의 다중 언어·도구 번역 능력"을 관통하는 핵심 원리입니다.

심층 분석 01 · LLM의 튜링 합류

신경망(연속 행렬 연산)도 결국 처치-튜링 명제 안의 '튜링 계산 체계'로 수렴한다

전통적인 기호주의 AI(Symbol Manipulation)와 현대의 딥러닝(Continuous Matrix Multiplication)은 겉보기에 정반대처럼 보입니다. 하지만 처치-튜링 명제 관점에서 볼 때 유한 정밀도(BF16/FP8) 트랜스포머의 단일 순전파는 TC0라는 하위 부류에 머물 뿐, Chain-of-Thought(자기 기록 루프)와 코드 인터프리터(외부 메모리)를 결합하는 순간 람다 대수·파이썬·튜링 기계와 완벽히 동등한 보편 계산 부류(Turing-complete)로 합류합니다. 즉 "연속 벡터 연산 + 자기회귀 루프" 역시 처치-튜링 명제가 가리키는 동일한 계산 능력의 또 다른 구현체입니다.

심층 분석 02 · 기술 과대광고 판독기

"차세대 GPU·광컴퓨터·양자 AI도 '계산 불가능' 문제는 풀 수 없다"

고전 처치-튜링 명제는 계산 속도가 아니라 계산 가능성의 우주적 상한선을 정합니다. 따라서 엔비디아 B200 GPU 클러스터든 광학 AI 가속기든, 심지어 큐비트 기반의 양자 머신러닝이든 간에 튜링 기계가 원리적으로 풀 수 없는 비계산 문제(정지 문제, 라이스 정리, 100% 무환각 보편 검증기)를 풀 수 있게 되지는 않습니다. 하드웨어 혁신이 돌파하는 영역은 '확장 처치-튜링 명제' 즉 시간·전력 복잡도의 장벽이지, 계산 가능성의 절대 벽이 아닙니다.

심층 분석 03 · AGI의 철학적 토대

물리적 처치-튜링 명제: 인간 뇌가 물리적 계산체라면 AGI는 이론적으로 가능하다

아래 원전 목록에 소개된 것처럼 처치-튜링 명제는 물리학과 심리철학에 깊은 함축을 던집니다. 만약 강한/물리적 처치-튜링 명제가 참이어서 생물학적 뇌의 뉴런·시냅스 정보 처리 또한 물리 법칙 하에서 튜링 계산 가능하다면, 인간과 동등하거나 이를 능가하는 범용 인공지능(AGI)을 디지털 컴퓨터 위에 구현하는 일은 원리적으로 100% 가능합니다. 반대로 펜로즈·루카스가 주장하듯 뇌가 비계산적 양자 현상(Hypercomputation)을 사용한다면 디지털 AI에는 근본 한계가 존재하게 됩니다.

심층 분석 04 · LLM 코드·도구 번역의 근거

왜 LLM은 Python ↔ Haskell(람다) ↔ SQL ↔ Bash를 자유롭게 상호 변환하는가?

최신 코딩 LLM(Claude, GPT, Gemini 등)이 한 언어의 알고리즘을 다른 언어(예: 명령형 Python ⇄ 함수형 람다 계산 기반 Haskell/Lisp)로 정확히 번역하고 실행할 수 있는 근본 이유는, 처치-튜링 명제가 보증하는 표현 동치성(Expressive Equivalence) 덕분입니다. 모든 튜링 완전한 언어는 본질적으로 동일한 계산 구조를 공유하므로, LLM은 특정 문법의 표면 차이를 넘어 알고리즘의 불변하는 계산 구조를 학습·변환할 수 있습니다.

심층 분석 05 · Hypercomputation vs 실세계 오라클

폐쇄된 튜링 계산을 여는 열쇠: 실시간 웹·센서·인간 피드백(Oracle Interface)

고전 처치-튜링 명제는 고정된 입력에서 시작해 고립되어 동작하는 폐쇄 알고리즘(Closed Algorithm)을 전제합니다. 반면 현실의 AI 에이전트는 웹 검색, 물리 센서, API 응답, 그리고 인간(HITL)이라는 외부 비결정적 환경과 끊임없이 상호작용합니다(이를 인터랙티브 튜링 기계 또는 경험적 오라클이라 부름). 즉 현대 AI는 고립된 계산의 한계를 외부 세계와의 실시간 상호작용 루프로 확장해 나가고 있습니다.

INFOGRAPHIC 02 · AI · LLM 생태계에서 처치-튜링 명제가 지배하는 4대 영역 이론적 동치성과 물리적 한계가 실제 AI 연구·코딩 에이전트·AGI 논쟁을 어떻게 규정하는가
AI · LLM에서 처치-튜링 명제(Church-Turing Thesis)가 갖는 4대 의미 LLM 튜링 합류 · 하드웨어 한계선 · 다중 언어 번역 근거 · AGI(뇌-기계 동치) 철학 ① 딥러닝 ➔ 보편 계산(Turing-Complete) 합류 • 1-Pass Transformer = 고정 깊이 회로 TC⁰ (제한적) • CoT 스크래치패드 + 코드 실행 도구 결합 시 ➔ 튜링 완전 결론 ➔ 연속 신경망도 충분한 테이프(CoT·도구)를 얻으면 고전 기호 알고리즘과 동일한 계산 능력의 반열에 합류 ② 하드웨어 상한선 : GPU · 양자칩도 계산 불가 못 푼다 • 차세대 GPU · 광학칩 · 양자컴퓨터 ➔ 속도(복잡도)만 혁신 • 정지 문제 · 라이스 정리 · 보편 무환각 필터 = 여전히 불가 결론 ➔ 계산 불가능성 해결을 신형 칩에 기대할 수 없으며, 근사 · 유한 가드레일 · 샌드박스가 영원한 아키텍처 필수요소 ③ 코딩 LLM : 모든 언어 간 보편 번역의 이론적 근거 • Python ≡ Lambda Calculus(Haskell) ≡ C++ ≡ Turing Machine • 튜링 완전 언어들의 표현력 동등성 덕분에 논리 구조 이전 가능 결론 ➔ LLM은 자연어 요구사항을 최적의 실행 패러다임 (SQL, Python, Z3 SAT, Bash)으로 자유롭게 환원·호출 ④ AGI 논쟁 : 물리적 명제 vs 펜로즈 초월계산 & 오라클 • 물리적 CT 명제 ➔ 인간 뇌가 계산체라면 AGI 실리콘 구현 가능 • 펜로즈 반론 ➔ 양자 초월계산(Hypercomputation) 미검증 쟁점 결론 ➔ 현실 AI는 실시간 웹·센서·인간(HITL) 피드백을 통해 폐쇄 계산의 틀을 넘어 상호작용형(Interactive) 지능으로 진화
SECTION 03 · FOR AI ENGINEERS

AI 개발자들에게 Church-Turing Thesis가 가지는 5대 실무 의미

처치-튜링 명제를 이해한 AI 개발자는 새로운 하드웨어나 모델 프레임워크가 쏟아질 때도 흔들리지 않는 "보편성과 한계에 대한 안목"을 갖게 됩니다.

개발자 통찰 01

하드웨어·모델 교체로 풀리지 않는 '본질 한계' 구분

GPU 세대가 바뀌고 양자컴퓨터가 발전해도 튜링 계산 불가능한 문제(무한 루프 완전 사전 판별, 100% 완벽 가드레일)는 절대 풀리지 않습니다. 개발자는 기술 신봉 대신 유한 안전 예산과 검증 루프를 설계해야 합니다.

개발자 통찰 02

가장 검증하기 쉬운 형식·언어로 문제 치환

계산 능력이 동등하다면 굳이 LLM 자연어 속에서 어설프게 계산할 필요가 없습니다. 수학 검증은 Lean4/SymPy로, 데이터 질의는 SQL로, 비즈니스 로직은 Python 함수로 치환하는 것이 보편 동치성을 가장 똑똑하게 쓰는 방법입니다.

개발자 통찰 03

'단일 패스'가 아닌 'CoT + 도구 루프'로 보편성 확보

처치-튜링 동치성은 임의 깊이 반복과 외부 작업 메모리가 있을 때 성립합니다. 정밀한 상태 추적이나 다단계 계산 작업에는 반드시 LLM에게 반복 추론(CoT)과 실행 도구(Tool Loop)를 허용하세요.

개발자 통찰 04

표현력(Computability)과 효율성(Extended CT) 분리 분석

"이 문제는 Python으로 풀 수는 있지만 느리다"는 것과 "알고리즘 자체가 불가능하다"는 것은 전혀 다릅니다. 병렬 GPU 최적화나 양자·광학 칩의 가치는 속도(Extended CT Thesis)를 바꾸는 데 있음을 정확히 구분해 투자하세요.

개발자 통찰 05

폐쇄 모델을 여는 실시간 웹·센서·인간(Oracle) 인터페이스 설계

아무리 강력한 만능 튜링 기계라도 학습 시점 이후의 변화나 현실 물리 상태는 내부 계산만으로 알아낼 수 없습니다. 현대 AI 개발자의 핵심 역량은 정적인 모델 추론 루프에 실시간 검색, API 센서, 인간 승인(Human-in-the-Loop)이라는 외부 세계 오라클을 깔끔하게 접목하는 데 있습니다.

SECTION 04 · ARCHIVE PRESERVATION

원전 해설 및 물리학·철학 함축 아카이브 (원본 보존)

.......... 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)

SECTION 05 · TERMS, SITES, PAPERS & VIDEOS

관련 용어 · 웹 사이트 · 학술 논문 · 강연 동영상 (원본 보존)

video :

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