‘계산 가능한 것’의 경계선을 묻다, 처치–튜링 명제

스마트폰 계산기에서 더하기 버튼을 누르면 답이 즉시 나온다. 사람은 머릿속으로 계산하지만, 기계는 미리 짜인 절차를 따라 움직인다. 처치–튜링 명제는 이때 쓰이는 모든 ‘기계적 계산’이 궁극적으로 같은 힘을 지닌다고 말한다.

다시 말해, 연필과 종이로든 노트북이든, 혹은 상상 속 기계이든 수행할 수 있는 절차적 계산은 하나의 표준 모델, 곧 튜링 머신과 동등하다는 주장이다.

이 명제는 현대 컴퓨터 과학의 토대다. 어떤 문제는 애초에 프로그램으로 풀 수 없는 이유도, 어떤 언어가 다른 언어만큼 강력한 이유도 여기에서 출발한다.

기원과 역사

1936년 알론조 처치는 람다 계산법으로 ‘효과적으로 계산 가능한 함수’ 개념을 수학적으로 정식화했다.

같은 해 앨런 튜링은 ‘계산 가능한 수’ 논문에서 테이프 위를 이동하며 기호를 읽고 쓰는 이상 기계, 즉 튜링 머신을 제안했다.

두 모델이 표현하는 함수 집합이 일치한다는 사실이 곧 입증되면서 ‘하나의 본질적 개념이 둘로 나타났다’는 통찰이 생겼다.

이어 에밀 포스트는 표준 기호 체계를 단순화한 제한형 기계를 정의해 동일한 결과를 얻어, 모델 간 등가성이 더욱 확고해졌다.

명제의 핵심 내용

처치–튜링 명제는 “모든 효과적 절차는 튜링 계산으로 모사 가능하다”는 한 문장으로 요약된다. 여기서 ‘효과적’이란 사람이 기계적 단계로 따를 수 있는 절차를 뜻한다.

처치와 튜링은 각각 람다식·튜링 머신으로 효과적 절차를 정의했고, 둘이 같은 범위의 함수를 산출함을 보였다. 이는 결정 불가능성, 즉 어떤 문제는 절대 해결 규칙이 없다는 결과로 이어진다.

명제는 정리(수학적 증명)라기보다 경험적 가설이다. ‘효과적’이라는 직관적 개념을 완벽히 형식화한 모델이 이미 여럿 있지만, 그 이상 강력한 모델이 물리적으로 가능하다는 증거는 아직 없다.

유명한 번외 효과는 ‘정지 문제’다. 어떤 프로그램이 언젠가 멈출지를 판정하는 범용 알고리즘은 존재하지 않는다는 사실이 여기서 나온다.

물리적 해석과 확장

1985년 데이비드 도이치는 양자역학을 바탕으로 ‘물리적 처치–튜링 원리’를 제시하며, 물리적으로 구현 가능한 모든 계산은 양자 튜링 머신으로 모사 가능하다고 주장했다.

그의 시각은 “우주 자체가 보편 컴퓨터”라는 디지털 물리학으로 확장돼 왔다.

많은 이론가가 이 원리가 지금까지 실험과 합치한다고 보지만, 아직 결정적 증명도 반례도 없다.

반대편에서는 연속 값을 무한 정밀도로 다룰 수 있는 ‘아날로그 계산’이 이론상 더 강력할 수 있다고 제기한다. 단, 실제 물리 한계가 이를 허용할지는 미지수다.

양자 컴퓨팅과 논쟁

양자 컴퓨터는 소수 분해처럼 특정 문제를 고전 컴퓨터보다 훨씬 빠르게 풀지만, 계산 종류 자체를 확장하진 않는다. 이는 양자 튜링 머신과 복잡도 클래스 BQP 연구로 확인됐다.

양자 회로와 양자 튜링 머신이 다항 시간 안에 서로 모사 가능하다는 결과는 ‘양자도 결국 튜링 범주 안’임을 시사한다.

즉 양자 속도 향상은 ‘얼마나 빨리’이지 ‘무엇을’ 계산하느냐를 바꾸지 않는다.

일부 연구자는 양자역학과 일반상대성이 결합된 극한 조건에서 초계산이 가능할 수 있다고 추정하지만, 실험이나 이론적 일관성은 확보되지 않았다.

초계산 이론

수학자들은 오라클 머신, 무한 시간 튜링 머신 같은 모델을 고안해 ‘튜링 한계 너머’를 탐험했다.

마라먼트–호가스프 시공 등 일반상대론적 공간에서는 무한 계산을 유한 관찰자가 볼 수 있다는 시나리오가 제안되기도 했다.

그러나 이런 모델은 무한 정확도, 무한 속도, 특수한 우주 구조 같은 비현실적 가정을 요구한다.

현재까지 물리적으로 실현 가능한 초계산 장치의 청사진은 없다. 처치–튜링 명제는 여전히 실험에 부합한다.

현대 기술과 교육

모든 범용 프로그래밍 언어가 ‘튜링 완전’하다는 평가는 명제에서 비롯된다. 파이썬·자바·C는 서로 다른 문법일 뿐 동일한 계산 능력을 지닌다.

암호학과 복잡도 이론도 이 틀 위에서 발전했다. NP 완전, P 대 NP 같은 유명 난제 역시 튜링 모델을 기준으로 정의된다.

컴퓨터 공학 교육 과정은 기본적으로 ‘계산 가능·불가능’ 구분을 가르치며, 이 경계선 위에 프로그래밍 실무를 배치한다.

철학·인지과학에서는 인간 사고가 튜링 기계와 동등한지, 아니면 더 강력한지 논쟁이 이어지고 있다.

연구 동향

2023년 발표된 연구는 23종의 생화학 반응 네트워크가 모두 튜링 완전함을 보이며, 자연계 시스템도 계산 한계 안에 있음을 시사했다.

같은 해 최종 합의된 EU AI Act는 고위험 AI 시스템이 ‘예측 불가능한 초계산’을 일으키지 않도록 데이터·모델 검증을 의무화했다.

2024년 리뷰 논문들은 양자·아날로그·생체 계산이 명제의 경계를 시험했지만, 현실적 반례를 찾지 못했다고 결론냈다.

이에 따라 명제는 ‘반증되지 않은 경험 법칙’으로서 과학·공학 설계의 디폴트 가정을 계속 유지한다.

연구자들은 양자중력 이론을 반영한 계산 모델, 혹은 우주론적 특이점 근처 정보 처리를 탐색하며 명제의 물리적 한계를 다시 시험할 계획이다.

반면 산업계·규제 당국은 CT 범위 안에서 안전·투명·해석 가능성을 높이는 방향으로 AI 기술을 관리하려 한다.

학계에서는 ‘명제에 대한 확신이 기술 규범의 기둥’이라는 인식 아래, 초중등 교육용 교재에도 계산 가능성 구분을 심화 반영할 움직임이 나타나고 있다.

결국 처치–튜링 명제는 88년 전 선언 이후 단 한 번도 실험에 배신당한 적이 없다. 인류는 이 명제를 신뢰하며 새로운 계산 장치를 설계하고, 혹시 모를 반례를 찾아 우주 깊숙한 곳까지 시선을 뻗칠 것이다.

한국정보기술신문 정보기술분과 전호재 기자 news@kitpa.org