처치–튜링 논제(Church–Turing thesis)

'정해진 규칙을 기계적으로 따라가면 답이 나온다'는 말은 누구나 알아듣지만, 정의는 아닙니다. 1930년대 중반 여러 사람이 이것을 각자 다른 방식으로 엄밀하게 정의했습니다. 미국 논리학자 알론조 처치의 람다 계산⁠(lambda calculus)⁠이 있었고, 괴델과 프랑스의 자크 에르브랑, 미국의 스티븐 클리니가 다듬은 재귀 함수⁠(recursive function)⁠가 있었습니다. 재귀 함수는 0과 '다음 수'에서 출발해 함수⁠(function)⁠ 합성, 되부름(재귀⁠(recursion)⁠), '조건을 만족하는 가장 작은 수 찾기'만으로 만들어지는 자연수⁠(natural number)⁠ 함수입니다. 여기에 튜링의 튜링 기계, 그리고 미국의 에밀 포스트가 따로 구상한 비슷한 기계가 더해졌습니다. 출발점은 제각각이었는데, 곧 이들이 계산할 수 있는 함수가 정확히 같다는 것이 증명되었습니다. 처치–튜링 논제는 이 공통의 범위가 곧 '기계적으로 계산할 수 있는 것' 전부라는 주장입니다. 튜링 기계로 계산할 수 있으면 기계적으로 계산할 수 있다는 쪽은 당연합니다. 논제의 알맹이는 거꾸로, 기계적으로 계산할 수 있는 것은 무엇이든 튜링 기계로도 계산할 수 있다는 쪽입니다.

:

논제의 한쪽은 '기계적 계산'이라는 직관이라 수학적으로 증명할 수 있는 정리가 아닙니다. 모형끼리 같다는 것은 정리이지만, 그 모형이 직관을 다 잡았다는 것은 증거로 받아들이는 주장입니다. 증거는 세 가지입니다. 동기가 전혀 다른 모형들이 모두 같은 곳에 닿았고, 튜링은 사람이 종이에 계산하는 과정을 직접 분석해 기계를 만들었으며, 그 뒤 90년 동안 어떤 반례도 나오지 않았습니다. 그래서 오늘날 "그것을 하는 알고리즘⁠(algorithm)⁠은 없다"는 말은 "그것을 하는 튜링 기계는 없다"는 뜻으로 쓰이고, 정지 문제⁠(halting problem)⁠가 대표적인 예입니다. 기계는 가산개뿐인데 자연수에서 자연수로 가는 함수는 셀 수 없이 많으니, 계산할 수 없는 함수가 계산할 수 있는 함수보다 훨씬 많습니다.

놀랍도록 단순한 체계도 이 범위에 닿습니다. 한 줄의 칸이 매 순간 자기와 양옆, 세 칸만 보고 다음 값을 정하는 세포 자동자⁠(cellular automaton)⁠에서 규칙 번호는 여덟 가지 이웃 모양에 대한 답을 이진수로 읽은 수입니다. 규칙 은 이고, 처음 줄은 입니다. 규칙 110⁠(Rule 110)⁠은 보편 계산이 가능합니다. 끝없이 되풀이되는 배경 무늬 위에 처음 줄을 알맞게 짜 주면 어떤 튜링 기계의 계산이든 흉내 낼 수 있다는 뜻으로, 매슈 쿡의 증명이 2004년 논문으로 출판되었습니다. 규칙 30은 무작위처럼 보이는 무늬를 만듭니다. 규칙 90을 한 칸에서 시작하면 파스칼의 삼각형⁠(Pascal's triangle)⁠의 수를 2로 나눈 나머지⁠(remainder)⁠가 나오는데, 이것이 삼각형 가운데를 되풀이해 파낸 무늬인 시에르핀스키 삼각형입니다(폴란드 수학자 바츨라프 시에르핀스키의 이름을 땄습니다).

논제는 무엇을 계산할 수 있는지만 말하고, 얼마나 빨리 계산하는지는 말하지 않습니다. 모형을 서로 흉내 낼 때는 보통 다항식⁠(polynomial)⁠ 정도의 비용이 더 들 뿐입니다. 한 모형에서 t걸음 걸리는 계산을 다른 모형이 $t^2$이나 $t^3$걸음쯤에 해낸다는 뜻입니다. 다항식에 다항식을 합성해도 다항식이므로, 어떤 문제가 '빨리'(다항식 걸음 안에) 풀리는지는 합리적인 모형 사이에서 달라지지 않고, 이것이 P 대 NP 문제⁠(P versus NP problem)⁠를 모형과 상관없이 물을 수 있는 이유입니다. 여기서 한 걸음 더 나아가 '물리적으로 만들 수 있는 모든 계산 장치는 튜링 기계가 다항식 비용만 더 들여 흉내 낼 수 있다'는 강한 형태의 논제도 있습니다. 이것을 흔드는 것이 양자역학의 중첩을 계산에 쓰는 양자 컴퓨터입니다. 양자 컴퓨터⁠(quantum computer)⁠는 계산할 수 있는 함수의 범위는 넓히지 않습니다. 하지만 미국 수학자 피터 쇼어가 1994년에 내놓은 알고리즘을 쓰면, 충분히 큰 양자 컴퓨터는 소인수분해⁠(prime factorization)⁠를 다항식 걸음에 해낼 수 있어 RSA를 위협합니다. 보통 컴퓨터로는 소인수분해의 다항 시간⁠(polynomial time)⁠ 방법이 알려져 있지 않습니다. 그런 방법이 정말 없고 큰 양자 컴퓨터를 실제로 만들 수 있다면, 강한 형태의 논제는 틀린 셈입니다. 두 물음 모두 아직 열려 있습니다.

이어지는 곳. 이 논제 덕분에 '그런 알고리즘은 없다'는 말을 '그런 튜링 기계는 없다'는 정리로 바꿔 증명할 수 있습니다. 계산 모형의 사다리에서 튜링 기계는 맨 위에 있고, 기억이 유한한 유한 오토마톤⁠(finite automaton)⁠은 맨 아래에 있습니다. 문법으로 본 같은 사다리가 촘스키 위계⁠(Chomsky hierarchy)⁠입니다. 세포 자동자의 무늬는 규칙이 결정론적인데도 앞날을 알려면 한 걸음씩 돌려 보는 수밖에 없어 보이는 경우가 많다는 점에서 혼돈⁠(chaos)⁠과 닮았습니다. 다만 혼돈은 처음 값의 아주 작은 차이가 점점 커지는 현상이고, 여기서 막히는 까닭은 결과를 미리 알려 주는 지름길이 알려져 있지 않다는 데 있어 이유가 다릅니다. 물리 법칙으로 일어나는 모든 과정을 튜링 기계로 흉내 낼 수 있는가를 묻는 '물리적 처치–튜링 논제'도 있습니다. 괴델의 불완전성 정리⁠(incompleteness theorem)⁠가 말하는 '형식 체계⁠(formal system)⁠'도 증명을 기계가 확인할 수 있는 체계, 곧 이 논제가 말하는 뜻의 기계적인 체계입니다.