Turing'sProof

(여기에서는 튜링 기계와 튜링 계산가능성에 대하여 튜링의 원본 논문을 보면서 알아보고, 튜링이 제시한 철학적 고찰점들에 대하여 수학적, 기계적, 기술적으로가 아닌 철학적, 추상적으로 논의한다. 튜링 기계와 튜링 계산가능성에 대한 수학적, 기계적, 기술적인 정의와 그 논의는 현대 수리논리학의 관점에서 재정리한 계산가능성 포스트에 정리해두었다.)

튜링 머신은 앨런 튜링이 수리 논리학의 문제를 풀기 위하여 만든 개념이다. 튜링 머신은 매우 강력하지만 매우 단순하며, 튜링 머신의 기능 하나라도 제거하면 그것은 아무것도 할 수 없다. 튜링 머신은 컴퓨터의 최초의 이론적 모델이다. 컴퓨터의 근본을 파헤침으로써 컴퓨터가 가능한 것과 불가능한 것을 이해할 수 있다. 그래서 튜링 머신은 컴퓨터 공학자들이 많은 관심을 갖지만, 정작 튜링의 실제 논문 《On Computable Numbers, with an Application to the Entscheidungsproblem》 에 관심을 가지는 사람은 몇 없다. 여기에서는 이 튜링의 논문을 이해해볼 것이다.

튜링의 목적은 힐베르트가 풀려했던 수리 논리학의 임의의 명제의 증명가능성을 판단하는 일반적인 과정을 찾는 문제인 "Entscheidungsproblem" 을 푸는 것이었다. 하지만 튜링의 논문은 (기계에 의하여) 계산가능한 수에 대하여서도 많이 다뤘다. 계산가능한 수와 실수의 차이를 이해하는 것은 중요하기에 먼저 수에 대하여 가볍게 살펴보자.

디오판토스와 페르마의 유산✔

고대 그리스 때 디오판토스가 다룬 2차 이하의 방정식들은 대부분 해가 있었다. 17세기에 디오판토스의 대수학 저서 『Arithmetica』 가 라틴어로 번역되어 페르마에게 읽힌 후, 페르마는 이 책에 관한 자신의 메모를 많이 남겼다. 이 메모들 중 \(x ^{3} + y ^{3} = z ^{3}\) 꼴의 방정식에 정수 해가 존재하지 않는다는 등의 페르마의 마지막 정리가 있었다. 이때부터 수학자들은 방정식의 해를 구하는 것이 아니라 방정식이 풀리는지, 풀리지 않는지 판단할 수 있는 판정법을 찾는 것에 관심을 갖기 시작했다. 방정식이 풀리는지 어떻게 알 수 있을까?

무리수, 대수적 수, 초월수✔

대수적 방정식은 다음과 같은 형태의 방정식이다.

디오판토스 방정식과 대수적 방정식은 다른데, 디오판토스 방정식은 다변수 방정식이기 때문이다. 대수적 방정식의 해가 되는 수를 대수적 수(algebraic number)라 한다. 위와 같은 대수적 방정식을 n차 다항식으로 볼 수 있는데 n차 다항식은 최대 n개의 해를 갖는다.

대수적 수는 모든 정수와 모든 유리수와 제곱근으로 나타내어질 수 있는 무리수를 포함한다. 오일러는 대수적 수가 아닌 무리수가 존재함을 보이고 이러한 수들을 초월수(transcendental number)라 정의했다. 리우빌은 특정한 초월수를 보였는데 이는 다음과 같다.

이 수는 \(1\) 이 팩토리얼 수번째에 나타나도록 만든 것이다. 즉, 리우빌 수에서는 \(1\) 이 \(1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, \dots\) 번째에 나타난다. 리우빌 수는 어떠한 대수적 다항식의 해가 될 수 없는 초월수다. 린데만은 \(\pi\) 가 초월수임을 증명했다. 또 다른 유명한 초월수는 \(e = \displaystyle \lim_{x \to \infty} \bigg (1+\frac{1}{x} \bigg )^{x}\) 이다.

역사적으로 많은 수가 초월수임이 밝혀졌지만 어떤 수가 초월수라는 것을 판정하는 일반적인 방법은 아직도 발견되지 않았다. 지금까지도 수학자들은 \(\pi ^{\pi }\) 가 초월수인지 판정중이다.

튜링의 논문은 허수를 제외하고 실수로 논의영역을 한정했다.

자연수와 전단사 대응을 갖는 집합을 열거가능(enumerable), 또는 가산(countable) 이라 한다. 자연수는 1, 2, 3, 4, ... 로 열거 할 수 있다. 칸토어는 대수적 수 또한 열거가능임을 증명했고, 실수는 열거 불가능임을 보였다. 실수는 직관적으로 열거 불가능한데, 가령 실수 1 다음의 수를 말하기는 곤란하다. 칸토어는 실수가 열거 불가능하다는 증명이 곧 초월수의 존재성 증명임을 깨달았다. 초월수가 존재하지 않으면 실수는 열거 가능하기 때문이다. 칸토어는 초월수도 열거 불가능함을 증명했다. 칸토어는 무한을 열거가능한 무한과 열거 불가능한 무한으로 구분했다. 이에 따라 집합의 기수는 열거가능한 집합의 기수(자연수, 유리수, 대수적 수 등)와 열거불가능한 집합의 기수(초월수, 실수, 연속체 등)로 구분된다. 열거가능함을 셀 수 있는 집합이라 하여 가산 집합, 열거 불가능함을 셀 수 없는 집합이라 하여 비가산 집합이라고도 한다.

유한집합의 진부분집합의 기수는 항상 원래의 집합의 기수보다 작다. 무한집합의 특성은 진부분집합과 원래의 집합의 기수가 같을 수도 있다는 것이다. 가령 짝수는 자연수의 진부분집합이지만 서로 기수가 같다. 자연수는 실수의 진부분집합이고 실수의 기수보다 작은 기수를 갖는다. 칸토어는 \(\R \approx \R ^{2}\) 를 증명하고 "내가 이것을 증명했지만, 나는 이것을 믿지는 않는다" 라며 놀라움을 표현했다.

칸토어는 자연수의 기수를 \(\aleph _0\) 로 표현했고 수학의 모든 초한수를 표현하기 위하여 \(\aleph _1, \aleph _2, \aleph _3, \dots\) 의 표기를 택했다. 실수의 기수는 어떤 초한수에 해당할까? 일단 실수의 기수는 \(2 ^{\aleph _0}\) 로 알려져있다. 칸토어는 연속체의 기수 \(2 ^{\aleph _0}\) 가 초한수 \(\aleph _0\) 바로 다음의 초한수인 \(\aleph _1 = 2 ^{\aleph _0}\) 라는 연속체 가설을 세웠다. 칸토어는 연속체 가설을 증명하기 위하여 부단히 애썼지만 실패했다.

힐베르트 프로그램✔

힐베르트가 제시한 문제들 중 10번째 문제는 다음과 같았다.

Entscheidung 는 결정, 결정가능성, 판정이라는 뜻이다. 이 문제의 뜻은 "Determination of the Solvability of a Diophantine Equation" 이다. 즉, 주어진 디오판토스 방정식을 풀 수 있는지 판정하는 유한한 결정과정을 찾는 것이다. 힐베르트의 문제는 모든 디오판토스 방정식을 푸는 방법을 요구하는 것이 아니라 방정식이 풀릴 수 있는지 판정하는 것을 요구한다. 즉, 힐베르트는 유한한 알고리즘을 원한 것이다. 힐베르트는 이 알고리즘이 존재한다고 굳게 믿었다.

1893년 프레게는 『Grundesetze der Arithmetik』 을 출판했지만 판매율이 저조해서 출판사에서 2판을 출판하기를 원치 않아했다. 하지만 아주 중요한 독자가 이 책을 읽었는데, 바로 러셀이다. 러셀은 1902년 『The Principles of Mathematics』 의 출판작업에 돌입했고, 그러면서 집합론의 모순을 밝혀냈다. 그 모순이란 이러하다. 집합은 다른 집합을 원소로 가질 수 있고, 집합은 자기 자신 또한 원소로 포함시킬 수 있다. 그렇다면 자기 자신을 집합으로 갖지 않는 모든 집합들을 원소로 갖는 집합은 어떠한가? 이 집합이 만약 자기 자신을 포함하지 않으면, 자기 자신을 포함하지 않는 집합이므로 자기 자신을 포함할 것이다. 만약 자기 자신을 포함한다면, 자기 자신을 포함하는 집합이므로 자기 자신을 포함하지 않을 것이다.

러셀은 이 모순을 프레게에게 알렸고, 프레게는 충격에 빠졌다. 프레게는 그의 책 2판의 부록을 급히 추가했지만, 이 모순이 해결되지는 않았다. 왜냐하면 이 자기지시성(self-referentiality)에 의하여 발생하는 모순은 프레게의 인생의 업적 모든 곳에서 근본적으로 존재했기 때문이다. 러셀은 이 자기지시성을 제거하면 집합론을 모순으로부터 자유케할 수 있음을 깨닫고, 타입 이론(type theory)을 개발했다. 러셀은 집합의 위계를 구축하여, 가장 밑바닥에는 1종(Type 1) 집합을 두었다. 1종 집합은 숫자 같은 개별 원소만 지닌다. 1종 집합은 오직 2종 집합에만 포함될 수 있다. 2종 집합은 3종 집합에만 포함될 수 있다. 일반적으로 n종 집합은 (n+1)종 집합에만 포함될 수 있다.

이 시기에 러셀은 『The Principles of Mathematics』 의 2판 작업을 시작했다. 그의 작업은 논리주의 학파에서 프레게의 작업을 계승하는 것이었다. 이때 러셀은 힐베르트와 함께 논리주의 학파의 작업을 하고 싶어 했지만, 영국과 독일의 전쟁으로 인하여 이 둘의 합작이 어려워졌다.

1917년 힐베르트는 "공리적 생각"을 기반으로 수학의 기초에 대한 작업을 시작했다. 이때 사람들은 힐베르트 프로그램에 대하여 알 수 있었다. 그리고 힐베르트가 논리주의 학파를 버리고 모든 수학의 완전하고 엄밀한 공리화를 추구한 것이 이 시기즈음이다. 힐베르트는 공리주의 체계를 분석하여 메타수학(metamathematics, 상위수학)과 증명이론(proof theory)를 만들고, 이것을 수학 체계의 구조에 대한 결론을 이끌어내는 수리논리학으로 사용하려 했다. 이 힐베르트의 아이디어가 이후에 형식주의 학파로 발전되었다. 힐베르트에게 수학 체계란 공리와 정의, 그리고 추론규칙에 의한 정리였다. 힐베르트가 상상하는 이상적인 수학 체계는 다음과 같은 상호 관련된 성질을 지녀야 했다.

• 독립성(Independence)
• 일관성(Consistency, 무모순성)
• 완전성(Completeness)
• 결정가능성(Decidability, Entscheidung)

독립성이란 공리들이 서로 독립적인 수학 체계를 뜻한다. 즉, 수학자들이 유클리드 원론에서 처음 4개의 공리로 5번째 공리를 도출할 수 있지 않을까 하며 항상 우려했던 것과 비슷한 일이 발생하면 안된다.

무모순성은 가장 중요한 성질인데, 서로 상반된 주장을 하는 정리가 도출되지 않는 수학 체계를 뜻한다. 이 성질이 중요한 이유는 모순된 정리가 도출되면, 그것으로부터 존재하는 모든 주장을 참이라고 증명할 수 있는 논리적 도구가 마련되기 때문이다.

완전성은 모든 참인 명제가 공리로부터 증명되는 정리가 되는 수학 체계를 뜻한다. 설령 증명가능하지 않은 명제일지라도 우리는 참이라고 여기는 경우가 있다. 가령 골드바흐의 추측이 증명되지는 않았지만 거의 모두가 그것을 참이라고 본다.

또한 힐베르트는 수학 체계가 지녀야할 중요한 특성으로 결정가능성을 선정했는데, 이는 수학체계에 잘 형성된 명제(wff, well-formed formula)의 증명가능성을 판단하는 일반적인 방법이 존재한다는 특성이다. 수학 체계가 불완전해도 결정가능성을 지닐 수 있다. 증명 불가능한 명제가 존재하더라도 그 명제가 증명 불가능하다는 결론을 이끌어내는 결정 절차가 존재할 수도 있고, 더 강력한 결정 절차가 존재한다면 설령 증명 불가능한 명제일지라도 그 명제의 참거짓을 밝힐 수도 있다.

힐베르트는 먼저 결정가능성 문제를 디오판토스 방정식으로 연결시켰다. 그리고 그는 결정가능성을 뜻하는 Entscheidung 와 problem 을 연결시켜서 Entscheidungsproblem(결정가능성 문제) 라는 단어를 사용하기 시작했다. 힐베르트의 조수 아커만은 힐베르트의 강의를 수집하여 책을 냈는데 지금은 "Hilbert & Ackermann"(힐베르트&아커만) 라는 제목으로 더 알려져있다. 이 책은 1차 논리에 대하여 설명하고 있었다.

괴델의 불완전성 정리✔

이 책의 초기 독자 중 쿠르트 괴델이 있었는데, 괴델은 1차 논리에 대한 서술 중 다음과 같은 구절을 읽었다.

괴델은 공리 체계의 완전성에 관한 문제를 해결하는 과정에서 1차 논리가 완전한 체계임을 증명했다. 1차 논리에서 참인 명제는 증명 가능하다. 이것이 괴델의 완전성 정리이다. 이 정리는 공리와 증명 메커니즘이 모든 참인 명제를 도출하기에 적절함을 뜻한다. 즉, 불필요한 공리가 없고 추가적으로 더 필요한 공리가 없으며 추론 규칙 또한 더하거나 뺄 필요 없이 완전하다는 것을 뜻한다.

1차 논리의 주된 목적 중 하나는 산술 체계의 기초를 제공하는 것이었다. 즉, 논리 체계에 공리를 추가하여 수 체계를 구축하는 것이다. 수 체계를 형성할만큼 충분한 공리가 추가된 1차 논리는 완전할까? 괴델은 이제 이 문제를 해결하려 했다. 그리고 결국 괴델은 산술 체계를 구축할 수 있을만큼 1차 논리에 공리를 추가하면 완전성이 사라지고 불완전 체계가 된다는 것을 증명했다. 괴델은 만약 산술이 무모순적이라면, 참인 명제 중 어떤 명제는 반드시 증명 불가능하다는 것을 증명했다. 이것이 괴델의 불완전성 정리이다. 불완전성 정리의 중요한 전제는 산술 체계의 무모순성이었다. 괴델은 불완전성 정리의 따름정리로써 산술 체계의 무모순성을 산술 체계의 논리로 보이는 것이 불가능함을 증명했다. 그러나 이는 산술 체계가 모순적임을 뜻하지 않는다. 단지 산술 체계 내부의 논리로 산술 체계가 일관적이라는 것을 증명 못한다는 것이다. 수학자들 중 누구도 산술 체계가 모순적이라고 생각하지 않았다.

불완전성 정리는 수리 논리학을 연구하는 수학자들에게 너무나도 큰 충격이었다. 불완전성 정리는 모든 수학 기초론, 산술 체계의 무모순성과 완전성 등등 모든 진리를 밝힐 수 있다는 낙관론에 빠져있던 수학자들에게 찬물을 끼얹었다. 힐베르트는 괴델의 정리를 듣고 처음에는 분노했지만, 결국 괴델의 불완전성 정리를 인정하고 이 정리를 힐베르트 프로그램에 포함시켰다. 다른 수학자들은 수리 논리학 자체에 흥미를 잃어버리기도 했다. 러셀은 『The Principles of Mathematics』 를 계속해서 집필하는데에 지적 호기심이나 흥미를 완전히 잃어버렸고 철학, 정치학, 사회적 문제에 자신의 흥미를 돌렸다. 심지어 폰 노이만도 괴델 이후에 수리 논리학을 버렸다. 그러나 이후에 폰 노이만이 디지털 컴퓨터를 개발할 때 수리 논리학의 원리를 적용하였다.

그러나 수리 논리학에 잔류한 수학자들은 아직 남아있는 문제를 풀기 시작했다. 불완전성 정리는 결정가능성이 말하는 결정 절차가 존재하지 않는다는 것을 뜻하지 않았다. 그러나 불완전성 정리는 결정 절차가 모든 참인 명제가 증명가능하다는 것을 판정할 수 없음을 말해주었다. 몇몇 타입의 수리 논리학의 명제들에 대하여 이미 결정 절차가 개발되어 있었다. 하지만 일반적인 결정 절차는 존재하지 않을 것 같았고, 실제로 그러함이 증명되었다. 알론조 처치가 "The general case of the Entscheidungsproblem of first-order predicate logic is unsolvable" 임을 증명했고 알론조 처치와 완전히 독립적으로 앨런 튜링이 같은 결론("the Hilbertian Entscheidungsproblem can have no solution")을 이끌어 내었다. 즉, 괴델이 힐베르트 프로그램의 완전성을 부정하는 불완전성을 증명했다면, 처치와 튜링은 결정가능성을 부정하는 결정불가능성(undecidability)을 증명했다.

어떤 프로그램에 버그가 있는지 분석하는 프로그램을 만들 수 있을까? 이런 프로그램이 만들어진다면 다른 프로그램을 디버깅할 수 있고 매우 가치 있을 것이다. 이러한 프로그램을 만들기 어려운 것은 알겠지만, 이론적으로라도 가능하기는 할까? 그 대답은 불가능하다이다. 일반화된 버그 찾는 알고리즘은 이론적으로 존재하지 않는다. 왜 그럴 수밖에 없는지 앨런 튜링의 계산 가능한 수와 Entscheidungsproblem 에 대한 논문을 살펴보자.

튜링의 등장✔

앨런 튜링은 10살 때 인간의 몸도 기계라고 주장하는 책을 읽었다. 튜링은 인간의 몸과 심지어 마음까지도 일종의 기계의 결과물이라는 인식을 갖게 되었다. 그는 자연스럽게 인간의 몸과 기계 사이의 관계를 탐구하게 되었다. 튜링이 수리논리학이라는 희소한 분야에 관심을 기울이기 시작한 것은 러셀의 책 『Introduction to Mathematical Philosophy』 를 읽고나서부터였다. 이후 튜링은 뉴먼의 수학기초론 강의를 들었는데, 이 강의의 클라이맥스는 괴델의 불완전성 정리였다. 뉴먼의 강의는 아직 풀리지 않은 Entscheidungsproblem(수학 명제가 증명가능한지 판단하는 기계적인 과정을 정의하라) 도 설명했다. 뉴먼은 문제를 풀기 위한 절차의 집합을 알고리즘(Algorithm)이라고 설명했다.

튜링은 Entscheidungsproblem 를 풀기 시작했고 곧 뉴먼 교수에게 《On Computable Numbers, with an Application to the Entscheidungsproblem》 라는 논문을 제출했다. 튜링의 논문은 수학 증명에 대한 일반적이지 않은 접근을 취했다. 튜링은 이 논문에서 매우 단순한 가상의 계산 기계를 소개했는데, 그 단순성에도 불구하고 이 기계의 능력이 인간의 수학적 계산 능력과 같다고 주장했다. 튜링은 이 기계로 \(1/3\) 을 이진수로 표현했고 무리수와 초월수도 이진수로 표현해 보였다. 또한 튜링은 다른 모든 계산 기계를 흉내낼 수 있는 보편 기계(Universal Machine)를 만들었다.

계산가능한 수✔

그러나 튜링 기계들은 모든 실수(real number)를 계산할 수는 없었다. 튜링이 고안한 계산 기계들은 유한한 연산을 갖기 때문이다. 튜링은 기계의 연산을 숫자로 대응시켰는데, 이로써 각각의 계산 기계를 Description Number 라는 유일한 정수로 대응시킬 수 있었다. 따라서 튜링 기계는 열거가능(enumerable)하다. 튜링 기계가 계산 할 수 있는 수를 계산가능한 수(computable number)라 한다. 계산가능한 수는 반드시 열거가능해야 하고, 실수는 열거가능하지 않다. 계산가능한 수는 대수적 수를 포함하고 \(\pi\) 나 \(e\) 같은 초월수도 포함한다. 그러나 실수가 열거가능하지 않으므로 계산 가능한 수는 모든 실수를 포함하지 못한다.

튜링 기계는 절대적이지 않다. 이상하게 행동하는 튜링 기계를 쉽게 만들 수 있고, 아무 동작도 못하는 튜링 기계도 만들 수 있다. 따라서 튜링은 튜링 기계를 만족 기계(satisfactory machine)와 불만족 기계(unsatisfactory)로 구분했다. 튜링 기계가 완전히 Description Number 만으로 정의될 수 있기에 Description Number 를 분석하여 특정 기계가 만족 기계인지 불만족 기계인지 판단하는 튜링 기계도 만들 수 있어 보였다. 그러나 튜링은 이것이 불가능함을 보였다. 튜링 기계가 요구를 모두 만족하는 만족 기계라는 것을 판단할 일반적인 절차는 존재하지 않는다. 한 튜링 기계가 다른 튜링 기계를 분석할 유일한 방법은 그 튜링 기계의 연산을 한 단계 한 단계 밟아보는 것이다. 그래서 분석하는 의미가 없다. 즉, 어떤 튜링 기계가 무엇을 하는지 알기 위하여 그것을 직접 실행하는 방법 밖에 없다. 컴퓨터는 보편 기계이고 컴퓨터 프로그램은 튜링 기계이므로 이 사실은 컴퓨터 프로그램에도 적용된다. 즉, A 라는 컴퓨터 프로그램이 B 라는 프로그램을 분석하는 방법은 B 를 실행해보는 것밖에 없다.

같은 시기 알론조 처치가 다른 방법으로 힐베르트 프로그램의 Entscheidungsproblem 가 풀 수 없는 문제임을 증명해서 튜링은 논문의 부록에 자신이 언급하는 계산가능성(computability)과 처치의 효과적인 계산가능성(effective calculability)이 같은 개념이라는 말을 추가했다.

튜링은 계산가능한 수를 유한한 방법으로 소수(decimal)를 계산할 수 있는 실수로 정의했다. 이는 그가 논의영역을 실수로 한정하고 계산가능한 수를 실수의 부분집합임으로 정의했음을 뜻한다. 초월수 \(\pi\) 가 계산가능한 수에 포함된다고 언급했었는데 \(\pi = 3.14159 \dots\) 이므로 소수를 유한한 방법으로 계산하지 못할 것 같아 보인다. 그러나 무한한 소수를 계산하는 과정 자체가 무한할지 몰라도 이 과정을 진행하는 방법은 유한한 규칙과 유한한 절차로 이루어져 있으므로 유한하다. 즉, 기계에 의하여 소수를 계산할 수 있는 수는 계산 가능한 수이다.

튜링은 논문에서 \(\pi\) 나 \(e\) 같은 초월수 몇몇은 계산가능하다고 했다. 또한 그는 모든 초월수가 계산가능한 것은 아니라고 했다. 계산가능한 수의 범위가 꽤 크긴 하지만, 열거가능하므로 실수보다는 작다.

튜링의 논문 《On Computable Numbers, with an Application to the Entscheidungsproblem》✔

이제 튜링의 논문의 11개 챕터중 첫번째 챕터부터 살펴보자.

§1 - Computing Machines✔

튜링은 계산가능한 수를 기계(유한한 방법)로 써내려갈 수 있는 수로 정의하고, "유한한 방법"을 인간의 유한한 기억으로 정당화했다. 이런 식으로 튜링은 인간의 마음을 유한한 상태를 갖는 기계와 연결시켰다.

m 은 machine 을 뜻한다. 기계는 유한한 설정을 갖고 각 설정마다 다른 일을 한다. 이것을 상태라고도 할 수 있다. 튜링은 마음의 상태를 기계의 상태와 같은 것으로 보았다. 가령 세척 기계는 채우기, 씻기, 거품칠하기, 돌리기 라는 유한한 상태를 갖는다. 인간의 마음도 마찬가지다. 가령 인간은 긴 나눗셈을 할 때 "이제 곱셈을 해야겠어", "이제 뺄셈을 해야겠군", "이제 나머지를 구해야 해" 라는 식으로 유한한 상태의 마음을 가진다.

튜링은 기계의 테이프가 인간의 종이와 같다고 말했다. 왜냐면 인간은 종이로 숫자를 계산하기 때문이다. 보통 튜링 기계의 테이프는 종이로 생각되어지지만 실제로 구현할 때는 마그네틱이나 컴퓨터 메모리로 구현된다.

섹션은 숫자나 알파벳을 포함할 수 있다. 테이프의 섹션에 기록되는 기호를 표현하기 위하여 튜링은 \(\mathfrak{S}\) 를 사용했다.

가령 3451번째 테이프의 기호는 \(\mathfrak{S}(3451)\) 이고 이것은 가령 'A' 일 수 있다.

즉, 기계는 모든 테이프를 한번에 볼 수 없고 한 순간에 오직 한 섹션만 볼 수 있다.

가령 특정한 m-설정 \(q_{34}\) 의 기호가 A 면 m-설정 \(q _{17}\) 로 스위칭하고, 이때의 기호가 B 면 m-설정 \(q _{123}\) 으로 스위칭한다고 하자. 그러면 \(q _{17}\) 은 마지막 기호가 A 였다는 것을 알고, \(q _{123}\) 은 마지막 기호가 B 였다는 것을 안다.

m-설정은 \(q_1, q_2, \dots\) 이다. m-설정이 스캔된 기호 \(\mathfrak{S}(r)\) 와 함께 있으면 단순히 설정(configuration)이라 한다. 기계는 한 m-설정에서 스캔된 기호에 의하여 다른 m-설정으로 스위칭한다. 그러면 기계가 할 수 있는 다른 일은 무엇일까?

테이프를 읽는 헤드(head)라는 개념을 도입하여 헤드가 움직이면서 기호를 읽거나 쓰고 지우거나 옮긴다고 보아도 튜링의 개념에 위배되지 않는다.

튜링은 자신의 기계가 숫자를 계산할 수 있기를 원했기에 기계는 숫자를 출력할 수도 있어야 했다. 이를 위하여 기계는 테이프의 일부를 캐시 메모리로 사용한다.

튜링이 말한 숫자 계산이란 인간이 하는 숫자 계산을 뜻한다. 그러나 아직 이 기계가 덧셈을 하지 못한다고 생각할 수도 있다. 물론 튜링 기계에 덧셈 기능은 없다. 그러나 기계의 설정을 바꿈으로써 덧셈을 하도록 할 수 있다.

이제 우리는 사실상 전개되는 이론을 이해할 준비가 되었지만 튜링은 먼저 몇가지 정의를 소개한다.

§2 - Definitions✔

기계의 행동을 판별할 때 튜링은 가능한 행동들을 규명하려 했다. 기계의 행동은 자격을 획득해야 하는데, 이는 어떤 기계에서는 외부 연산인 인간의 상호작용에 의하여 기계의 행동이 바뀔 수도 있기 때문이다.

c-기계의 행동은 인간의 선택같은 외부 연산에 의하여 결정되므로 이러한 기계의 행동은 모호한 것이다. 튜링은 c-기계가 아니라 a-기계만을 다룰 것이기 때문이 접두사 a- 를 생략한다고 한 것이다.

튜링이 a-기계와 c-기계를 구분하는 것은 배치 프로세싱과 상호작용적인 컴퓨팅을 구분하는 것과 비슷하다. c-기계를 무시하는 이유는 c-기계가 튜링의 논문에서 하는 역할이 거의 없기 때문이다.

튜링은 기계를 만들기 전에 기계가 숫자 0 과 1 만을 출력한다는 제한을 걸었다. 이는 이진수의 사용을 위한 것이다. 이진수만 사용하는 것은 현명한 선택이지만 1937년대의 독자들에게는 왜 이렇게 하는지가 명백하지 않았다. 섀넌(1916-2001)은 1937년에 전자 회로와 불 대수의 동치를 보였다. 따라서 섀넌 정도 극소수의 인물만이 튜링의 선택의 진가를 알아보았을 것이다.

기계가 빈 테이프를 제공받으면 0 또는 1 과 다른 기호를 출력하는데 0 또는 1 이 계산된 수열을 구성한다. 튜링은 계산된 수열과 계산된 숫자를 구별했다.

이 문장을 쉽게 이해하기가 쉽지는 않은데 그 당시 사람들이 이진수에 익숙하지 않아서 튜링이 이렇게 쓸 수밖에 없었다. 이 문장은 이진수로 실수의 소수점을 표현한다는 것을 의미하고 있는데, 사실 오늘날 이진수에 익숙한 사람이더라도 이진수로 소수점을 표현하는 것이 완전히 편하지는 않다.

가령 \(.25, .5, .75\) 는 십진수로 소수점을 표현한 것이고 이것과 똑같은 이진수 소수점은 \(.01, .1, .11\) 이다. 이진수 소수점 \(.10101\) 의 의미는 다음과 같다.

또 다른 예시들은 다음과 같다.

이제 튜링의 설명을 다시 살펴보자. 가령 어떤 튜링 기계가 0 과 1 을 출력했다면 기계에 의하여 계산된 수열은 다음과 같다.

그리고 기계에 의하여 계산된 숫자는 수열을 소수점 자리에 붙여서 얻어진 실수이므로 다음과 같다.

이것으로 튜링은 설정(configuration)이라는 단어를 3번 사용했다.

1. m-설정은 기계의 상태 중 하나를 나타낸다.
2. 설정은 m-설정과 스캔된 기호의 쌍이다.
3. 완전한 설정은 그 시점의 기계의 전체 테이프의 스냅샷이다.

\(0\) 또는 \(1\) 을 출력하다가 어느 시점에서 멈춘다면 순환이다. 튜링은 이런 기계를 원치 않았다. 튜링은 그의 기계가 영원히 수를 출력하기를 원했다. 그러한 기계가 비순환 기계이다. 만약 기계가 \(\frac{1}{4}\) 를 이진수 형태로 출력할 수 있다면 \(0\) 과 \(1\) 을 출력하고 \(0\) 을 영원히 출력할 것이다.

"순환" 이라는 단어를 프로그램이 루프에 빠져서 탈출하지 못한다는 식의 부정적인 의미로 생각하면 된다. 그래서 튜링은 비순환 기계를 좋은 기계, 순환 기계를 나쁜 기계로 정의했다.

튜링이 명시적으로 언급하지는 않았지만 튜링 기계는 테이프를 왼쪽에서 오른쪽으로 써내려간다.

튜링은 수열과 수를 구별했다. 계산가능한 수열은 다음과 같다.

이에 따른 계산가능한 수는 다음과 같다.

다음과 같은 수를 생각하자.

이 수는 계산가능하다. 왜냐하면 기계에 의하여 계산된 수와 정수만큼 다르기 때문이다.

§3 - Examples of computing machines (튜링 기계)✔

튜링은 수학 논문에 가상의 기계를 소개하는 것이 참신하고 대담한 것임을 알고 있었다. 튜링은 몇가지 예시를 보여주었다.

이 기계의 테이프는 다음과 같이 출력된다.

그러나 튜링은 언제나 수열을 출력할 때 다음과 같이 한 칸씩 띄우는 것을 선호했다.

튜링은 m-설정을 표현하기 위하여 \(\mathfrak{b, c, k, e}\)(b, c, k, e) 와 같은 폰트를 사용했다.

P 에는 출력될 문자가 뒤따라 온다. 가령 P0 은 0 을 출력한다.

즉, 빈 테이프의 m-설정 \(\mathfrak{b}\) 를 만나면 0 을 출력하고 오른쪽으로 이동하고 m-설정 을 \(\mathfrak{c}\) 로 바꾸라는 것이다.

현재 헤드가 있는 곳을 굵은 박스로 표시하기로 하자.

임의의 빈 테이프에 m-설정 \(\mathfrak{b}\) 에서 기계가 시작되었다고 하자.

그러면 위와 같이 0 이 출력되고 다음에는 오른쪽으로 헤드를 옮기고 m-설정을 \(\mathfrak{c}\) 로 바꾼다.

m-설정이 \(\mathfrak{c}\) 이면 헤드를 오른쪽으로 옮기고 m-설정을 \(\mathfrak{e}\) 로 바꾼다.

m-설정이 \(\mathfrak{e}\) 이면 1 을 출력하고 헤드를 오른쪽으로 옮기고 m-설정을 \(\mathfrak{k}\) 로 바꾼다.

m-설정이 \(\mathfrak{k}\) 이면 헤드를 오른쪽으로 옮기고 m-설정을 \(\mathfrak{b}\) 로 바꾼다. 이로써 다시 \(\mathfrak{b}\) 에 도착하고 기계의 순환이 반복되면서 0 과 1 을 무한히 출력하게 된다.

이 기계가 다음과 같은 수열을 출력하고, 튜링은 이 수열이 계산가능한 수열임을 말했었다.

이 수열은 다음과 같은 계산가능한 수로 변환될 수 있다.

그러면 이 기계가 \(\frac{1}{3}\) 을 계산하는 기계임이 분명히 보일 것이다. \(1\) 부터 출력한다면 우리는 \(\frac{2}{3}\) 를 계산하는 기계를 만들어낸 것이다.

이렇게 \(0\) 과 \(1\) 을 출력하는 순서를 자유자재로 바꿀 수 있음을 알 수 있다. 그렇다면 우리는 튜링 기계가 임의의 유리수를 계산해낼 수 있다는 것을 깨닫게 된다.

일찍이 튜링은 이 기계가 스캔된 섹션을 왼쪽 또는 오른쪽으로 옮김으로써 스캔된 섹션도 바꿀 수 있다는 것을 언급했다. 그는 이것이 좀 더 유연해지길 원했다.

놀랍게도 이제 기계가 오직 하나의 m-설정 를 갖게 되었다. 이 표에 의하여 기계는 \(0\) 과 \(1\) 을 영원히 출력한다.

첫번째 기계에서 튜링은 이 기계로 임의의 유리수를 계산할 수 있음을 보였다. 이제 튜링의 관심사는 무리수였다. 그리고 더 나아가서 초월수까지 계산하려 했다. 지금 만들고자 하는 기계는 \(1\) 들이 \(0\) 에 의하여 분리되어 있고 계속해서 \(1\) 을 더 많이 출력하는 기계이다. 따라서 이 기계는 이전에 출력한 \(1\) 들의 개수를 기억하고 하나 더 많은 \(1\) 을 출력해야 한다.

즉, 튜링이 만든 기계는 다음과 같은 출력을 한다.

튜링은 중간 비어있는 섹션을 임시 저장소로 사용했다. 튜링은 나중에 숫자가 있는 섹션(figure)을 F-스퀘어로 부르고 기호가 있는 섹션(erasable)을 E-스퀘어로 불렀다.

다음은 튜링이 무리수를 계산하기 위하여 만든 기계 표이다.

기계는 m-설정 \(\mathfrak{b}\) 에서 시작하여 다음과 같이 테이프를 출력한다.

위 표에서 \(R, R\) 이나 \(L, L\) 이 나오는데 이는 숫자 섹션을 옮겨다니는 용도(\(\mathfrak{q, f}\))나 기호 섹션을 옮겨다니는 용도(\(\mathfrak{p}\))로 사용된다.

\(\mathfrak{b}\) 를 제외한 m-설정들은 스캔된 기호에 따라 자기 자신에게 되돌아오는 루프 기능을 한다.

\(\mathfrak{o}\) 가 \(0\) 을 만나면 아무 기능도 하지 않고 상태를 \(\mathfrak{q}\) 로 바꾼다. \(\mathfrak{q}\) 는 숫자를 만나지 않을 때까지 \(R, R\) 을 하고 비어있는 칸에 도달하면 \(1\) 을 출력한 뒤 왼쪽으로 한 칸 가고 상태를 \(\mathfrak{p}\) 로 바꾼다.

\(\mathfrak{p}\) 는 비어있는 칸을 만나면 비어있지 않은 칸을 만날 때까지 \(L, L\) 한다. 기계가 \(e\) 를 읽었으므로 \(R\) 한 다음 \(\mathfrak{f}\) 상태로 바꾼다.

\(\mathfrak{f}\) 는 비어있는 칸을 만날 때까지 \(R, R\) 하다가 비어있는 칸을 만나면 \(0\) 을 출력하고 \(L, L\) 한 다음 \(\mathfrak{o}\) 상태가 된다.

\(\mathfrak{o}\) 는 \(1\) 을 만나면 \(R\) 하고 \(x\) 를 출력하고 \(L, L, L\) 하고 \(\mathfrak{q}\) 가 된다.

\(\mathfrak{q}\) 가 실행되면 테이프가 다음과 같이 되고 \(\mathfrak{p}\) 로 바뀐다.

\(\mathfrak{p}\) 는 \(x\) 나 \(e\) 를 만날 때까지 \(L,L\) 하고 \(x\) 를 만나면 그것을 지우고 \(R\) 한 다음 \(\mathfrak{q}\) 가 된다.

\(\mathfrak{q}\) 는 빈칸이 나올 때까지 \(R,R\) 하고 \(1\) 을 출력하고 \(L\) 한 다음 \(\mathfrak{p}\) 가 된다.

\(\mathfrak{p}\) 는 \(e\) 를 만날 때까지 \(L,L\) 하고 \(R\) 하고 \(\mathfrak{f}\) 가 된다.

\(\mathfrak{f}\) 는 빈칸을 찾을 때까지 \(R,R\) 하고 \(0\) 를 출력하고 \(L,L\) 하고 \(\mathfrak{o}\) 가 된다.

그리고 계속 표의 작동을 보며 기계의 동작을 예측해보면 목표로 하던 수열을 기계가 영원히 출력한다는 것을 알 수 있다.

튜링이 표현한 기계의 모습✔

하지만 실제로 튜링은 논문에서 위와 같은 테이프 모양의 다이어그램을 보여주지 않았다. 튜링은 "임의의 단계에 있는 기계는 스캔된 스퀘어의 숫자, 테이프 위의 모든 기호의 완전한 수열, m-설정을 그 단계의 완전한 설정이라고 한다" 라고 했다. 튜링은 이 완전한 설정을 다음과 같은 방식으로 표기하려 했다.

 : e e 0   0 : e e 0   0 : e e 0   0 : e e 0   0   : e e 0    0   1 :
b      o           q               q              q             p

콜론들 가운데에 연속적인 테이프의 스냅샷이 들어가있다. 문자들 사이에 좀 더 넓은 빈 공간은 빈 테이프를 나타낸다. 아랫줄은 m-설정을 보여준다. m-설정의 폰트는 원래 \(\mathfrak{b, o, q, p, f}\) 이지만 편의상 b, o, q, p, f 로 나타내었다. m-설정 문자들의 위치는 헤드의 위치를 보여준다.

처음 \(\mathfrak{b}\) 설정이었을 때 테이프는 완전히 비어있고, 이 상황이 첫번째 스냅샷에 표현된다. 그 다음 \(\mathfrak{o}\) 설정일 때 테이프가 다음과 같은 모양이 되는데, 이 상황이 두번째 스냅샷에서 표현된다.

그리고 그 다음 스냅샷들은 기계의 그 다음 진행상황을 차근차근 보여준다.

튜링은 두줄로 표현되어 있는 이 표현법을 한 줄로 표현하는 방법을 제시했다.

b : e e o 0   0 : e e q 0   0 : ...

튜링은 이 형식을 설정(configuration)을 뜻하는 C 형식이라고 불렀다.

덧셈과 곱셉✔

이 튜링 머신으로 덧셈과 곱셈 기계를 만들 수 있다. 논문에는 덧셈과 곱셈 기계의 설계도를 보여주지만 여기에서는 생략하고 빠르게 넘어간다.

서브루틴✔

그리고 자주 사용되는 m-설정을 서브루틴으로 만들어서 사용할 수도 있다. 이 서브루틴을 수학에서의 함수처럼 만들어서 파라미터를 받아서 기능을 정의할 수 있다. 이 서브루틴이 현대의 프로그래밍의 함수나 메소드로 나타난다. 튜링은 이러한 서브루틴을 m-함수라고 하지 않고 스켈레톤 테이플(skeleton table)이라고 불렀다. 그리고 스켈레톤 테이블을 사용하는 기계 표를 축약된 표(abbreviated table)라고 했다.

튜링은 보편 기계을 만들기 위하여 여러가지 서브루틴을 정의해두었다. 가령 테이프의 특정 문자를 검색하고 치환하는 서브루틴을 만들어놓았다.

§5 - Enumeration of computable sequences (모든 것이 수이다)✔

현대에는 이미 텍스트, 그림, 사진, 소리, 음악, 영화 등이 모두 디지털화 가능하다. 그러나 1930년대에는 아니었다. 하지만 튜링은 2차 대전 때 텍스트를 암호화하기 위하여 이진수로 변환하고 매우 큰 수를 곱했다. 그러면 인수분해가 어렵기 때문에 텍스트를 암호화할 수 있었다. 튜링은 이 과정을 자동화하는 기계를 만들었다.

튜링은 사진과 음악 뿐만 아니라 기계 그 자체도 수로 나타낼 수 있음을 보였다. 모든 것은 수였다. 튜링 머신도 수였다.

만약 다음과 같은 m-설정들이 있다고 하자. 모든 기계의 m-설정은 다음과 같이 문자 하나를 출력하고 \(L\) 또는 \(R\) 을 하는 원초적인 형태로 분해 가능하다.

m-설정들에 수를 부여하면 이 표는 다음과 같이 된다.

만약 기계가 237개의 m-설정을 가지면 이것들은 \(q_1\) 부터 \(q _{237}\) 을 부여받는다.

그러면 위 기계는 다시 다음과 같아진다.

표준형✔

일반적인 경우 튜링은 다음과 같은 세가지 표준형을 보였다.

지우는 연산이 없다고 생각할 수 있는데, \(S_0\) 를 빈칸으로 정의했으므로 이것을 출력하는 것이 지우는 연산이 된다. 단순히 \(L\) 이나 \(R\) 하는 연산은 테이프에 있는 기호를 재출력하고 \(L\) 이나 \(R\) 하는 것으로 이루어진다. 그렇다면 우리의 기계는 이제 표준형을 따라 다음과 같게 된다.

이제 표 대신 각 설정을 m-설정, 기호, \(L\) 과 \(R\) 의 조합으로 표현할 수 있다.

튜링은 헤드가 움직이지 않는 경우를 No 를 뜻하는 \(N\) 으로 표현한 것이다.

그리고 이러한 형태를 5가지 원소로 구성된 퀸튜플(quintuple)이라고 한다.

표준 표현(S.D)✔

이제 기계를 퀸튜플의 나열로 표현할 수 있다. 이때 퀸튜플의 순서는 상관없다. m-설정표에서 m-설정들의 순서를 바꿔도 상관없는 것처럼 말이다.

그러면 이제 \(q_5\) 는 \(DAAAAA\) 가 되고, \(S_2\) 는 \(DCC\) 가 된다.

표현수(D.N): 기계 → 수✔

튜링은 의심할 여지 없이 괴델의 불완전성 정리에서 정리들을 유일한 정수로 변환하는 것에 착안하여 이렇게 한 것이다.

퀸튜플의 순서가 상관없기 때문에 여러개의 D.N 이 하나의 계산가능한 수열을 출력하는 기계를 정의할 수 있는 것이다.

우리는 단순히 가능한 모든 경우의 수를 따져가며 계산가능한 수열을 나열할 수 있다. 왜냐하면 이것이 단지 정수이기 때문이다.

튜링이 언급하지 않은 함의는 단지 계산가능한 수가 열거가능한 실수의 부분집합이라는 것이다.

튜링이 논문에서 언급한 \(\S 3\) 의 기계 \(\text{I}\) 는 우리가 이미 살펴본 0 과 1 을 영원히 출력하는 다음과 같은 기계이다.

이것은 절대 실행되지 않는 m-설정을 추가하여 똑같은 계산가능한 수열을 출력하는 다른 표를 얻을 수 있다는 것이다.

튜링은 D.N 은 S.D 보다 자주 사용하지 않았다. 튜링은 D.N 을 단지 추상적 개념으로 여겼고 그것을 굳이 계산해 보이지는 않았다. 하지만 튜링은 예시를 위하여 S.D 를 D.N 으로 치환해보였다.

두번째 줄은 실행되지 않는 관계 없는 m-설정을 추가한 표이다. 마지막에 \(31323253117\) 이 추가되었을 뿐이다. 이 두 기계가 다른 기계를 정의하지만 정확히 같은 수를 계산한다.

다음과 같은 무한수열을 가지는 \(\pi\) 를 계산하는 기계를 생각하자.

그러면 우리는 튜링 기계의 D.N 으로 \(\pi\) 를 유한한 정수로 표현할 수 있다. D.N 이 \(\pi\) 를 계산하는 알고리즘을 표현하므로 \(\pi\) 를 저렇게 무한소수로 표현하는 것보다 D.N 이 더욱 근본적인 수 표현이다.

튜링은 정수를 나열함으로써 기계를 생성하려 했다. 물론 모든 정수가 유효한 D.N 이 아니고, 많은 D.N 이 비순환 기계를 나타내지 않지만, 이 나열은 명백히 각각 계산가능한 수로 대응되는 모든 비순환 튜링 기계를 포함했다. 그러므로 계산가능한 수는 열거가능하다.

현대의 프로그래머에게 컴퓨터 프로그램이 수라는 것은 익숙하다. 왜냐하면 그것은 단지 바이트의 나열이고, 단일 정수로 나타내어질 수 있기 때문이다. 가령, 배틀그라운드라는 FPS 게임 프로그램도 단일 정수로 변환 가능하다. 그 수가 무지막지하게 크겠지만 어쨌든 유한하다. 그리고 모든 유효한 튜링 기계 집합에 포함되어 있다.

만족수✔

특정 정수가 유효한 D.N 임을 결정하는 절차는 존재하지만, 튜링은 특정 D.N 이 비순환 기계를 표현하는지 결정하는 일반적인 절차는 존재하지 않음을 밝혔다.

그러므로 일반적으로, 프로그램이 무한루프에 빠지거나, 크래시가 난다거나, 이상하게 꼬여버린다는 것을 결정할 절차도 존재하지 않는다.

§6 - The universal computing machine (보편 기계)✔

보편 기계(Universal Machine)는 다른 기계의 S.D 가 주어지면 그 기계를 흉내낼 수 있는 튜링 기계이다. 현대에는 보편 기계를 프로그래밍 가능(programmable)하다고 한다. 보편 기계의 물리적 구현체가 컴퓨터이다.

지금까지의 튜링 기계는 입력을 받고 단지 m-설정에 따라 수열을 출력했지만 보편 기계는 어떤 기계의 S.D 를 입력받아서 그 기계가 출력하는 수열을 그대로 출력한다.

하지만 이것은 러프한 설명이다. 실은 일반적으로 보편 기계가 어떤 기계를 완벽하게 그대로 흉내낼 수는 없다. 튜링 기계는 일반적으로 빈 테이프로 시작하지만, 보편 기계는 빈 테이프가 주어지지 않는다. 보편 기계에는 이미 S.D 가 주어져있기 때문이다. 그래서 만약 어떤 기계가 튜링의 관습대로 단방향으로만 출력하는 것이 아니라 양방향으로 출력한다면 어떻게 되겠는가? 보편기계에 주어진 S.D 는 출력에 의해 덮여쓰여질 것이다.

(BOF 같은 해킹의 원리는 이렇게 컴퓨터의 본질적인 구조의 문제에서 비롯된 것이다. 그런데 더 곤란한 문제는 이 논의는 튜링 기계의 설정표가 계산 테이프와 독립적인 공간에 격리되어 있다고 암묵적으로 상정하고 있는데, 실제 컴퓨터는 데이터 뿐만 아니라 프로그램까지 메모리에 함께 올려서 실행하게 된다. 이는 보편 기계가 주어진 기계의 실행규칙을 덮어쓸 수 있을뿐만 아니라 자기 자신의 실행규칙까지도 덮어 쓸 수 있다는 것이다. 그러면 해킹가능성은 튜링이 설계한 컴퓨터의 본질적인 구조에서 비롯되므로 구조적으로 해결할 수 없는 문제일까?)

튜링은 보편기계가 어떤 기계의 S.D 로 시작하는 테이프를 가진다고 말한다. 만약 테이프가 양방향으로 무한하다면 시작이 존재하지 않을 것이다. 튜링은 암묵적으로 보편기계의 출력을 S.D 이후의 빈 테이프로 제한했다. 실제로 보편기계는 실질적 출력을 위한 출력 공간을 필요로 한다. 따라서 그것의 출력은 그것이 흉내내려는 기계의 출력과 달라질 것이 뻔하다. 사실 튜링은 틀리게 말한 적이 없다. 튜링은 보편기계가 그것이 흉내내려는 기계의 출력을 정확하게 복제해낸다고 보장한 적이 없다. 튜링은 단지 "보편기계가 주어진 기계와 같은 수열을 계산한다" 라고만 말했을 뿐이다. 그리고 실제로 보편기계는 그 수열을 출력할 뿐만 아니라 다른 추가적인 것들도 많이 출력한다.

튜링이 컴퓨터를 설계하기 시작했다.

완전한 설정이란 연산이 완료된 이후의 테이프, 헤드의 위치, 다음 m-설정을 포함하는 스냅샷이다. 그러므로 연속적인 완전한 설정은 기계의 연산의 모든 진행과정을 보여준다.

튜링이 논문에서 언급한 p. 235 에서의 C 형태란 튜링이 표현한 기계의 모습에서 기계의 연속적인 스냅샷들을 다음과 같은 형태로 표현한 것이다.

b : e e o 0   0 : e e q 0   0 : ...

괄호 안의 언급은 \(\mathcal{M}'\) 의 출력에 관한 것이다. \(\mathcal{M}\) 은 F-스퀘어에 단지 0 과 1 을 출력하고 E-스퀘어는 0 과 1 을 계산하기 위한 보조 기호들을 출력하는데에 사용한다. \(\mathcal{M}'\) 은 \(\mathcal{M}\) 의 연속적 완전한 설정을 F-스퀘어에 출력하고 E-스퀘어는 이 작업을 보조하기 위하여 사용한다.

\(\mathcal{M}\) 의 S.D 를 \(\mathcal{M}'\) 의 내부 어딘가에 작성해놓는다는 \(\mathcal{M}'\) 의 아이디어는 완전히 새로운 개념이었다. 도대체 어디에 작성해놓을 것인가? 그리고 그것에 어떻게 접근할 것인가? 비록 이것이 \(\mathcal{M}'\) 을 설계할 수 있는 합리적인 방식이었지만, 튜링은 이러한 방식으로 자신의 목적을 훼방하는 \(\mathcal{M}'\) 을 추구했다.

튜링은 보편기계가 기계의 S.D 를 받는다고 말했다. 그것이 "꺼내져서 다른 것으로 바꾸어질 수 있는 것" 의 뜻이다. 즉, 우리는 보편기계에 우리가 실행하고 싶은 기계의 S.D 가 담긴 테이프를 주면 되는 것이다. 보편기계가 기계의 S.D 를 받으면 그것의 연속적 완전한 설정을 출력해야 한다.

이것이 가능한 이유는 S.D 와 연속적 완전한 설정이 같은 방식으로 인코딩 되어 있기 때문이다. 보편기계가 다음과 같은 완전한 설정을 출력했다고 해보자.

이것은 다음 m-설정이 \(q_3\) 이고 다음 스캔된 기호가 \(1\) 이라는 것을 뜻한다. S.D 에는 이 패턴과 매칭되는 문자들이 있다. 만약 없으면 이 기계는 비순환이 아닌 것이다. 보편기계가 할 일은 패턴을 매칭시켜서 다음 설정을 찾는 것이다. 그리고 다시 그 설정에 정의된 동작대로 완전한 설정을 출력해내는 것이다. 첫번째 완전한 설정을 출력하면, 그 설정을 기반으로 다음 완전한 설정을 출력해내는 식이다. 보편 기계의 입장에서 이것은 단순히 비교하고 기호를 복사하는 일에 불과하다.

실제로 \(\mathcal{M}'\) 은 \(\mathcal{M}\) 의 연속적 완전한 설정을 F-스퀘어에 \(A, C, D, :\) 으로 출력했을 뿐이고, E-스퀘어는 임시메모장으로 사용하고 있다. 진정한 목적은 수 \(0\) 과 \(1\) 을 출력해내는 것이다.

이제 \(\mathcal{M}'\) 이 수를 출력하기 시작하는데, 이 수들이 연속적 완전한 설정들 사이에 출력되었다는 것을 제외하면 \(\mathcal{M}\) 이 출력하는 수들과 똑같다. \(0:\) 이 두번 반복되는데 이것은 첫번째 완전한 설정이 동작했을 때 출력되는 수들을 뜻한다.

튜링은 이 기계 \(\mathcal{M}'\) 을 보편기계 \(\mathcal{U}\) 라고 상정하고 있었다. 이제부터 \(\mathcal{M}'\) 을 \(\mathcal{U}\) 로 표기하자.

한편 보편기계가 이렇게 작동되어야 하므로 튜링은 지금까지 수들이 출력되면 그것이 절대 바뀌지 않도록 설계한 것이다.

§7 - 보편기계의 설계도✔

튜링은 이 보편 기계가 실제로 존재한다는 것을 보이기 위하여 보편 기계의 m-설정 표를 직접 만들어서 보여주었다.

튜링이 논문의 챕터 7 에서 보편 기계의 실제 설계도를 보여줌으로써 보편 기계의 존재성을 증명했지만, 여기에서는 생략한다.

그런데 보편 기계에는 한계가 있었다. 보편 기계는 임의의 일반적인 튜링 기계를 실행할 수 없었기 때문이다. 보편 기계는 자신의 헤드를 초기 위치에서 왼쪽으로 임의의 위치로 움직이는 기계를 실행해야 할 때, 완전한 설정의 왼쪽에 빈칸을 삽입해야 하므로, 제대로 작동하지 않았다. 보편 기계는 단지 빈칸을 \(0\) 이나 \(1\) 로 바꾸거나 오른쪽 방향으로 향하는 동작을 가진 기계만 제대로 실행할 수 있었다. 물론 보편 기계는 이렇게 동작하지 않는 기계를 실행할 수 있기는 했지만 그렇게 했을 때 올바른 \(0\) 과 \(1\) 의 수열이 출력되지 않았다.

물론 이러한 한계와 몇 가지 버그와 잘못된 출력에도 불구하고 튜링은 꽤 훌륭한 무언가를 만든 것이었다. 그는 단일 보편 기계가 임의의 계산 기계의 연산을 수행하도록 프로그래밍된다는 것을 보임으로써 계산의 일반성을 증명했다. 혹자는 튜링이 보편 기계의 존재성을 증명한 이 정리가 지난 세기의 지성의 랜드마크 중 하나라고 말했다.

그렇다면 튜링은 컴퓨터를 발명한 것인가?

컴퓨터가 구현되기 시작하다✔

거의 아무것도 하지 않는 계산기계를 상상함으로써 튜링은 거의 다목적 컴퓨터(계산 기계)를 생각해내었다. 이것은 혁명이었다. 왜냐하면 그때까지만 해도 컴퓨터란 특정 목적을 위하여 설계되어야 한다는 생각이 지배적이었기 때문이다. 이때 당시 개발된 최신 컴퓨터는 1920년대에 MIT 교수 버니바 부시가 만든 미분 해석기였다. 미분 해석기가 미분 방정식을 풀었기에 당시 최첨단 컴퓨터였지만, 그것이 다였다. 이 계산 기계는 다른 것은 전혀 계산하지 못했다.

디지털 컴퓨터를 설계하는데 깊게 관여한 사람들일지라도 디지털 논리의 일반성을 파악하지 못했다. 가령 컴퓨터의 선구자인 Howard Aiken 도 다음과 같이 말했다.

튜링의 상황은 좀 더 나았다. 당대의 대부분의 컴퓨터 설계자들이 하드웨어에 집중한 반면 튜링은 소프트웨어를 썼다. 튜링은 덧셈같은 기본 산술 연산도 소프트웨어적으로 얻어질 수 있었다. 튜링은 이렇게 말했다.

누군가는 속도가 컴퓨터의 모든 것이 아니라고 말하겠지만, 사실은, 속도는 모든 것이다. 사람들이 컴퓨터 설계를 고려할 때는 언제나 최우선의 고려사항은 속도였고, 그에 따른 시간이었고, 그에 따른 돈이었다.

튜링과 폰 노이만이 만났을 때 폰 노이만은 튜링에게 괴델의 불완전성 정리 때문에 수리논리학에 관련된 논문을 그만 읽으라고 말했었다. 둘의 대화 주제는 주로 계산가능성이 아니라 주기함수와 군론이었다. 이후에 폰 노이만은 튜링의 논문을 읽었고 튜링의 아이디어를 극찬했다.

폰 노이만이 펜실베니아 대학교에 갔을 때 컴퓨터 에니악이 만들어지고 있었다. 에니악의 한계가 명백해보이자 곧바로 후속작인 에드박이 계획되었다. 폰 노이만은 에드박의 기술 회의에 참여했고 논리 설계에 대한 아이디어를 제공해주었다. 1945년 폰 노이만은 에드박에 대한 설계도 "First Draft of a Report on the EDVAC" 를 완성했다. 이 설계도는 중요한 개념을 지니고 있었다.

폰 노이만에 따르면 컴퓨터는 반드시 이진수를 기반으로 작동하는 전자공학물이어야 하고, 프로그램을 메모리에 저장할 수 있어야 한다. 그러나 이것이 순수한 폰 노이만의 아이디어였는지 그곳 사람들 사이에 널리 퍼져있던 아이디어를 정립한 것인지는 분명하지 않다. 하지만 수년 후 사람들은 이 구조를 폰 노이만 구조라고 부르기 시작했다.

그는 에드박 설계도에 한 레퍼런스를 달아놓았는데, 그것은 "A Logical Calculus of the Ideas Immanent in Nervous Activity" 였다. 이것은 폰 노이만이 컴퓨터와 인간의 뇌의 관계에 흥미를 갖고 있었다는 것을 보여준다. 그런데 재밌는 점은 이 논문의 저자도 그의 뇌에 대한 생리학적 개념을 튜링 머신에 두고 있었다는 것이다. 폰 노이만과 일했던 물리학자는 그가 튜링의 논문에 대하여 열광했었다고 말했다. 사람들이 컴퓨터의 아버지를 폰 노이만이라고 말했지만, 폰 노이만은 자신의 개념의 근본이 튜링에 있었음을 알고 있었고, 따라서 폰 노이만은 사실상 튜링의 개념을 사람들에게 널리 알린 것이었다. 실제로 폰 노이만은 주변 사람들에게 튜링의 지대한 공헌, 특히 결정적 기계가 보편적일 수 있다는 공헌을 알리려 했다.

튜링은 자신의 설정표를 스스로 개선해나갈 수 있는 기계라면 그 기계가 자신의 선생으로부터나 자신의 행동의 결과로부터 학습하는 학생과 같은 지능을 보이는 것이라고 말했다.¹

튜링은 프로그래밍을 디지털 컴퓨터가 사람의 뜻을 행할 수 있게 만드는 것이라고 말했다.

§8 - Application of the diagonal process (계산가능성)✔

튜링도 컴퓨터를 물리적으로 실제로 구현하는 프로젝트에 참여했지만, 튜링은 Entscheidungsproblem 를 해결하기 위하여 이론적 컴퓨터를 만든 것이었다. 아직 몇 단계가 더 남아있는데, 핵심적인 것은 튜링 기계가 본질적으로 무엇을 할 수 없는지 규명하는 것이다.

이 섹션에서는 튜링 기계의 궁극적 운명을 미리 판단할 수 있는 튜링 기계가 존재하지 않는다는 것을 보일 것이다.

계산가능한 수 집합은 매우 크고 실수와 비슷하지만 열거가능하다. 튜링은 이것을 각 계산가능한 수열이 최소한 하나의 D.N 으로 대응되고, D.N 에는 하나 이상의 계산 가능한 수열이 대응되지 않는다는 것으로 증명했다. 하지만 계산가능한 수에는 초월수도 포함된다.

그런데 거의 모든 초월수는 겉으로 보기에 무작위 수의 나열이다. 실수의 영역에서는 질서있는 수를 찾아보기가 힘들다. 우리가 어떻게 패턴이 없는 수를 기계로 계산할 수 있고, 완전한 무작위 수를 출력할 수 있을까?

컴퓨터는 실제 난수를 출력하는 것이 아니라 시간을 기반으로 유사 난수를 출력할 수 있을 뿐이다. 왜냐하면 컴퓨터가 수행하는 산술적 계산은 완전히 결정적이기 때문이다. 가령, C 언어의 rand 함수는 \(0\) 부터 \(32,767\) 사이의 난수를 출력한다. rand 는 시드(seed)라는 수에서 출발하는데, 시드는 기본적으로 \(1\) 로 초기화되어 있다. C 언어 구현에 따라 알고리즘이 다를 수 있지만 마이크로소프트의 C²⁷에서 rand 는 다음과 같이 구현된다.

int seed = 1;

int rand()
{
    return ((seed = seed * 214013 + 2541011) >> 16) & 32767;
}

rand 는 시드에 \(214,013\) 을 곱하고 \(2,531,011\) 을 더하고 그것을 시드에 다시 저장한다. 하지만 시드가 32비트 signed integer 형이기 때문에, 오버플로우나 언더플로우가 발생할 수도 있다. 리턴값은 32비트에 맞게 잘려나가고, 가장 높은 비트가 \(1\) 이면, 그 값은 실제로 음수가 된다. 계산된 값은 \(65,536 = 2 ^{16}\) 으로 효과적으로 나누기 위하여 오른쪽으로 16비트 쉬프트된다. 마지막으로 \(32,767\) 와 AND 연산이 되어 리턴값이 \(0\) 과 \(32,767\) 사이에만 존재하도록 한다.

이 함수는 완전히 결정적이다. rand 함수로 난수를 출력해보면 다음을 얻는다.

41
18,467
6,334
...

하지만 시드를 현재 시각으로 초기화하여 유사 난수를 얻을 수 있다.

결정적인 연산으로부터 결정되지 않은 무작위 수는 나올 수 없다. 대부분의 프로그램은 유사 난수로도 충분한 목적이 달성되지만, 종종 진짜 난수가 필요한 프로그램들이 있다. 이 경우에는 주변 환경의 데이터를 수집하거나 양자적인 과정을 통하여 진짜 난수를 출력해주는 하드웨어(RNG, random number generator)의 지원을 받아서 컴퓨터에 진짜 난수를 입력해주어야 한다.

RNG 가 출력한 진짜 난수와 똑같은 실수를 출력하는 튜링 기계를 만드는 것은 불가능하다. RNG 를 흉내내는 유일한 방법은 그 숫자들을 정확하게 똑같이 출력하는 것 뿐인데, 이렇게 하면 튜링 기계는 유한한 설정을 가질 수 없다.

어쩌면 실수의 무작위성은 환상일지도 모른다. 실제로 우리는 \(\pi\) 의 소수점을 보고 그것이 무작위라고 생각했었지만, 결국 그것의 규칙성을 찾아내었다. 이처럼 실수는 우리가 아직 완전히 밝혀내지 못한 어떠한 구조를 기반으로 소수점을 가질지도 모른다. 그래서 우리가 만약 관점을 약간 바꾼다면 계산가능한 수가 열거가능하지 않다고 생각할 수도 있다. 즉, 계산가능한 수 집합을 실수 집합처럼 비가산 집합으로 생각할 수도 있는 것이다.

튜링은 먼저 이러한 가능성을 피하지 않고 대면했다.

이로써 튜링은 칸토어가 실수의 열거불가능성을 증명하기 위하여 사용했던 대각선 논법을 암시했다. 튜링은 실수에 적용되었던 칸토어의 대각선 논법을 계산가능한 수에 적용했다. 두 경우 모두 수는 극한에 도달하는데, 칸토어의 증명에서 그 극한은 실수이지만, 칸토어는 그 극한이 열거가능한 실수에 들어가 있지 않음을 보임으로써, 실수가 열거가능하지 않다는 것을 증명했다. 계산가능한 수의 경우에도 우리는 어떤 극한에 도달한다. 그런데 그 극한 또한 계산가능한 수일까?

튜링은 극한에 도달하는 수열 \(\alpha\) 와 \(\beta\) 를 생각했다. 극한이 계산가능한 수가 되려면 수열을 극한까지 계산할 수 있어야 한다. 즉, 우리는 이 알파와 베타에 의하여 접근되는 극한을 말해주는 일종의 알고리즘을 고안할 수 있다. 하지만 그럴 수 있을 것 같지 않다. 우리가 이 수열의 극한을 계산할 수 없으면 그것은 계산가능한 수가 아니다. 그것은 계산불가능한 실수이고, 그러므로 계산가능한 수가 열거가능하다는 반증을 아직 하지 못한다.

계산가능한 수열은 \(0\) 과 \(1\) 의 반복이고, 이것은 \(\phi\) 로 표현된다. 따라서 다음과 같이 표현된다.

\(\beta\) 는 다음과 같다.

즉, 어떤 \(K\) 에 대하여 다음을 만족하는 계산가능한 수열 \(\alpha_K\) 가 존재한다는 것이다.

\(n\) 에 대하여 \(1 - \phi _n(n) = \phi _K(n)\) 이므로 다음이 성립한다.

이제 튜링은 \(\beta\) 가 존재하지 않음을 보이기 위하여 다음을 사용했다.

즉, 다음과 같이 된다.

하지만 튜링은 침착하게 이렇게 말했다.

하지만 \(\beta\) 가 열거가능한 계산가능한 수열로부터 계산되었으므로 이것은 계산가능하지 않을까? 실제로는 그렇지 않다. 튜링은 계산가능한 수를 유한한 방법으로 계산할 수 있는 것으로 정의했었다. 그는 이런 수들을 계산할 수 있는 상상의 기계를 만들고 각 기계들이 D.N 이라는 양의 정수로 유일하게 특정된다는 것을 증명했다. 정수가 열거가능하므로 튜링 기계도 열거가능하며, 따라서 계산가능한 수열도 열거가능하다.

이 관점에서 튜링 기계의 열거는 다음과 같이 정수를 열거하는 것만큼 쉽다.

모든 튜링 기계는 위와 같은 D.N 의 목록에 다 포함되어 있고, 이 D.N 에서 S.D 를 얻을 수 있고, 이로써 우리는 이 S.D 를 보편 기계에 입력하여 계산가능한 수열을 얻을 수 있다.

물론 우리는 이 리스트에서 어떤 수가 비순환 기계의 D.N 인지 결정하는 방법은 마련하지 않았다.

비순환 기계는 \(0\) 과 \(1\) 을 영원히 출력하는 기계이다. 이 기계가 통제를 벗어나는 것처럼 보여도 이 기계는 무리수를 계산할 때 필요하고 수가 반복되는 유리수를 계산할 때 필요하다. 심지어 유리수 \(.1 = \frac{1}{2}\) 를 다음과 같이 출력하기 위하여 비순환 기계가 필요하다.

순환 기계는 원치 않는 루프에 빠지는 기계이다. 가령 이런 기계는 헤드를 더 이상 움직이지 않으면서 영원히 \(0\) 을 출력할 수도 있다. 비순환 기계는 자신에게 주어진 영원함을 \(0\) 또는 \(1\) 을 출력하는 루프에 사용하지만, 순환 기계는 존재하지 않는 m-설정에 빠질 수도 있다. 우리는 비순환 기계의 D.N 을 규명해야 하는데, 왜냐하면 그것만이 보편기계에 입력될 자격이 있기 때문이다. 우리는 모든 튜링 기계를 나열했지만 아직 그것이 비순환 기계인지 규명하지는 못했고, 따라서 우리는 그것을 계산가능한 수열을 생성하는데에 사용할 수 없다.

많은 정수가 임의의 기계의 D.N 이 아니라는 것이 자명하다. 우리는 쉽게 특정 정수가 well-formed D.N 인지 결정할 수 있다. 우리는 기계가 존재하지 않는 m-설정을 참조하는지도 결정할 수 있다. 또한 특정 m-설정이 사용되는지도 결정할 수 있다. 임의의 m-설정이 실제로 \(0\) 이나 \(1\) 을 출력하는 연산을 포함하는지도 확인할 수 있다. 이런 절차는 가장 작은 D.N 이 \(31,334,317\) 이라는 것을 말해주고, 이것이 순환 기계라는 것을 말해준다. 이 기계는 빈 칸만 출력한다. \(313,324,317\) 은 첫번째 비순환 기계이고, \(313,325,317\) 은 첫번째로 왼쪽에서 오른쪽으로 출력하는 비순환 기계이다.

단순한 기계들을 규명하는 것은 단순하지만 일반적으로 특정 정수가 비순환 기계의 D.N 인지 결정하는 절차는 존재하지 않는다. 하지만 이 일반적 절차가 대각화를 수행하기 위하여 필요한 것이다.

\(\beta\) 의 각 수는 각기 다른 계산가능한 수에 기반을 두고 있으므로 \(\beta\) 를 계산하기 위해서는 모든 비순환 기계를 규명하는 것이 필요하다. 튜링은 이 비순환 기계들이 유한한 방법으로는 규명될 수 없다는 것을 증명했다. 즉, 우리가 튜링 기계가 비순환인지 확인하려면 해당 기계를 개별적으로 확인해볼 수밖에 없다. 하지만 이 방법은 유한한 절차로 이루어지지 않는다. 이는 우리가 명시적으로 계산가능한 수열을 열거할 수 없다는 것을 뜻한다. 따라서 \(\beta\) 는 계산가능한 수열이 아니다. 쉽게 말해, \(\beta\) 를 유한한 절차로 계산할 기계는 없다. \(\beta\) 를 계산해내려면 \(\beta\) 의 무한한 각 자릿수에 해당하는 계산가능한 수열에서 매번 수를 추출해와야 한다. 이 과정은 유한하지 않다.

튜링은 칸토어의 대각선논법을 계산가능한 수열에 적용하기 시작했지만, 그는 우리가 비순환 기계의 모든 D.N 을 규명하려 할 때 무슨일이 일어나는지 조사하기를 원한 것이었다.

특정 정수가 비순환 기계의 D.N 인지 결정하는 일반적 절차가 존재하지 않으면, \(\beta\) 는 계산불가능한 수인 것이다. 이것이 증명되면 계산가능한 수열이 열거가능하지 않다는 증명도 무효화된다. 그러면 이로써 우리는 계산가능한 수열이 열거가능하다는 증거를 얻는다.

튜링은 특정 기계가 비순환인지 결정하는 일반적 절차에 대하여 말한 것이다. 만약 그것이 존재한다면 \(\beta\) 를 계산할 수 있게 되기 때문이다. 하지만 \(\beta\) 가 계산될 수 있으면, 대각선 논법을 통하여 계산가능한 수열이 열거가능하지 않는 결론이 나온다.

튜링은 이제 특정 정수가 비순환 기계의 D.N 인지 결정하는 기계가 존재하지 않음을 보이려 했다. 튜링이 먼저 원하는 기계는 계산가능한 수열에서 수 하나를 추출하는 기계였다.

튜링은 일찍이 계산가능한 수가 모든 정의가능한 수를 포함하지 않고, 그 예시로써 계산불가능한 정의가능한 수가 있다고 말했다. \(\beta\) 나 \(\beta '\) 은 정의가능하다. \(\beta '\) 이 정의 가능한 것은 그것을 계산하는 절차를 정의할 수 있기 때문이다. 1 부터 모든 수를 나열하고, 각 수마다 튜링 기계의 well-formed D.N 인지 결정한다. 그리고 기계가 비순환인지 결정한다. 그리고 \(n\)까지의 수를 계산한다. \(n\)은 지금까지 만난 비순환 기계의 수보다 하나 더 큰 수이다. 그 수는 \(\beta '\) 의 \(n\)번째 수이다.

그러므로 \(\beta '\) 은 정의 가능하다. 하지만 계산 가능한가?

Halting Problem✔

튜링이 기계를 종료하는 연산을 정의하지 않았지만, 튜링이 지금 해결하려는 문제는 정지 문제(halting problem)로도 알려져서 다양한 곳에서 연구되었다. 우리는 어떤 기계가 정지할지 영원히 실행될지 결정하는 기계를 만들 수 있는가? 정지라는 개념을 순환성(circularity)으로 바꾸면 문제는 간단해진다. 우리는 어떤 기계의 궁극적인 운명을 결정할 수 있는 튜링 기계를 만들 수 있는가?

튜링은 먼저 임의의 기계가 비순환인지 결정하는 기계가 존재한다고 가정한다. 튜링은 지금까지 D.N 을 사용했던 것과 달리 이번에는 S.D 를 사용하는데, 이것은 사소한 차이이다. S.D 를 D.N 으로 변환하는 것은 쉽기 때문이다.

\(\mathcal{D}\) 는 결정 기계(decision machine) 의 줄임말, \(u\) 는 불만족 기계(unsatisfactory) 의 줄임말, \(s\) 는 만족 기계(satisfactory)의 줄임말이다. 불만족스러운 기계는 순환 기계, 만족스러운 기계는 비순환 기계이다.

\(\mathcal{H}\) 에는 양의 정수를 생성하고 그것을 S.D 로 바꾸는 기능도 필요하다. 하지만 이것은 사소한 문제이다. \(\mathcal{H}\) 가 임의의 양의 정수를 만들면 \(\mathcal{D}\) 를 사용하여 그 수가 만족 기계인지 결정하면 된다. 그렇다면 \(\mathcal{H}\) 는 S.D 를 보편기계 \(\mathcal{U}\) 로 전달하고 수열을 계산한다. \(n\)번째 계산가능한 수열에 대하여 \(\mathcal{U}\) 는 단지 \(n\)번째 수까지 기계를 실행하면 된다. 그 수는 \(\beta '\) 의 \(n\)번째 수가 된다. \(\mathcal{U}\) 는 \(\mathcal{H}\) 의 통제 하에 있으므로 \(\mathcal{H}\) 는 \(\mathcal{U}\) 가 특정 자릿수를 출력했을 때 \(\mathcal{U}\) 를 멈출 수 있다.

\(\mathcal{H}\) 는 \(\mathcal{D}\) 의 S.D 를 검증해서 \(\mathcal{U}\) 가 불만족 기계를 실행하다가 stuck 되는 것을 방지해야 한다.

튜링은 마치 \(\mathcal{D}\) 가 존재하지 않는다는 것을 암시하는 것처럼, \(\mathcal{D}\) 의 실제 설계를 언급하는 것을 애써 피했다. \(\mathcal{D}\) 가 어떤 기계의 모든 연산 단계를 그대로 수행하는 방법을 제외하고, 어떻게 기계가 비순환인지 결정할 수 있을까?

\(\mathcal{D}\) 는 테이프에 S.D 를 인코딩하여 작동한다는 점에서 \(\mathcal{U}\) 와 비슷하다.

\(\mathcal{D}\) 는 판결로써 \(s\) 나 \(u\) 를 남길 것이다.

\(\mathcal{H}\) 는 양의 정수를 생성하여 그것을 \(\mathcal{D}\) 로 보내서 그것이 만족스러운지 판결하고, 그러하다면 \(\mathcal{U}\) 에 보내서 계산가능한 수의 특정 수까지 계산하게 한다.

\(R\) 은 그 시점까지 규명한 비순환 기계의 수를 축적한다. 기계는 몇번째 자리수까지 계산할지 판단하기 위하여 \(R\) 이 필요하다.

만약 \(N = 3,133,225,317\) 이면 이것이 두번째 비순환 기계의 D.N 이므로 \(R(N - 1) = 1\) 이 된다. \(\mathcal{D}\) 는 \(N\) 이 비순환 기계의 D.N 인지 판단할 것이고, 비순환 기계라고 판명날 것이기 때문에 \(R(N) = R(N - 1) + 1 = 1 + 1 = 2\) 가 될 것이다. 그러면 \(\mathcal{H}\) 는 이 D.N 을 \(\mathcal{U}\) 에게 보내서 두번째 자리수까지 계산가능한 수열을 계산시키고, 마지막 수를 가져와서 \(\beta '\) 의 두번째 자리수로 지정할 것이다.

물론 일반적인 경우 D.N 은 아예 기계가 아니거나 순환 기계이다.

이제 튜링은 \(\mathcal{H}\) 가 비순환 기계라는 것을 증명하려 했다. \(\mathcal{H}\) 는 단순히 잠재적 D.N 들을 \(\mathcal{D}\) 로 보내기만 하고, \(\mathcal{D}\) 는 가정에 의하여 비순환 기계이다.

그런데 \(\mathcal{H}\) 도 튜링 기계이므로 D.N 을 갖는다. 튜링은 이것을 특별히 \(K\) 라고 불렀다. 그렇다면 어느 시점에서 \(\mathcal{H}\) 는 자기 자신의 D.N 에 도착한다. \(\mathcal{H}\) 는 \(\mathcal{H}\) 가 비순환인지 판단해야 한다.

그리고 튜링은 덧붙혔다.

근본적인 문제는 \(\mathcal{H}\) 가 무한한 재귀에 빠진다는 것이다.

\(\mathcal{H}\) 가 \(K\) 에 도착하기 전에 \(\mathcal{H}\) 은 \(1\) 부터 \(K-1\) 까지의 수를 테스트했을 것이다. 그때까지의 비순환 기계의 수는 \(R(K-1)\) 이고 \(R(K-1)\) 만큼 \(\beta '\) 의 자리수가 규명되었을 것이다. 이제 \(\mathcal{H}\) 가 수행할 연산은 \(\beta '\) 의 \(R(K)\) 번째 자리의 수를 계산하는 것이다.

\(\mathcal{H}\) 는 자신의 D.N 인 \(K\) 를 \(\mathcal{U}\) 에게 보내서 \(\mathcal{H}\) 의 연산을 따라가며 \(R(K)\) 번째 자리수까지 계산하도록 시킬 것이다. 그런데 이것은 지금 \(\mathcal{H}\) 가 이미 수행하고 있는 일이다! \(\mathcal{U}\) 가 실행하는 \(\mathcal{H}\) 도 \(R(K-1)\) 자리까지 계산하겠지만 \(R(K)\) 를 계산하려 할 때 또 다시 \(\mathcal{U}\) 에게 \(\mathcal{H}\) 을 실행하라고 시킬 것이다. 이로써 \(\mathcal{H}\) 는 자기 자신을 무한히 실행하는 무한 재귀에 빠진다. 그러므로 \(\mathcal{H}\) 은 본질적으로 비순환일 수 없다.

결론✔

그러므로 기계가 비순환이라는 것을 결정할 일반적인 절차는 존재하지 않는다. 이것은 다른 컴퓨터 프로그램의 궁극적인 운명을 미리 판단할 수 있는 컴퓨터 프로그램은 존재할 수 없다는 것을 의미한다.

지금까지의 논의를 정리해보자. 계산가능한 수가 열거가능하지만, 대각선 논법은 그 리스트에 들어가지 않는 계산가능한 수를 생성해내는 것처럼 보였다. 하지만 대각선 논법에 의해 탄생한 수열은 유한한 방법으로 계산될 수 없으므로 계산가능하지 않다. 그러므로 계산가능한 수는 열거가능하지만, 유한한 절차로 열거될 수는 없다.

튜링이 \(\mathcal{E}\) 라는 기계를 정의한 이유는 나중에 우리가 궁극적으로 해결하려는 문제 Entscheidungsproblem 가 해답을 갖지 않는다는 것을 보일 때 필요하기 때문이다. \(\mathcal{E}\) 의 존재성은 기계가 \(0\) 을 무한히 출력할지 결정하는 절차의 존재성을 함의하는데, 이는 기계가 \(1\) 을 무한히 출력할지 결정하는 절차의 존재성도 보장해준다. 만약 어떤 기계가 \(0\) 을 무한히 출력할지, \(1\) 을 무한히 출력할지, 또는 그 둘 다 출력할지 결정할 수 있는 기계가 존재하면 우리는 그 기계를 사용하여 어떤 기계가 비순환인지 결정할 수 있다. 하지만 이것은 불가능하므로 \(\mathcal{E}\) 의 존재성도 부정된다.

\(\mathcal{M}\) 이 주어지면 \(\mathcal{M}\) 의 S.D 로부터 \(\mathcal{M}_1, \mathcal{M_2}, \dots\) 들의 S.D 를 생성해낼 수 있을까? 튜링은 가능하다고 말하고, 이 기계를 \(\mathcal{F}\) 라고 했다.

실제로 어떤 기계 \(\mathcal{M}\) 이 주어지면 m-설정표를 조금만 수정하여 쉽게 \(\mathcal{M}_1\) 과 \(\mathcal{M}_2\) 들을 만들 수 있다.

즉, \(\mathcal{G}\) 는 \(\mathcal{F}\) 를 사용하여 \(\mathcal{M}, \mathcal{M}_1, \mathcal{M}_2 \dots\) 의 S.D 를 생성하고, \(\mathcal{E}\) 는 그것을 받아서 기계가 \(0\) 를 출력할지 테스트한다. 기계가 \(0\) 을 출력하지 않으면 \(\mathcal{E}\) 는 \(0\) 을 출력한다.

\(\mathcal{M}\) 이 \(0\) 을 출력하지 않으면 \(\mathcal{M}_1, \mathcal{M}_2, \dots\) 들도 그러하다. \(\mathcal{M}\) 이 \(0\) 을 한번만 출력하면 \(\mathcal{M}_1, \mathcal{M}_2, \dots\) 들은 \(0\) 을 출력하지 않는다. \(\mathcal{M}\) 이 \(0\) 을 두 번 출력하면 \(\mathcal{M}_1\) 은 \(0\) 을 한 번 출력하고, \(\mathcal{M}_2\) 이후로는 \(0\) 을 출력하지 않는다. \(\mathcal{M}\) 이 \(0\) 을 무한히 출력하면 \(\mathcal{M}_1, \mathcal{M}_2, \dots\) 들도 그러하다.

\(\mathcal{M}\) 이 \(0\) 을 출력하지 않거나 유한한 수만큼 출력하면 \(\mathcal{G}\) 는 \(0\) 을 무한히 출력한다. \(\mathcal{M}\) 이 \(0\) 을 무한히 출력하는 경우에만 \(\mathcal{G}\) 는 \(0\) 을 출력하지 않는다.

튜링은 \(\mathcal{E}\) 의 존재성이 결국 \(\mathcal{D}\) 의 존재성을 함의한다는 것을 보임으로써 \(\mathcal{E}\) 이 존재하지 않음을 보였다.

튜링은 다음과 같이 말하며 이 장을 마무리하려 했다.

한편 튜링은 튜링 기계의 출력에 의미를 부여함으로써 기계가 좀 더 유연해진다는 것을 보여주었다. 가령 다음과 같은 수열을 출력하는 기계를 생각하자.

이 수열은 의미없어 보이지만 사실 소수를 출력하는 기계이다. \(n\)번째 수가 \(1\) 이면 \(n\) 이 소수라는 것이고 \(n\) 이 소수가 아니면 \(0\) 이다.

이 기계는 어떤 수를 계산하는 것이 아니라 자연수에 대한 사실을 말해주고 있다.

이제 튜링은 자신의 계산 기계를 수리논리학으로 연결 시키려 했다. \(1, 0\) 은 단순히 이진법 수로써 역할만 하는 것이 아니라 불이 깨달았던 것처럼 참과 거짓을 뜻하기도 했다.

소수를 출력하는 기계를 자연수 \(n\) 에 대하여 \(\text{IsPrime}(n)\) 이라는 불 함수(boolean function)로 정의할 수 있다. 또한 다음과 같은 기계들도 정의할 수 있다.

튜링은 계산가능한 수열이 열거가능하다는 것을 보였다. 그런데 이 함수들의 이름도 마찬가지이다. 가령, 이들은 알파벳순으로 정렬가능하다. 자연수에 대한 계산가능하고 알파벳순서화 될 수 있는 불 함수의 집합의 기수는 열거가능한 집합의 기수처럼 \(\aleph _0\) 이다.

각 불 함수는 자연수 부분집합에 대하여 \(1\) 인 부분집합을 반환하는 것이다. 가령 \(\text{IsPrime}(n)\) 은 다음을 리턴한다.

이렇게 각 불 함수들은 본질적으로 자연수의 부분집합이다. 자연수 부분집합의 기수는 \(2 ^{\aleph _0}\) 이므로 생각할 수 있는 모든 불 함수의 기수도 \(2 ^{\aleph _0}\) 이다. 물론 계산가능한 불 함수 집합의 기수는 \(\aleph _0\) 이다. 이처럼 계산 가능한 것과 생각할 수 있는 것에는 큰 차이가 있다.

§9 - The extent of the computable numbers (기계와 인간)✔

튜링은 계산가능한 수에 대하여 정의할 때 \(\S 9\) 에 도착할 때까지 계산가능한 수에 대한 정의가 정당화되지 않을 것이라고 말했다. 우리는 드디어 튜링의 논문의 9번째 챕터에 도달했다. Andrew Hodges 에 따르면 이 챕터는 수학 논문 중 가장 특이한 것 중 하나이다.

챕터 9 와 챕터 10 까지 튜링은 튜링 기계의 계산가능성이 인간의 계산가능성과 동등하다는 것을 설득하려 했다.

튜링은 튜링 기계의 능력이 잘 정의된 수학적 과정을 수행하는 인간 컴퓨터의 능력과 동등하다는 것을 보이려 했다. 이것은 튜링 기계에 의해 해결 불가능한 알고리즘은 인간에 의해서도 해결 불가능하다는 것을 뜻했다. 이 아이디어는 튜링 논제(Turing thesis) 또는 처치-튜링 논제(Church-Turing thesis)라고 불린다. 이것이 논제라고 불리는 이유는 수학적으로 엄밀하게 증명될 대상이 되지 않기 때문이다. 하지만 이 논제는 다른 디지털 컴퓨터까지 적용되어, 그것들이 튜링 기계보다 더 나은 계산 능력을 갖지 않는다는 것을 보장해준다.

우리는 챕터 9 의 처음 얼마쯤만 살펴보고, 수리논리학의 배경지식을 갖춘 다음에, 다시 챕터 9 를 정복할 것이다. Martin Davis 는 이렇게 말했다.

II. 는 수리논리학에 대한 배경지식을 갖춘 다음에 살펴볼 것이고, III. 은 튜링의 논문의 챕터 10 에서 진행된다.

"힐베르트 함수 계산"이란 오늘날의 1차 논리를 뜻한다. 힐베르트는 이 논리에서 Entscheidungsproblem 을 정의했다.

튜링은 컴퓨터라는 용어를 사용하는데, 이때 당시 컴퓨터computer란 단순히 계산 "compute" 에 하는 사람 "-er" 이 붙은 "계산하는 사람" 이라는 뜻이었다. 물론 튜링도 컴퓨터를 계산하는 사람이라는 의미로 사용했다.

1972년 괴델은 이 튜링의 해석에 대하여 "튜링의 철학적 오류" 라고 평가했다. 괴델에 따르면 마음은 정적이지 않고 끊임없이 변하고, 심지어 마음의 상태는 무한에 가깝다. 이러한 의견 충돌은 마음을 궁극적으로 뇌의 기계적인 절차로 보는 관점과 그렇지 않은 관점의 차이에서 생겼다.

튜링은 연필로 숫자를 체킹한다는 것을 언급하며 수가 아닌 기호로 스퀘어를 마킹하는 기계 연산을 암시했다.

튜링은 인간의 어떤 행위를 기계적으로 표현할 수 있는 방법을 찾고, 그것을 실제로 기계화하였다. 그러므로 인간이 자신의 행위를 관찰하여 기계화하는 행위를 기계화하는 것은 가치있는 일이다.

p. 250 에서 한 말이란 바로 이전 페이지에서 한 말이다.

즉, 인간 컴퓨터가 계산하는 수열을 계산할 수 있는 계산기계가 구성될 수 있다는 것이다.

인간의 뇌와 기계 사이의 연관성에 대한 튜링의 매혹은 1936년의 계산가능한 수에 대한 논문에서도 이어졌다. 1950년에 나온 튜링의 다른 유명한 논문 《Computing Machinery and Intelligence》 에서는 마음에 대한 철학적 고찰이 주제이다.

논리와 계산가능성✔

러셀의 저명한 책 『Principia Mathematica』(수학원리)는 시작할 때 그 목표가 "수학을 전개할 때 사용되는 모든 추론 단계와 아이디어의 완전한 열거" 라고 말했다. 이 프로그램을 논리주의(logicism)라고 한다. 논리주의는 수학의 기초를 논리에 둔다. 이 위업을 달성하기 위해 러셀은 논리학의 모든 무기고를 열었다. 일부러 그들의 수학적 테크닉을 제한하는 것은 터무니 없어 보였다.

형식주의(formalism)를 주창했던 힐베르트는 달랐다. 형식주의는 공리 체계를 다뤘고, 특히 일관성(consistency), 건정성(soundness), 완전성(completeness), 결정가능성(decidability)을 강조하는 힐베르트 프로그램에 집중했다.

힐베르트는 교육적 목적과 분석적 목적으로 수학원리를 분석 및 분해하여 부분집합으로 확장시켰다. 그래서 그 조각들이 그것 자체만으로 연구될 수 있게 만들었다. 힐베르트는 이것을 괴팅겐에서 가르치다가 1928년에 이 내용을 『Principles of Mathematical Logic』 라는 책에 담아내었다. 이 책은 현재 "Hilbert & Ackermann"(힐베르트&아커만) 으로 더 잘 알려져있다.

튜링의 논문의 이후의 내용을 이해하기 위해서는 힐베르트&아커만에서 다룬 논리에 익숙해져야 한다. 힐베르트&아커만은 수리논리학의 표준이 되었다. 알론조 처치, Stephen Kleene, Elliott Mendelson, Herbert B. Enderton, 그리고 다른 많은 사람들이 이 표준을 따라 수리논리학 서적들을 집필했다.

명제 논리✔

(명제 논리는 수리 논리학에서 제대로 다루고, 여기에서는 독자가 명제 논리를 알고 있다고 가정하고 가볍게 넘어간다.)

힐베르트&아커만은 sentential calculus 를 다루는데, 이것은 이후에 명제 논리(propositional calculus, or propositional logic)라는 용어로 정착되었다.

이 논리는 힐베르트&아커만이 restricted functional calculus 라고 부르는 논리로 확장된다. 이는 오늘날 1차 논리(first-order logic, or first-order predicate logic, or first-order predicate calculus)라는 용어로 정착되었다. 몇 가지 개념을 소개하고 나면 우리는 1차 논리와 2차 논리를 구분할 수 있게 될 것이다.

명제 논리는 진리값을 갖는 선언적 명제(또는 문장)을 다룬다. 명제의 예시는 다음과 같다.

• 오늘은 월요일이다.
• 7 은 소수이다.

이 명제는 참이나 거짓이라는 진리값을 갖는다. 명제를 결합하여 더 복잡한 명제를 만들 수 있다. \(X\) 와 \(Y\) 를 \(\lor\) 로 결합한 명제 \(X \lor Y\) 는 둘 중 하나만 참이어도 참이 된다. \(\lor\) 는 "또는" 을 뜻한다. 명제 논리에는 동등 기호 \(=\) 가 포함되어 있지 않다. 최소한 힐베르트&아커만이 형식화한 명제 논리에서는 동등 기호가 존재하지 않는다.

한 명제가 다른 명제와 동등하다는 것은 모든 성분 명제의 진리값에 따라 두 명제가 같은 진리값을 갖는다는 것이다. 이 동등함을 표현하기 위해 메타언어(metalanguage)로도 알려진 인간 언어를 사용한다. 메타언어는 다른 언어를 다루는 언어이다. 힐베르트&아커만은 두 명제가 같다는 것을 표현하려고 다음과 같은 메타언어 \(\text{eq.}\) 를 사용했다. "equivalent" 의 줄임말인 \(\text{eq.}\) 는 명제 논리의 언어가 아니다.

"그리고" 를 뜻하는 논리 연산 기호는 \(\land\) 이다. 명제 \(X\land Y\) 는 \(X\) 와 \(Y\) 가 둘 다 참이어야만 참이 된다.

"그리고" 연산은 결합(conjunction)으로 불리고 "또는" 연산은 보통 분리(disjunction)로 불린다.

\(\lor\) 가 \(\land\) 보다 먼저 연산되는 경우 두 연산을 함께 쓸 수 있다. 이 연산 우선순위를 명확성을 위하여 괄호로 표시할 수도 있다. 즉, 다음이 성립한다.

결합과 분리가 이항연산이지만, 부정 연산은 단항연산이다. 명제에 마이너스 기호를 붙이면 진리값이 반전된다. 가령 \(X\) 의 진리값은 \(-X\) 와 다르다. 그러므로 다음이 성립한다.

함의(implication)라는 이항연산은 \(X \implies Y\) 로 표기한다. 함의는 "\(X\) 가 \(Y\) 를 함의한다" 또는 "\(X\) 가 참이면 \(Y\) 도 참이다" 또는 "\(X\) 이면 \(Y\) 이다" 라는 뜻이다. 가령 "비가 오면 빗물이 흐른다" 라는 것이 함의 명제이다. 그래서 \(X \implies Y\) 가 참이 되려면 \(X\) 가 참일 때 \(Y\) 가 참이어야 한다. 반면, \(X\) 가 거짓이면 가정이 성립하지 않으므로 공진리(vacuous truth)에 의하여 \(X \implies Y\) 가 무조건 참이 된다. \(X\) 가 참인데도 \(Y\) 가 거짓일 때에만 \(X \implies Y\) 는 거짓말이 된다.

힐베르트&아커만은 이중조건문(biconditional) 또는 필요충분조건(if and only if, iff) 연산 \(\iff\) 도 정의했다. \(X \iff Y\) 는 \(X\) 와 \(Y\) 가 똑같은 진리값을 가질 때에만 참이 된다.

모든 경우에서 참인 명제를 항진식(tautology)라고 한다. 항상 거짓인 명제를 모순(contradiction)이라고 한다.

다음과 같은 명제를 생각하자.

이 명제는 \(X\) 와 \(Y\) 의 값에 따라 참이 될 수도 있고 거짓이 될 수도 있다. 이러한 명제를 만족스러운 명제라고 한다. 항진식 또한 만족 명제라고 간주한다.

우리는 명제를 구성하는 명제의 진리값을 따져보며 진리표를 만들고, 이로써 명제가 항진식인지 모순인지 만족 명제인지 결정할 수 있다. 이 작업은 기계적이다. 이 작업에는 어떠한 통찰이나 영감이나 직관이 필요치 않다. 당신이 프로그래머라면 벌써 명제의 참과 거짓을 따지고 명제를 결정하는 알고리즘이 떠오를 것이다. 그러므로 우리는 명제 논리를 결정가능하다고 말한다. 명제 논리에는 명제를 결정할 결정 절차가 존재한다.

그러므로 Entscheidungsproblem 은 명제 논리에서 해결가능하다. 명제가 아무리 길든 간에, 그래서 구성 명제가 \(100\) 개여서 진리표의 라인이 \(2 ^{100} = 1267650600228229401496703205376\) 개가 된다고 해도, 그것은 어쨌든 결정가능하다. 진리표를 계산하는 계산 시간은 지수 시간으로 알려져있다.

1차 논리✔

(1차 논리는 수리 논리학에서 제대로 다루고, 여기에서는 독자가 1차 논리를 알고 있다고 가정하고 가볍게 넘어간다.)

하지만 명제 논리는 대부분의 목적을 이루기에는 불충분하다. 가장 큰 문제는 명제 논리의 명제가 완전히 선언적인 명제라는 것이다. 그래서 명제의 내부를 다룰 수 없다. 명제 논리는 매우 단순한 3단논법(인간은 죽는다, 소크라테스는 인간이다, 그러므로 ...)도 다루지 못한다.

우리는 명제 함수(propositional function) 또는 술어(predicate)를 도입하여 명제 논리를 더 강력하게 만들 수 있다. 술어라는 용어는 문법에서 왔다. 문장은 주어와 서술어로 나뉜다. 가령 "비가 내린다" 에서 "비" 가 주어이고 "내린다" 가 술어이다. 또한 "정치인이 크게 연설했다" 에서 정치인이 주어이고 "크게 연설했다" 가 술어이다.

술어를 도입하는 것이 명제 논리를 1차 논리로 만드는 첫단계이다. 우리가 술어를 사용할 때, 반드시 그것의 도메인(domain, 모수)을 정한다. 현실에서 이 도메인은 대부분 자연수이다.

힐베르트&아커만에서 술어는 함수와 같지만, 함숫값으로 참이나 거짓만을 갖는다. 가령 이전에 만들어놓았던 \(\text{IsPrime}\) 함수의 도메인은 자연수이고 \(\text{IsPrime}(7)\) 은 참이고 \(\text{IsPrime}(9)\) 는 거짓이다. 술어가 인자를 전달받으면 명제가 된다. 가령 \(\text{IsPrime}(10)\) 은 "10 은 소수이다" 라는 명제이다. 술어는 여러 인자를 받을 수 있다. 가령 \(\text{Loves}(\text{Pat}, \text{Terry})\) 는 "팻이 테리를 사랑한다" 는 명제이다.

그러면 \(\text{Loves}(x, \text{Pat})\) 은 무슨 뜻일까? 이것에는 인자 중 하나에 변수가 들어갔으므로 양화사(quantifier)로 모호함을 해소해주어야 한다. 다음과 같이 쓰면 모든 \(x\) 에 대하여 \(x\) 가 \(\text{Pat}\) 을 사랑한다는 뜻이 된다. \(\forall\) 은 보편 양화사이다.

\(\exists\) 는 존재 양화사로써 다음과 같이 쓰면 테리를 사랑하는 누군가가 존재한다는 뜻이 된다.

1차 논리에서 양화사는 도메인의 변수에 대해서만 적용된다. 2차 논리에서는 양화사가 명제 함수로 표현되는 변수에도 적용 가능된다. 양화사는 다음과 같이 중첩될 수 있다.

이것을 보통 편의상 다음과 같이 쓴다.

이것은 \(\exists x : P(x)\) 에서 \(P(x) = \forall y : \text{Loves}(x, y)\) 가 치환된 것이다.

1차 논리에서도 항진식가 존재하는데, 1차 논리에서는 항상 참인 명제를 보편적으로 타당(universally valid)한 명제라고 한다. 가령, 다음은 보편적으로 타당하다.

다음은 반드시 거짓일 수밖에 없는데, 명제 논리에서 항상 거짓인 명제를 모순이라고 했다면 1차 논리에서는 이것을 논박가능한 명제(refutable)라고 한다.

한편, 보편적으로 타당한 명제와 논박가능한 명제 사이에 있는 명제도 있을 것이다. 가령,

에서 도메인이 자연수, \(F\) 는 "0 과 같거나 큰" 이라고 하자. 그러면 이 명제는 항상 참이다. 반면, \(F\) 가 "소수이다" 라고 하자. 그러면 이 명제는 거짓이 될 것이다. 이렇게 해석에 따라 참이 되는 명제를 만족스러운 명제(satisfiable)라고 한다.

명제는 만족스럽거나 논박가능하다. 어떤 명제가 타당하면 만족 명제이다. 그러나 만족 명제라고 해서 타당한 것은 아니다. 어떤 명제가 만족 명제이고 타당하지 않으면 이 명제는 만족 명제이지만 논박가능한 명제는 아니다.

타당성(validity)과 만족성(satisfiability)은 수리논리학의 의미(semantic)적인 접근과 연관되어 있다. 왜냐하면 이것들이 명제에 관련된 진리의 의미에 관련되어 있기 때문이다.

수리논리학의 또 다른 접근법은 구문(syntactic, 문법, 통사론적)적 접근이다. 공리(axiom)로부터 시작하여 정리를 도출해내는 것이다. 이렇게 도출된 정리를 증명가능하다고 한다. 이 접근법을 따르면 진리에 관한 형이상학적일 수도 있는 지저분한 개념에 얽매일 필요가 없다.

힐베르트&아커만은 명제논리의 공리로써 수학원리에서 유래한 다음의 4가지 명제를 선언했다.

1. \(X \lor X \implies X\)
2. \(X \implies X \lor Y\)
3. \(X \lor Y \implies Y \lor X\)
4. \((X \implies Y) \implies (Z \lor X \implies Z \lor Y)\)

이 공리들은 분리와 함의밖에 사용하지 않았지만, 결합을 다음과 같이 정의하여 사용할 수 있다.

1차 논리에서 힐베르트&아커만은 다음과 같은 두 가지 공리를 추가하였다. 임의의 술어 \(F\) 에 대하여 다음은 위 4가지 공리에 추가된 공리이다.

5. \((\forall x)F(x) \implies F(y)\)

6. \(F(y) \implies (\exists x)F(x)\)

공리에서부터 더 복잡한 명제를 얻기 위하여 다음의 연역 규칙을 사용할 수 있다.

1. 치환: 명제 변수를 명제로 치환할 수 있다.
2. 함의: 명제 \(P\) 가 참이고 \(P \implies Q\) 가 참이면 \(Q\) 도 참이다.

두번째 규칙을 긍정 논법(MP, modus ponens)라고 한다.

이 6가지 공리와 2가지 규칙을 통하여 도출된 것을 정리(theorem)라고 하고, 이 도출 자체를 증명(proof)이라고 한다. 증명의 결과가 되는 명제를 증명가능하다고 한다. 따라서 정리는 증명가능하다.

가령, \(P\) 와 \(Q\) 가 정리이면 공리 3 과 규칙 1 에 의하여 다음도 정리이고 증명가능하다.

공리로부터 시작하여 정리를 도출할 수 있고, 어떤 명제를 공리로 되돌려볼 수도 있다. 후자의 경우는 어떤 명제가 정리인지 확인하려는 것이다. 자동 정리 프로그램들은 수학 원리에서 소개된 이 공리와 규칙들을 사용하여 정리들을 도출해낸다.

힐베르트 프로그램과 이후의 상황✔

이렇듯, 힐베르트는 수학을 형식화하여 수학의 발전을 단순히 기호의 기계적인 조작으로 격하시키려 했다. 즉, 이들은 공리와 연역 규칙을 때려넣으면 근의 공식, 미적분법, 오일러의 세상에서 가장 아름다운 공식 같은 수학의 모든 진리들을 도출해내는 기계를 만드려 한 것이다.

그렇다면 정리들은 보편적으로 타당한 명제들과 같은가? 아니면 공리로부터 생성되지 않은 보편적으로 타당한 명제들이 존재하는가?

힐베르트&아커만을 기반으로 괴델은 1차 논리에 대한 의미적 접근과 구문적 접근이 동등하다는 것을 증명했다. 괴델 이전에, 모든 증명가능한 명제가 보편적으로 타당하다(의미론적으로도 참이다)는 것이 알려져 있었다. 이것을 건전성(soundness)이라고 한다. 그리고 이것은 논리 체계의 핵심이다.

괴델이 증명한 것은 모든 보편적으로 타당한 명제는 증명가능하다는 것이다. 이것을 완전성(completeness)이라고 한다. 괴델은 힐베르트&아커만에 의하여 제시된 공리 체계가 완전하다는 것을 증명한 것이다. 괴델의 완전성 정리는 1차 논리를 위하여 힐베르트&아커만이 제시한 공리 체계가 모든 보편적으로 타당한 명제를 열거하기에 충분하다는 것을 보여준다. 즉 공리가 완전하다는 것을 보여준다.

정리의 열거와 괴델의 완전성 정리는 1차 논리에서의 결정절차에 대한 기반을 제공해준다. 가령 어떤 명제 \(P\) 의 증명가능성을 결정하고 싶다면, 모든 정리를 열거하면서 \(P\) 와 비교해보면 된다. 만약 \(P\) 가 증명불가능하면 매칭되는 정리를 찾을 수 없을 것이고 정리를 열거하는 것을 언제 멈추어야 할지 모를 것이다.

\(P\) 가 만족 명제이거나 보편적으로 타당하지 않거나 논박 가능한 명제이면 매칭되는 정리를 찾을 수 없다. 따라서 열거 기반의 결정 절차는 준결정가능(semi-decidable)하다. 괴델이 완전성 정리를 발표한 1930년에도 여전히 Entscheidungsproblem 은 해결되지 않았다.

괴델은 1931년에 더 유명한 불완전성 정리를 발표했다. 그는 덧셈과 곱셈 같은 기초 산술을 포함하는 1차 논리에서 산술을 사용하여 괴델은 모든 명제와 증명을 수로 만들었다. 괴델은 "증명가능하다" 라는 술어를 만들고 그것의 부정의 괴델 수에 이 술어를 적용했다. 그러면 그것 자체의 증명불가능성을 주장하는 명제가 완성된다. 이로써 기초 산술을 포함하는 논리 체계라면 본질적으로 증명되거나 반증될 수 없는 참인 명제가 반드시 존재한다는 것이 증명되었다. 이 정리가 불완전성 정리로 알려져있지만 이 논문의 제목은 "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I" 였고, 이 제목은 완전성이나 불완전성을 지칭하는 것이 아닌 결정불가능한 명제에 대하여 지칭하고 있었다.

불완전성 정리는 결정가능성을 부정하지 않았다✔

그렇다면 불완전성 정리가 일반적인 결정 절차의 종말을 선언했는가? 그렇지 않다. 불완전성 정리가 결정불가능한 명제에 관한 것이지만, Entscheidungsproblem 는 주어진 명제의 증명가능성을 결정하는 일반적 절차에 대한 존재성에 관한 것이다. 만약 결정 절차가 존재한다면 결정불가능한 명제에 대하여 증명불가능하다고 분류해줄 것이다.

튜링은 그의 기계에 의하여 계산가능한 수가 "자연스럽게 계산가능하다고 여겨지는 모든 수" 도 포함해야 한다고 말했었다. 그리고 나서 튜링은 로마 숫자 I. 로 시작하는 섹션을 시작하여 이 섹션을 Type (a) 라고 했었다. 이 의미는 "직관에 호소하기" 였다. 이제 튜링은 로마 숫자로 섹션 II. 를 시작하며, Type (b) 로 논의를 진행하려 했다. 이것의 의미는 "두 정의의 동등성에 대한 증명(새 정의가 더 직관적일 경우)" 이었다.

\(\mathcal{K}\) 는 이미 테이프 위에 인코딩 되어 있는 공리에서 시작하거나 공리를 테이프 위에 쓰면서 시작한다. 이 공리들은 1차 논리의 기본 공리이거나, 다른 술어를 위해 필요한 추가 공리들이다. 이 기계는 증명 가능한 모든 명제를 생성할 수 있는 추론 규칙을 구현한다.

중요한 점은 이 기계가 증명가능한 모든 명제를 생성한다는 점이다. 괴델의 완전성 정리는 증명가능한 명제의 모임이 보편적으로 타당한 식과 같다는 것을 보장해준다.

1차 논리 체계에 자연수를 도입하는 것은 필수적이다. 수를 논리에 병합하는 것은 페아노 공리의 변형으로부터 시작된다. 이것은 페아노의 오리지널 9가지 공리로부터 추출한 5가지 공리이다. 페아노 공리는 다음수(successor)의 개념을 기반으로 세워진다. 다음수는 다음 숫자라는 개념으로 가령 12 의 다음수는 13 이다. 다음수를 가지지 않는 유일한 수는 0 이다. 1차 논리에 자연수를 도입하는 페아노 공리는 다음과 같다.

1. 0 은 수이다.
2. 모든 수는 다음수를 갖는다.
3. 0 은 어떤 수의 다음수도 아니다.
4. 다음수가 같은 두 수는 서로 같다.
5. 어떤 것인 0 에 대하여 참이고, 그것이 어떤 수에 대하여 참일 때 그것의 다음수에서도 참이면, 그것은 모든 수에서 참이다.

이 페아노 공리는 수론에서 엄밀하게 정의된다. 5) 는 수학적 귀납법을 말하고, 튜링도 이 논증을 사용했다. 그러나 1차 논리 언어로 귀납법을 표현하는 것은 약간 문제가 있다. 왜냐하면 귀납이 자연수에 대하여 주장하는 모든 술어에 적용되어야 하므로 귀납이 본질적으로 2차 논리의 개념이기 때문이다.

동등성(\(=\))의 개념도 본질적으로는 2차 논리의 개념이다. 그래서 논리학자들이나 이 논문에서의 튜링도 두 argument 가 같을 때 그것을 참인 술어를 도입하는 것을 주저하는 것처럼 보이는 것이다.

수론을 도입할 때 첫번째 수를 \(0\) 로 삼고 그것의 다음수들을 \(0', 0'', 0''', \dots\) 로 두고 그것들에 \(1,2,3,\dots\) 의 기호를 정의한다. 그러나 튜링은 \(0\) 이라는 기호조차 사용하기를 거부하고 \(u\) 라는 기호를 사용했다. 튜링은 효과적인 표기를 위해 가령 \(u''''' = u ^{(5)}\) 로 표기했다.

튜링은 \(x\) 가 음이 아닌 정수일 때 참이 되는 명제 함수 \(N(x)\) 를 정의했다. 또한 튜링은 \(y\) 가 \(x\) 의 다음수일 때 참이 되는 명제 함수 \(F(x,y)\) 를 정의했다. 즉, \(F(x,y)\) 는 \(y = x+1\) 라는 뜻이다.

가령 다음과 같은 수열 \(\alpha\) 을 생각하자.

\(G _{\alpha}(0)\) 는 참, \(G _{\alpha}(1)\) 는 거짓, \(G _{\alpha}(2)\) 는 참이 된다.

\(F\) 는 자연수를 정의할 때 필수적인 다음수 함수이다.

공리의 결합은 실제로 \(\alpha\) 를 정의하지 않고 \(\alpha\) 를 정의할 기반을 제공하지도 않는다.

\(P\) 는 페아노(Peano)를 뜻하고 이는 세 항의 결합이다. 첫째는 \(u\) 의 존재성, 둘째는 임의의 수가 다음수를 갖는다는 것, 셋째는 다음수가 자연수라는 것을 주장한다. 그런데 이것은 \(0\) 의 유일성이나 다음수의 유일성을 주장하지는 않았고, 이는 문제였다. 다음수 함수 \(S\) 가 갖는 공리는 다음과 같다.

첫째는 임의의 수가 다음수를 갖는다는 것, 둘째는 predecessor 를 가지지 않는 수가 존재한다는 것, 셋째는 \(r\) 이 \(x, y\) 의 다음수이고 \(x\) 가 \(s\) 의 다음수라면 \(y\) 도 \(s\) 의 다음수라는 것을 주장한다. 이로써 다음수의 유일성이 보장된다.

즉, \(F ^{(n)}\) 은 \(1\) 은 \(0\) 의 다음수이다, \(2\) 는 \(1\) 의 다음수이다, ... , \(n\) 은 \(n-1\) 의 다음수이다 를 뜻한다. 또한, \(A_n\) 은 \(\alpha\) 의 \(n\)번째 수가 \(1\) 임을 주장하고, \(B_n\) 은 \(\alpha\) 의 \(n\)번째 수가 \(0\) 임을 주장하는 것이다.

그러나 튜링의 다음수 함수에 대한 결합은 여전히 다음수의 유일성을 보장해주지 않았다. 가령 \(F(u', u''')\) 의 진리값은 무엇인가? 이것이 거짓이라는 근거는 어디에도 없다. 그래서 사실은 \(-F(u',u''')\) 처럼 \(F\) 의 결과값이 거짓임을 보장해주는 모든 식이 추가되어야 한다.

수열의 수가 홀수인지 검증해주는 튜링기계 \(\text{IsOdd}(n)\) 은 다음과 같은 수열을 출력한다.

이 수열에서 다음과 같은 식은 증명가능하다.

\(\mathfrak{A}\) 는 \(\text{IsOdd}\) 함수에 필요한 모든 공리를 포함한다. 이 결과는 수열의 첫 6번자리 수가 \(0,1,0,1,0,1\) 이라는 것에 대응된다.

\(\mathcal{K}\) 는 공리로부터 증명가능한 모든 식을 생성해내는 튜링기계라는 것을 기억하자.

가령 \(n\) 이 \(5\) 이면 기계는 다음과 같이 쓴다.

항 \(\mathfrak{A}\) 는 모든 공리의 결합이 될 것이고, \(F ^{(5)}\) 는 추가적인 공리의 결합이 될 것이다. 요점은 둘 중 하나의 식이 증명가능하다는 것이다. 기계는 테이프 위에 먼저 공리를 쓰고, 증명가능한 식들을 도출해내기 시작할 것이다.

\(\mathcal{K} _{\alpha}\) 도 보편 기계처럼 일반화될 수 있다고 충분히 생각할 수 있다. 이 기계는 이미 테이프에 인코딩 되어 있는 공리로부터 출발하여, 다른 공리나 다른 함수를 테이프에 인코딩하고, 1차 논리로 정의가능한 임의의 수열을 계산할 수 있을 것이다.

튜링은 1차 논리의 관점에서 계산기계를 설명했다. 지금은 그는 독자에게 모든 수를 기계로 계산가능하지 않다는 것을 상기시켜주길 원했다.

튜링은 그의 기계가 계산가능한 수를 계산할 수 있다는 것을 정당화했다.

§10 - Examples of large classes of numbers which are computable (계산가능한 함수)✔

튜링은 이후의 다른 논문에서 계산가능한 함수의 개념을 이렇게 설명했다.

기계는 이미 함수를 구현했다.

가령 무한한 수를 가지는 무리수를 컴퓨터로 계산하려면 어떻게 해야 할까? 무리수는 무한한 수를 가지므로 이것을 정확하게 컴퓨터로 계산할 수는 없다. 따라서 수를 근사시키는 것이 중요하다. 오늘날의 컴퓨터는 다음의 무한급수를 통하여 삼각함수를 계산한다.

오늘날의 컴퓨터는 각 항을 계산해가면서 정확도를 높이고 설정된 정확도까지 계산하면 계산을 그만둔다. 그러나 튜링 기계에서는 아직 문제가 있다. \(x = 1\) 일 때 첫번째 항은 \(1\) 이므로 계산하기 쉽다. 그러나 두번째 항은 \(\frac{1}{6}\) 이다. 이 항부터 이미 무한한 수를 계산해내야 한다. 튜링기계에서 무리수를 계산할 한 가지 전략이 있는데, 그것은 각 항에서 첫번째 자리수를 계산하고 첫번째 자리수가 \(0\) 이 되어가면 계산을 그만 둔다. 그리고 각 항에서 두번째 자리수를 계산하고 두번째 자리수가 \(0\) 이 되어갈 때 계산을 그만 둔다.

그러나 여전히 문제가 있다. 튜링 기계는 입력을 받는 것이 아직 곤란하다. 이를 위한 한 가지 전략은 하드코딩을 하는 것이다. 가령 \(\sin 37\) 을 계산하도록 설정된 기계를 만드는 것이다. 또 하나의 전략은 테이프에 입력값을 인코딩하는 것이다. 그러면 기계가 입력값을 읽고 계산을 시작할 수 있다. 또 하나의 전략은 기계가 입력을 생성하게 하는 것이다. 가령 기계가 \(\sin 1\) 을 계산했다가 \(\sin 2\) 를 계산했다가 하는 식으로 설정하는 것이다. 또 하나의 전략은 두 기계를 두고 한 기계는 실수를 생성하고 다른 기계는 그것의 사인값을 계산하는 것이다.

문제의 본질은 입력이 실수이고, 출력도 실수이고, 실수는 무한한 자리수를 가진다는 것이다. 무한한 자리수를 가지는 실수를 입력할 수도 없고, 그것을 테이프에 인코딩할 수도 없다.

섹션 10 은 이전 섹션의 내용이 곧바로 이어진다. 이전 섹션에서 튜링은 기계의 계산가능한 능력에 관련된 세 가지 논의를 말했다. 세번째는 계산가능한 수의 큰 클래스에 대한 예시를 제시하는 것이었다. 튜링은 계산가능한 수에 대한 그의 관심을 계산가능함 함수에 대한 영역으로 옮겼다.

섹션 10 이 튜링의 논문에서 가장 분석하기 힘든 섹션이다. 섹션 10 에서 튜링은 아주 간결하게 말했고, 그 때문에 문장들이 그 뜻이 분명하지 않고 종종 모호했다.

가령, \(\phi\) 가 다음과 같은 함수라고 하자.

이 함수에 대응되는 수열 \(\gamma\) 는 다음과 같다.

\(\gamma\) 는 계산가능하다. 이는 \(\phi (n)\) 이 계산가능한 함수임을 뜻하고, 이는 기계가 모든 값에 대한 함수를 계산하면서 \(\gamma\) 를 영원히 계산한다는 것을 뜻한다.

튜링은 이 접근 방식의 반대 방향으로 접근했다. 그는 먼저 \(0\) 가 무한히 나타나는 수열 \(\gamma\) 를 가정하고, \(\xi (\gamma ,n)\) 을 연속되는 \(1\) 의 개수를 표현하게 하고, \(\phi (n)\) 을 \(\xi (\gamma ,n)\) 으로 정의했다.

이 관점에서 \(0\) 가 무한히 나타나는 수열을 계산하는 임의의 기계는 양의 정수의 함수도 계산한다.

이제 튜링은 \(\phi\) 함수에 대응되는 술어를 가정하고 그것이 이전 챕터에서 살펴본 방식대로 논리 기반의 수 계산과 비슷해지게 했다.

\(\phi (x) = 2x + 1\) 의 경우 다음과 같은 술어 \(H(x, y)\) 를 정의할 수 있다.

\(\mathfrak{A}_{\phi }\) 는 \(H\) 와 \(P\) 를 정의하기 위하여 필요한 술어를 위한 공리의 결합이다. 우리의 예시의 경우 \(\text{Product}\) 와 \(\text{Sum}\) 을 정의하기 위하여 필요한 공리들이 해당될 것이다.

\(F ^{(N)}\) 은 \(N\) 까지의 수가 존재한다는 것을 보장해주는 다음수 함수의 결합이라는 것을 기억하자.

\(N\) 은 \(n\) 과 \(\phi (n)\) 만큼 크거나 더 커야 한다. \(n = 10\) 인 경우 \(\phi (n) = 21\) 이고 \(H\) 함수의 내부에서 숫자 \(1\) 과 \(2\) 가 필요하며 \(z = 20\) 이 될 것이다. 그러므로 \(N\) 은 최소한 \(21\) 이 되어야 한다. 그래야만 충분히 수를 정의할 수 있다.

\(N'\) 은 최소한 \(m\) 만큼 커야 한다.

튜링은 더 이상의 설명을 하지 않고 여기에서 그만두었다. 이것은 모든 증명가능한 식을 나열하는 \(\mathcal{K}\) 기계를 수정한 것이다. 이것은 섹션 9 에서 설명했듯이 모든 증명가능한 식을 나열하여 술어 \(G\) 의 진리값에 대응되는 값 \(n\) 에 대한 1 또는 0 을 출력한다.

다음과 같은 수열 \(\gamma\) 을 계산하는 기계 \(\mathcal{K} _{\gamma }\) 가 필요하다.

다른 점은 이 기계가 \(n\) 의 연속적인 값에 대한 모든 증명가능한 식을 나열할 뿐만 아니라 \(n\) 과 \(m\) 의 값을 변화시킨다는 것이다. 각 새로운 값 \(n, m\) 에 대하여 기계는 식 \(A\) 와 \(B\) 를 출력한다.

그리고 모든 증명가능한 식을 생성하며 둘 중 한 식의 매칭을 시도한다. \(n = 0\) 부터 시작하는데, 이것이 \(\phi (n)\) 와 \(H(n, m)\) 의 인자가 된다. 각 새로운 \(n\) 의 값에 따라 기계는 \(0\) 을 출력하고 \(m\) 을 \(0\) 으로 설정한다. \(m\) 은 \(\phi (n)\) 의 결과가 될 수 있고 술어 \(H(n, m)\) 의 인자가 될 수 있다.

각 새로운 \(m\) 의 값에 따라 기계는 모든 증명가능한 식을 생성한다. 만약 식 \(B\) 가 매칭되면 기계는 \(1\) 을 출력한다. 왜냐하면 \(m\) 의 값이 \(\phi (n)\) 의 결과가 아니기 때문이다. 기계는 \(m\) 을 증가시키고, 새로운 \(A\) 와 \(B\) 를 출력하고, 또 증명가능한 모든 식을 생성한다. 만약 \(A\) 가 매칭되면 \(m\) 은 \(\phi (n)\) 의 결과이므로 기계는 \(n\) 의 다음 값으로 넘어간다. \(n\) 의 다음 값에서 기계는 \(0\) 을 출력하고 \(m\) 을 다시 \(0\) 으로 설정한다.

이렇게 기계는 수열 \(\gamma\) 를 출력한다.

이를 위해 계산가능한 수와 계산가능한 함수의 계산이 협력하며 작동해야 한다. 가령 새로운 변수가 계산되면 계산가능한 함수가 그것을 받아서 새로운 결과의 수를 출력한다. 계산가능한 수와 계산가능한 함수는 같은 수준의 정확도를 유지해야 한다.

튜링은 이러한 함수의 예시로 탄젠트 함수를 예시로 들었다. 튜링은 모든 계산가능한 수에 대하여 탄젠트를 계산하려 했다.

탄젠트 함수는 변수 \(-90 \degree\) 와 \(90 \degree\) 를 거쳐가면서 함숫값 \(- \infty\) 와 \(\infty\) 를 거쳐간다. 즉, 모든 실수값을 거쳐간다.

탄젠트 함수도 실제로 계산할 때는 사인함수처럼 다음과 같은 무한급수를 통하여 계산된다.

함수 \(\phi (n)\) 은 만족 기계의 표현 수를 정의역과 치역으로 갖는다. \(\phi (n)\) 은 표현수를 수정하고, 본질적으로 기계를 재프로그래밍하여 다른 것을 계산하게 한다. 가령, \(x\) 를 계산하는 대신 \(2x + 1\) 을 계산하게 한다.

(ii) 와 (iii) 의 증명은 섹션 10 의 후반부에 소개된다.

쉽게 말해 스택을 쌓을 수 있다. 수를 계산하는 기계에서 시작하여, 이것을 그 수의 함수를 구현하는 기계에 적용할 수 있고, 첫번째 함수의 결과의 함수를 구현하는 또 다른 기계에도 적용할 수 있다. 탄젠트 함수를 기반으로 하는 이전의 함수도 기존 단계가 완료될 때까지 기다리지 않고, 수가 계산될 때마다 정보를 전달해주어야 한다.

가령 \(r = 1\) 이고 \(\phi (m,n) = m \cdot n\) 일 때 \(\phi\) 가 계산가능하다는 것은 자명하다. 이때 \(\eta\) 의 몇가지 값만 계산해보면 다음과 같다.

이렇게 \(\eta\) 는 팩토리얼 함수의 기능을 하게 된다. 튜링은 이렇게 계산가능한 함수로 정의된 정수 변수 함수 또한 계산가능하다는 것을 증명해보였다.

이것은 자명해보이지만, 튜링은 어떤 흥미로운 사실을 보여줄 기회로 이 정리의 증명을 소개했다.

가령 \(\text{IsPrime}(n)\) 이 \(n\) 이 소수일 때 \(1\) 을, 아닐 때 \(0\) 을 반환하면 다음 수열은 계산가능하다는 것이다.

이제 튜링은 하디의 『Course of Pure Mathematics』 에서 소개된 다음과 같은 데데킨트 정리를 언급했다.

이 정리는 실수와 유리수의 근본적인 차이를 말해주며, 특히, 실수가 어떻게 선형연속체를 구성하고 유리수는 구성하지 못하는지를 말해준다. 음의 무한대에서 양의 무한대로 가는 수의 선을 만들고 어느 한 지점을 절단하면 정확히 그 지점에 존재하는 수를 찾을 수 있고, 이것을 데데킨트 절단이라고 한다. 가령 \(\sqrt[]{2}\) 를 기준으로 이것보다 작은 수를 \(L\) 에, 큰 수를 \(R\) 에 속하게 하고 \(\sqrt[]{2}\) 를 \(L\) 과 \(R\) 에 속하게 할 수 있지만, 유리수에서는 \(\sqrt[]{2}\) 가 존재하지 않으므로 이것이 불가능하다.

즉, 계산가능한 수는 선형연속체를 형성하지 않는다. 왜냐하면 계산불가능한 수에서 데데킨트 절단을 만들 수 있기 때문이다. 가령, 어떤 수가 알고리즘적으로 정의하기 매우 복잡하여 정의 자체가 불가능할 수도 있고, 정의할 수는 있지만 계산이 불가능할 수도 있다. 후자의 경우 모든 계산가능한 수에서 한 자리수를 가져와서 수를 만들면 정의는 가능하지만 계산은 불가능하다.

튜링이 아래에서 소개하는 명제 함수 \(G(\alpha)\) 는 전달된 인자가 계산가능한 수로써 상수 \(\xi\) 보다 작으면(또는 작거나 같으면) 참이 된다. \(G(\alpha)\) 는 계산가능한 수를 두 클래스 \(L\) 과 \(R\) 로 나눈다. 그러면 데데킨트 정리의 조건 1) 은 성립하게 된다.

위 조건은 데데킨트 정리 조건 2) 와 동등하다.

위 조건은 데데킨트 정리 조건 3) 와 동등하다. 즉, \(G(\alpha)\) 가 참이면 \(\alpha\) 가 \(L\) 에 속하는 것이고, \(\beta\) 가 거짓이면 \(\beta\) 는 \(R\) 에 속하는 것인데 이 경우 반드시 \(\alpha<\beta\) 이다.

\(G(\alpha)\) 의 진리값을 결정하는 일반적 절차가 핵심이다. \(\xi\) 는 계산가능한 수이므로 일반적으로 \(G(\alpha)\) 의 정의에 명시적으로 저장될 수 없다. 그럼에도 기계가 그 값으로 좁혀지는 수를 계산할 수는 있다.

이제 튜링은 "계산가능한 수의 열" 이라는 표현을 사용하는데, 이 표현은 그의 논문 중에서 가장 혼란스러운 표현이다. 그는 "계산가능한 열" 이라는 표현을 기계가 생성하는 수를 지칭하기 위하여 사용했고, 여기서 그가 사용하는 "열(sequence)" 이라는 표현은 계산가능한 수의 순서 모임(ordered collection)이다.

이 부분을 주제로 토론이 있어왔는데, 한 가지 의견은 \(\frac{1}{2}\) 가 실수이고 사실은 \(- \frac{1}{32}\) 라는 것이다. 이 의견이 수열을 그럴듯하게 만들기는 하지만 이 수열이 계산가능한 극한인 \(0\) 로 접근하고 있기 때문에 튜링이 실제로 생각한 것이라고는 할 수 없다.

또 다른 의견은 튜링이 계산가능한 극한으로 접근하는 수열을 소개하려 했지만, 실제로는 그렇지 않다는 것이다. 수열은 유계 \(-1\) 과 \(1\) 을 가지며 이것은 극한이 실제로 계산가능한지도 말해주지 않는다.

튜링은 계산가능한 함수가 다음과 같은 다항식이라고 암시했다.

다항식 \(\phi (x)\) 에 대하여 우리는 \(\phi (1) = -1\) 와 \(\phi (2) = 21\) 사이 값을 좁혀가면서 해를 찾을 수 있다. \(\alpha=1, \beta=2\) 에 대하여 \(\alpha<\beta\) 이고 \(\phi (\alpha)<0<\phi (\beta)\) 이다. 함수가 연속이므로 \(\alpha\) 와 \(\beta\) 사이에서 \(\phi (\gamma )=0\) 가 되는 \(\gamma\) 가 존재한다. 목표는 이것을 계산하는 것이다. 그러면 \(1.5\) 를 선택해보고 \(\phi (1.5) = 3.125\) 로써 \(0\) 보다 크니까 \(1.25\) 를 시도해보고, 이런 식으로 계산가능하다.

연속적인 수의 차잇값이 작아지면서 수열이 수렴한다고 말할 수 있다. 임의의 실수는 유리수열의 수렴이다. 가령, 무리수 \(\pi\) 는 다음과 같은 유리수열의 수렴이다.

수열의 차잇값을 \(\epsilon\) 으로 두면, 특정 수열이 수렴하는 것은 임의의 양수 \(\epsilon\) 에 대하여 모든 \(n>N\) 과 \(m>N\) 에 대하여 \(|a_n - a_m| < \epsilon\) 이 되게 하는 \(N\) 이 존재한다는 것이다. 이 내용은 수론의 코시 수열에서 자세히 다룬다.

튜링은 계산가능한 수렴도 비슷하게 정의했다.

수열은 당연히 계산가능해야 하고, 튜링은 \(\epsilon\) 과 \(N(\epsilon)\) 도 계산가능해야 한다고 말했다.

다음과 같은 형태가 멱급수이다.

해석학에서 멱급수를 자세히 다룬다. 사인 함수는 다음과 같은 급수로 표현된다.

이 멱급수의 계수는 \(1,0,-1/3!, \dots\) 이다. 이 계수는 자명하게 계산가능한 수열을 형성한다. 어떤 멱급수는 \(x=0\) 에서만 수렴하고, 어떤 것은 수렴구간에서 수렴한다. 해석학에서 수렴구간을 자세히 다룬다. 사인 함수는 \(\R\) 에서 수렴하므로 수렴구간이 \(\R\) 전체이다. 계수가 계산가능하므로 기계가 수렴하는지 여부를 결정해줄 수 있다.

특정 함수로 수렴하는 함수열을 가질 수도 있다. 함수열은 점별수렴 할 수 있고, 또는 균등수렴할 수도 있다.

이 정리로부터 튜링은 모든 대수적 수가 다음과 같은 유명한 초월수처럼 계산가능하다는 결론을 내린다.

대수적 수는 다항식의 근이라는 사실을 기억하자.

이제 튜링은 논문에서 (ii) 와 (iii) 의 증명을 소개하지만, 여기에서는 생략하자. 해당 내용이 궁금하면 실제 튜링의 논문을 읽어보거나 "Petzold, The Annotated Turing" 를 읽어보면 된다.

튜링은 이로써 알고리즘이 필요로하는 모든 것을 형식적으로 포함하는 계산을 위한 모델을 정의했다. 그는 이제 Entscheidungsproblem 이 답을 가지지 않는다는 것을 증명할 준비를 마쳤다.

§11 - Application to the Entscheidungsproblem (증명)✔

섹션 8 에서 어떤 튜링 기계가 \(0\) 을 무한히 출력할지 판단하는 일반적 유한한 절차를 구현하는 튜링 기계는 존재하지 않는다는 것을 증명했다. 섹션 9 와 10 은 튜링 기계의 계산가능성이 인간의 계산가능성과 동등한 개념임을 논증했다. 이제 앞으로 볼 섹션 11 에서 튜링은 계산 기계의 기능성이 어떻게 1차 논리 언어로 표현되는지 보여준다. 그리고 튜링은 기계가 영원히 \(0\) 을 출력한다는 것과 동치인 증명가능한 식을 만들어 보였다. 만약 이 식이 결정가능하면, 즉, 만약 우리가 이것이 증명가능한지 판정할 수 있으면, 우리는 기계가 \(0\) 을 영원히 출력할지 판정하는 일반적 절차를 얻게 되는데, 우리는 이미 이것이 불가능하다는 것을 알고 있다.

튜링이 언급한 책이란 힐베르트와 아커만의 1차 논리에 대한 책이다. 저자는 다음과 같이 언급했다.

타당성과 만족가능성은 결정문제의 의미론적 기반을 지칭한 것이다.

튜링은 타당성이나 만족가능성이라는 단어보다 증명가능성이라는 단어를 사용함으로써 그가 의미론적 접근을 하려는 것이 아니라 구문론적 접근을 하려는 것임을 드러냈다. 의미론적 접근과 구문론적 접근은 수리논리학에서 자세히 살펴보았다. 구문론적 접근은 체계의 공리에 추론 규칙을 적용하여 진리를 연역해낸다.

섹션 9 와 10 을 통하여 튜링은 일반적 결정 절차를 구현하는 기계를 설계할 수 없다면, 인간이 수행할 수 있는 일반적 결정 절차도 존재하지 않는다고 주장할 수 있는 권리를 얻었다. 왜냐하면 그는 섹션 9 와 10 을 통하여 기계의 계산능력과 인간의 계산능력이 동등하다는 논증을 펼쳤기 때문이다.

괴델과 튜링은 결정가능성에 대하여 다르게 접근한 것이다. 괴델은 증명되지도 반박되지도 않는 명제의 존재성을 입증했는데, 이런 명제를 결정불가능하다(undecidable)고 한다. 튜링인 언급한 일반적 방법은 임의의 식을 분석하고 그것이 증명가능한지 증명불가능한지 판정하는 알고리즘(결정 절차)를 다루는 것이고, 이것이 존재하지 않는다는 것을 증명한 것이다. 결정불가능한 명제가 존재한다고 해도, 결정 절차는 존재할 수 있다.

괴델의 결과는 일반적 결정 절차의 기반을 제공해주지 않았다.

튜링 기계는 연산에 관련된 설정들로 구성된다. 튜링은 기계를 1차 논리의 언어로 표현해야 했다. 각 연산은 그 연산이 기계의 완전한 설정에 얼마나 영향을 끼치는지 표현하는 식으로 변환되어야 한다.

튜링은 몇 가지 명제함수(술어)를 소개했다. 이것은 참이나 거짓의 진리값을 갖는다. 이 함수에 전달되는 인자는 테이프와 완전한 설정의 스퀘어를 의미하는 음이 아닌 정수이다.

\(0\) 과 \(1\) 을 반복해서 출력하는 튜링기계의 처음 몇 완전한 설정은 다음과 같다.

CC x 는 완전한 설정(complete configuration) x 를 뜻하고, CC x 바로 우측 행이 스퀘어 Y 이다.

명제 함수의 정의✔

이전 챕터에서 "기호 \(S_0\) 는 빈칸, \(S_1\) 은 기호 \(0\), \(S_2\) 는 기호 \(1\), \(S_3\) 는 기호 \(e\), \(S_4\) 는 기호 \(x\) 일 것이다" 라고 했던 것을 기억하자. 그러면 가령 위의 예시에서 \(R _{S_2}(3, 2)\) 는 참이고, \(R _{S_2}(3, 1)\) 은 거짓이 된다.

위 예시에서 \(I(1, 1)\) 은 참이지만, 다른 스퀘어 \(y\) 에 대한 \(I(1, y)\) 는 모두 거짓이다.

위 예시에서 \(K _{q_2}(1)\) 은 참이고 \(K _{q_3}(1)\) 은 거짓이다.

즉, \(y = x + 1\) 라는 것이다. 가령 술어 \(F(u'', u''')\) 는 참이다.

이로써 튜링은 기계의 완전한 설정을 설명하는 명제 함수를 개발했다. 튜링은 이것을 실제 기계를 설명하는 표와 동일시하지는 않았다. 기계의 표준 형태는 라인 당 하나의 출력 명령과 하나의 이동 명령을 갖는다. 표의 각 라인은 m-설정 \(q_i\) 와 스캔된 기호 \(S_j\) 와 출력된 기호 \(S_k\) 와 왼쪽이나 오른쪽의 헤드 이동을 가질 수 있고 다음 m-설정 \(q_l\) 을 갖는다.

명제 Inst✔

튜링이 이제 소개하는 Inst 는 명령(instruction)의 약자이고, 명제 함수가 아니라 명제함수로 생성된 식의 축약이다.

이것은 Inst 식의 세 경우 중 하나이고, 이것은 헤드가 왼쪽으로 이동할 때 적용된다. 그래서 Inst 의 인자에 \(L\) 이 있는 것이다. 이전 챕터에서 "\((N_1)\) 형태는 \(q_iS_jS_kLq_m\) 로 표현할 수 있다. \((N_2)\) 형태는 \(q_iS_jS_kRq_m\) 로 표현할 수 있다. \((N_3)\) 형태는 \(q_iS_jS_kNq_m\) 로 표현할 수 있다" 라고 언급한 것을 기억하자.

첫번째 라인의 \(F(x, x')\) 는 \(x\) 와 \(x'\) 이 두 연속적인 완전한 설정이라는 뜻이다. 첫번째 라인의 \(F(y', y)\) 은 \(y\) 와 \(y'\) 이 두 인접한 스퀘어이다. 헤드가 왼쪽으로 움직이는 명령어에서 \(y\) 가 \(y'\) 의 다음수라는 것이다. 첫번째 라인의 나머지 3개 술어 \(R, I, K\) 는 특정 명령어를 지칭한다. 즉, 완전한 설정 \(x\) 에서 스캔된 스퀘어가 \(y\) 이고 스캔된 기호는 \(S_j\) 이고 설정은 \(q_i\) 라는 것이다.

두번째 라인은 함의 기호로 시작하는데, 이것은 명령어의 결과가 되는 완전한 설정을 뜻한다. 다음 완전한 설정은 \(x'\) 이고, 스캔된 스퀘어는 \(y'\) 이고, \(y\) 스퀘어는 이제 기호 \(S_k\) 를 갖고, m-설정은 이제 \(q_l\) 이 되었다.

세번째, 네번째, 다섯번째 라인은 스퀘어 \(y\) 이외의 스퀘어가 똑같이 남아있어야 한다는 것을 보장해준다. 모든 스퀘어 \(z\) 에 대하여 \(z\) 가 \(y'\) 다음 스퀘어인 \(y\) 가 아닐 경우 이전에 갖고 있던 기호를 그대로 보존해야 한다. \(S_0\) 부터 \(S_M\) 은 기계 \(\mathcal{M}\) 이 출력 가능한 모든 기호를 뜻한다.

튜링은 이것들의 상세를 굳이 논문에 명시하지는 않았다. 하지만 \(\operatorname{Inst} \{q_iS_jS_kR q_l\}\) 가 어떻게 정의될지 살펴보면 다음과 같다.

바뀐 부분은 첫번째 라인의 \(F(y, y')\) 와 3번째 라인의 \(F(z, y')\) 뿐이다.

명제 Des: 기계를 명제로✔

이전 챕터에서 기계의 m-설정표를 다음과 같은 표준형태로 표현했던 것을 기억하자.

각 퀸튜플이 \(\operatorname{Inst}\) 식이 된다.

\(\operatorname{Des}\) 는 Description 의 약어이다. 이것은 기계 \(\mathcal{M}\) 을 모든 Inst 식의 결합으로 완전하게 1차 논리 언어로 설명할 수 있다는 것이다. 가령 위 기계 \(\mathcal{M}\) 의 \(\operatorname{Des}(\mathcal{M} )\) 은 다음의 축약이다.

명제 Un, A✔

마지막 줄이 가장 이해하기 쉽다. 마지막 줄은 완전한 설정 \(s\) 에서 스퀘어 \(t\) 위의 기호가 \(0\) 이라는 것이라고 주장한다. 섹션 8 에서 튜링은 임의의 기계가 영원히 \(0\) 을 출력할지 판정하는 알고리즘이 존재하지 않음을 보였음을 기억하자.

튜링은 숫자기호 \(0\) 대신 기호 \(u\) 를 사용했음을 기억하자. 함의기호 이전 식들은 수 \(u\) 의 존재성을 주장하는데, \(u\) 는 첫번째 완전한 설정이기도 하고, 첫번째 스캔된 스퀘어이기도 하다. 첫번째 줄은 각 수 \(x\) 에 대하여 \(x\) 의 다음수 \(x'\) 의 존재성을 주장한다. 두번째 줄은 완전한 설정 \(u\) 에서(즉, \(0\) 에서) 테이프 위의 임의의 스퀘어 \(y\) 위의 기호는 \(S_0\), 즉, 빈칸임을 주장한다. 세번째 줄의 \(I(u, u)\) 는 완전한 설정 \(0\) 에서 스캔된 스퀘어가 \(0\)번째 것 임을 주장하고, \(K _{q_1}(u)\) 는 초기 m-설정을 \(q_1\) 으로 설정한다. 이들 뒤에 기계 자체를 설졍해주는 식인 \(\operatorname{Des}(\mathcal{M} )\) 이 따라온다.

이 논문의 개정판에서 튜링은 다음수의 유일성을 보장해주지 않은 것 때문에 \(y\) 가 \(x\) 보다 클 때 참이 되는 명제함수 \(G(x, y)\) 와 페아노 공리(Peano Axiom) \(P\) 를 대체할 식 \(\mathcal{Q}\) 을 정의했다. \(\mathcal{Q}\) 는 다음의 축약이다.

\(\mathcal{Q}\) 로 \(A(\mathcal{M})\) 을 더욱 단순하게 정의할 수 있게 된다. \(A(\mathcal{M} )\) 은 다음과 같다.

\(u\) 는 자유변수이지만 \(\operatorname{Un}(\mathcal{M} )\) 에서 종속변수가 된다. 이제 \(\operatorname{Un}(\mathcal{M} )\) 은 다음과 같이 된다. 명제 함수의 논의영역이 암묵적으로 자연수로 상정되어 있으므로 \(N(s)\) 와 \(N(t)\) 를 생략할 수 있다.

함의 기호 이전의 식들은 기계의 설명과 시작 조건에 대하여 설명해주며, 이것은 우리가 가정한 것이므로 참이다. 이들은 공리이다. 함의 기호 이후의 식은 기계가 언젠가 \(0\) 을 출력한다고 주장한다. 그러므로 \(\operatorname{Un}(\mathcal{M} )\) 은 기계가 \(0\) 을 출력할 때 참이 된다. 반면 기계가 영원히 \(1\) 을 출력하며 \(0\) 을 출력하지 않으면 거짓이 된다. 그렇다면 \(\operatorname{Un}(\mathcal{M} )\) 이 증명가능한지 결정해주는 알고리즘이 존재하는가? 그러하다면 임의의 기계가 \(0\) 을 출력할지 결정해주는 알고리즘이 존재하는 것이 되어 버린다.

두 가지 보조정리✔

남은 증명의 대부분은 순수하게 구문론적이고, 이들 명제 함수들(\(R,I,K,F\))의 정확한 의미를 따지는 일이 필요하지 않다.

이제 튜링은 \(\operatorname{Un}(\mathcal{M} )\) 이 증명가능한 것과 테이프 위에 \(S_1\) 이 나타나는 것이 동치임을 보이려 했다. 그는 증명을 두 보조정리로 나누었는데 다음의 \((a), (b)\) 가 그것이다.

\(u\) 는 \(0\), \(u'\) 는 \(1\), \(u''\) 는 \(2\), \(u ^{(n)}\) 는 \(n\) 을 나타낸다는 것을 기억하자. 튜링은 새로운 함수를 정의했다. 그러나 이들 함수는 정수를 반환하며, 명제 함수가 아니다.

함수 r, i, k✔

완전한 설정을 나타내는 \(n\), 테이프의 스퀘어를 나타내는 \(m\) 에 대하여 함수 \(r(n, m)\) 은 \(n\) 에서 \(m\) 위의 기호의 인덱스를 반환한다. 즉, 인덱스가 \(0\) 이면 빈칸, \(1\) 이면 \(0\), \(2\) 이면 \(1\) 이다. 그러므로 \(S _{r(n, m)}\) 은 완전한 설정 \(n\) 에서 스퀘어 \(m\) 위의 기호를 나타낸다. 튜링은 함수 \(r\) 을 명제함수 \(R\) 에 다음과 같이 적용했다. 그러나 명제함수에서는 엄밀하게 \(R _{S _{r(n, m)}}(u ^{(n)}, u ^{(m)})\) 라고 써야 한다.

함수 \(i(n)\) 은 완전한 설정 \(n\) 에서 스캔된 스퀘어의 수를 반환한다. 따라서 다음 술어는 항상 참이 된다.

함수 \(k(n)\) 은 완전한 설정 \(n\) 에서의 m-설정의 인덱스를 반환한다. 그래서 \(q _{k(n)}\) 은 완전한 설정 \(n\) 에서의 m-설정이다. 따라서 다음 술어는 항상 참이 된다.

명제 CC✔

완전한 설정 \(0\) 에서는 테이프 전체가 빈칸일 것이다. 완전한 설정 \(1\) 에서는 최대 \(1\) 개의 테이프에 빈칸이 아닌 기호가 있을 것이다. 그러므로 완전한 설정 \(n\) 에서는 최대 \(n\) 개의 기호가 테이프에 나타나있을 수 있다. 튜링은 완전한 설정 \(n\) 에서 스퀘어 \(0\) 에서부터 시작하는 이 기호열을 \(S _{r(n, 0)}, S _{r(n, 1)}, \dots, S _{r(n, n)}\) 이라고 표현한 것이다.

만약 \(n+1\) 개의 기호를 나열해도 문제 될 것은 없다. 기호 중 하나가 반드시 빈칸이 된다고 생각하면 되기 때문이다.

CC 는 complete configuration 의 약어이다. 첫번째 라인은 \(n+1\) 개의 스퀘어의 기호에 대응되는 함수의 결합이다. 두번째 라인은 스캔된 스퀘어 \(i(n)\) 와 m-설정 \(q _{k(n)}\) 을 뜻한다. 세번째 라인은 \(n\)번째 이후의 스퀘어가 빈칸이라는 뜻이다. 보편양화사로 지칭된 \(y\) 가 모든 스퀘어를 지칭하는 역할을 한다.

명제 CF✔

식 \(A(\mathcal{M} )\) 은 기계의 초기 설정(빈 테이프, m-설정 \(q_1\), 스캔된 스퀘어의 수가 \(0\)이라는 것)과 기계를 설명하는 \(\operatorname{Des}(\mathcal{M} )\) 을 포함한다. \(\operatorname{Des}(\mathcal{M} )\) 은 \(\operatorname{Inst}\) 식들로 구성된다. 각 \(\operatorname{Inst}\) 식들은 명령어가 어떻게 스캔된 스퀘어 위의 기호를 바꾸고, m-설정을 바꾸고, 스캔된 스퀘어를 바꿀지 명시한다.

튜링은 수학적 귀납법으로 \(CF_n\) 을 증명했다.

\(CC_n\) 에서 \(n = 0\) 이면 첫번째 라인은 아예 사라지고 \(I(u, u) \land K _{q_1}(u) \land (\forall y)R _{S_0}(u, y)\) 가 된다. 위 식은 이것을 재배열한 것이다.

\(A(\mathcal{M} )\) 의 식은 다음과 같으며, \(CC_0\) 이 갖는 \(R, I, K\) 를 그대로 가진다.

\(CF_n \implies CF _{n+1}\) 은 다음 식의 축약이다.

튜링은 함수 \(r,i,k\) 를 기반으로 정수 \(a,b,c,d\) 를 정의했다. 하지만 이 정의는 수정이 필요했다.

튜링은 논문의 개정판에서 완전한 설정 \(n\) 에 대하여 다음과 같이 정의했다.

• \(a = k(n)\), m-설정의 인덱스
• \(b = r(n, i(n))\), 스캔된 스퀘어 \(i(n)\) 의 기호의 인덱스
• \(c = k(n+1)\), 다음 m-설정의 인덱스
• \(d = r(n+1, i(n))\), 스퀘어 \(i(n)\) 의 새로운 기호의 인덱스

\(\operatorname{Des}\) 가 \(\operatorname{Inst}\) 항들의 결합이므로 \(\operatorname{Des}\) 가 참이면 \(\operatorname{Inst}\) 항들도 모두 참이고, 이 함의도 참이다. \(A(\mathcal{M} )\) 은 \(\operatorname{Des}\) 와 다른 식들의 결합이므로 다음이 성립한다.

그러므로 다음을 얻는다.

\(F ^{(n+1)}\) 는 공리로 가정한 것이므로 참이고, 참이므로 함의의 양쪽 식에 결합으로 추가할 수 있다.

사실 왼쪽 결합식에는 반드시 \(\mathcal{Q}\) 가 추가되어서 다음수의 유일성을 보장해주어야 한다. 그래서 다음과 같아야 한다.

이제 \(a,b,c,d\) 를 원래대로 되돌려보면 \(\operatorname{Inst}\) 식이 완전한 설정 \(n\) 을 \(n+1\) 으로 진행시키는 것임을 알 수 있다.

이는 다음과 동치이다.

그리고 완전한 설정 \(n\) 을 \(n+1\) 로 진행시키는 \(\operatorname{Inst}\) 식과 \(CC_n\) 의 결합이 \(CC _{n+1}\) 을 함의한다는 것은 매우 직관적이다. 이것을 증명할 수는 있지만 식들이 복잡하여 증명과정이 불필요하게 길어진다.

명제 \(X \implies (Y \implies Z)\) 가 \((X \implies Y) \implies (X \implies Z)\) 와 동치임을 보이는 것은 쉽다. 그러므로 다음이 성립한다.

술어 \(F\) 의 정의를 생각하면 \(F ^{(n+1)} \implies F ^{(n)}\) 임은 자명하다. 그러므로 다음이 성립한다.

두 괄호식 모두 \(CF_n\) 형식이다.

보조정리의 증명✔

귀납법으로 \(CF_n\) 이 증명가능하다는 결론을 얻었다. 그러나 아직 보조정리의 결론이 나온 것은 아니다. 이제 \(\operatorname{Un}(\mathcal{M} )\) 을 증명해야 한다.

\(N\) 은 완전한 설정의 수를, \(K\) 는 스퀘어를 나타낸다.

왜냐하면 결합의 임의의 항은 그 항을 함의하기 때문이다.

쉽게 말해서, 어떤 완전한 설정을 \(CC_N\) 이라고 두고, 그 완전한 설정에서 테이프 어딘가에 기호 \(S_1\) 이 나타난다고 가정했으므로 \(CC_N\) 은 반드시 \(R _{S_1}(u ^{(N)}, u ^{(K)})\) 을 가진다는 것이다.

두번째 식은 \(CF_N\) 이고, 이는 지금까지 증명한 사실에 의하여 증명가능하다.

지금까지 다룬 식은 자유변수 \(u\) 를 포함한다.

사실, \(0\) 이 나타나는 스퀘어 \(K\) 는 절대로 완전한 설정 \(N\) 보다 클 수 없다.

함수 \(R\) 은 \(u\) 부터 \(u ^{(N')}\) 까지의 존재성이 보장되지 않아도 되고, 오직 \(u ^{(N)}\) 와 \(u ^{(K)}\) 의 존재성만 필요로 한다.

식에서 변수의 표기만 치환할 수 있으므로 다음을 얻는다.

그런데 이는 \(\operatorname{Un}(\mathcal{M} )\) 의 정의와 같다.

이로써 보조정리 2 의 증명은 허무하게 끝난다.

이제 이로써 \(\operatorname{Un}(\mathcal{M} )\) 과 \(\mathcal{M}\) 의 어떤 완전한 설정에서 \(S_1\) 이 나타나는 것이 동치라는 사실을 얻었다.

Entscheidungsproblem 의 증명✔

만약 \(\operatorname{Un}(\mathcal{M} )\) 이 좀 더 단순하면 결정 절차에 의해 분석가능하다. \(\operatorname{Un}(\mathcal{M} )\) 은 \(A(\mathcal{M} )\) 을 갖는데, \(A(\mathcal{M} )\) 은 \(\mathcal{Q}\) 와 \(\operatorname{Des}(\mathcal{M} )\) 를 갖는다. \(\operatorname{Des}(\mathcal{M} )\) 는 \(\operatorname{Inst}\) 들을 갖는데, \(\operatorname{Inst}\) 는 5개의 보편 양화사를 갖고, \(\mathcal{Q}\) 는 3개의 보편 양화사와 1개의 존재 양화사를 가지며, \(A(\mathcal{M} )\) 은 또 다른 보편 양화사를 갖고 \(\operatorname{Un}(\mathcal{M} )\) 은 3개의 존재 양화사를 갖는다.

이 논문이 쓰여질 당시 결정 절차를 정립하려는 많은 노력과 시도들이 있었다. 수학자들은 먼저 단순한 경우에서부터 시작했다. 일반적으로 결정절차를 적용할 때 식을 프리넥스 표준형(prenex normal form)으로 변환했다. 이 형태는 모든 양화사가 식의 앞에 나오는 형태이다. 1928년에는 \(\exists ^{*}\forall ^{*}\) 로 시작하는 프리넥스 표준형의 결정절차가 밝혀졌다. \(\exists ^{*}\forall ^{*}\) 는 임의의 숫자의 존재 양화사와 임의의 숫자의 보편 양화사라는 뜻이다. 1928년에는 \(\exists ^{*}\forall \exists ^{*}\) 의 결정절차가 밝혀졌다. 이것은 임의의 존재 양화사와 1개의 보편양화사와 임의의 존재 양화사이다. 1932년에는 괴델이 \(\exists ^{*}\forall ^{2}\exists ^{*}\) 의 결정절차를 밝혀냈다. 이것은 임의의 존재 양화사와 2개의 보편양화사와 임의의 존재 양화사이다.

괴델은 \(\exists ^{*}\forall ^{2}\exists ^{*}\) 의 결정절차를 보이고, \(\forall ^{2}\exists ^{*}\) 까지도 보였다. 처치와 튜링의 증명 이전까지 일반적 결정 절차가 존재한다고 여겨졌지만, 튜링의 증명 이후에 \(\forall ^{3}\exists ^{*}\) 이 결정불가능하다는 것이 증명되었다.

튜링은 \(\forall \exists \forall \exists ^{6}\) 형태의 프리넥스 표준형은 결정 절차를 갖지 않는다는 것을 증명한 것이다.

즉, \(\forall \exists \forall \exists ^{4}\) 까지도 결정절차를 갖지 않는다는 것이다. 이후의 연구를 통하여 수학자들은 \(\exists \land \forall \exists \forall\) 도 결정불가능하고, \(\forall \exists \forall\) 도 일반적인 결정절차를 갖지 않는다는 것을 밝혀내었다.

수학자들은 이렇게 한계에 대하여 밝혀내기도 한다. 유클리드의 다섯번째 공리를 나머지 네 공리로 증명 불가능하다는 것, \(2\) 보다 큰 \(n\) 에 대한 \(x ^{n} + y ^{n} = z ^{n}\) 이 해를 갖지 않는다는 것, 산술체계의 무모순성을 체계 내에서 해결 불가능하다는 것과 같이 이제 1차 논리에 일반적 결정 절차가 존재하지 않는다는 것이 증명되었다.

모든 것이 튜링 기계인가?✔

튜링 기계의 재정의✔

튜링은 그의 기계를 컴퓨터의 설계도로써 만든 것이 아니라 단지 1차 논리에서 일반적 결정 절차가 존재하지 않는다는 것을 증명하기 위하여 만든 것이다. 튜링 기계를 튜링의 증명이 아닌 다른 목적으로 사용하기 위해서는 튜링 기계를 재정의해야 했다. 왜냐하면 튜링 기계는 단지 \(0\) 과 \(1\) 사이의 어떤 실수를 무한히 계산하기만 했기 때문이다. 물론 이것이 컴퓨터의 본질이기는 하다. 컴퓨터는 단지 데이터를 계산하고 메모리에 수열을 읽거나 써내려가는 기계에 불과하다.

컴퓨터 프로그래밍과 수학에서 매우 중요한 계산작업은 함수를 계산하는 것이다. 이를 위해서는 수를 입력받고 계산결과를 출력할 수 있어야 한다. 튜링은 섹션 10 에서 산술적 함수(자연수를 입력받고 출력하는 함수)를 \(0\) 으로 구분되는 연속적인 \(1\) 을 출력함으로써 만들어보였다.

스티븐 클레이니(Stephen Cole Kleene)는 튜링의 기술이 자연수의 진부분집합에서만 타당한 부분함수에서는 작동하지 않는다는 것을 지적했다. 그는 튜링 기계를 재정의했다. 그의 튜링 기계는 여전히 기호를 읽고, 기호를 쓰고, 테이프 위를 왼쪽이나 오른쪽으로 움직였다. 하지만 이것은 오직 하나의 수직 기호 \(|\) 에만 한정되었다. 이것을 틱(tick) 마크라고 한다. 틱 마크가 하나면 \(0\) 을, 2개면 \(1\) 을 나타내었다. 자연수는 틱 기호의 나열로 표현되고, 빈칸으로 구분된다.

보편 기계의 핵심요소는 프로그래밍가능성이다. 컴퓨터에 명령어열을 입력하고 결과를 출력받을 방법이 반드시 존재해야 한다. 현대의 컴퓨터에서는 명령어열이 바이트로 메모리에 입력된다.

튜링 완전✔

컴퓨터 프로그래밍 언어의 문법이 튜링 기계를 흉내낼 수 있다면 그 언어를 튜링 완전하다고 한다. 가령, HTML 은 튜링 불완전하고 자바스크립트는 튜링 완전하다. 임의의 튜링 완전 언어는 다른 튜링 완전 언어를 모방할 수 있다.

기계의 한계✔

튜링 기계는 효과적인 계산가능성의 기본 요건을 정립했을 뿐만 아니라 한계도 정립했다. 즉, 임의의 컴퓨터나 프로그래밍 언어는 튜링 기계보다 강력하지 않다. 이는 정지 문제(halting problem)를 해결할 컴퓨터나 프로그래밍 언어는 존재하지 않는다는 것이다. 그렇다면 이는 다른 컴퓨터 프로그램의 궁극적인 운명을 판정할 수 있는 컴퓨터나 프로그래밍 언어가 존재하지 않는다는 것이다. 우리가 할 수 있는 일은 더 나은 기계나 언어를 만드는 것이 아니라 더 빠른 기계나 언어를 만드는 일에 불과하다.

가용성과 한계에서 계산의 보편성은 어떤 종류의 데이터 처리 활동과도 본질적으로 같은 것 같다. 이 한계는 열역학 법칙이 지배하는 자연 세계의 뿌리 깊은 한계인 것 같다. 그러면 계산적인, 또는 논리적인 연산을 하는 자연적 메카니즘의 의미는 무엇인가? 이 질문은 두 가지 자연적 메카니즘, 즉, 인간의 마음과 우주 그 자체를 고려할 때 매우 심오하다.

엄격하게 말해서 튜링 논제는 오직 튜링 기계와 기계적인 알고리즘의 동등성만 말한다.

뇌는 튜링 기계이다✔

그런데 혹시 어떤 미스테리한 물리적 메커니즘이 튜링 기계가 흉내낼 수 없는 계산적 연산을 수행할 수 있을지도 모른다. 튜링 기계가 정말 인간의 마음과 우주를 이해하는데에 도움이 되는가?

McCulloch 는 뇌에 대한 이론을 공식화했고 이때 Pitts 의 수리논리학에 대한 지식이 적절하게 필요했다. 둘은 논문 『A Logical Calculus of Ideas Immanent in Nervous Activity』 을 썼다. 신경계가 뉴런으로 구성되어 있고 뉴런이 임계값까지 자극되면 촉발되는 스위치와 비슷하다는 사실이 밝혀져 있었다. 이 둘에게 뉴런은 논리 함수였고, 그들은 뉴런을 명제 함수로 모델링했다. 전통적인 논리학에 있지 않은 핵심적인 요소는 입력과 출력 사이의 시간 지연이었다. 이 시간은 뉴런이 순환적 패턴을 조직하게 하여 신호가 네트워크를 순환하며 계속 활성화되어 있게 해주었다. MaCulloch-Pitts 의 논문은 이 단순화된 모델의 공리를 정의하고 몇개의 정리를 증명했다. 그들은 논문에서 이렇게 말했다.

즉, 튜링 계산가능성은 뇌의 신경세포가 형성한 신경망, 더 일반적으로 임의의 유기체가 형성한 임의의 생물학적 구조에 의한 계산가능성과 동등하다. 이후 MaCulloch 는 튜링과의 연결성을 더욱 명시적으로 만들었고, 신경생리학(neurophysiology)에 대한 이론을 개발했다.

이후 MaCulloch 은 "Pitts 와 나는 뇌가 튜링 기계임을 보였고, 임의의 튜링 기계는 뉴런으로 만들어질 수 있었다" 라고 말했다.

이로써 뇌가 무한한 일을 하지 않는 이상 그것을 기계화할 수 있다는 것이 밝혀졌다. 그러나 명백하게 인간이 무한의 영역에서 살아가고 실질적인 무한을 다룰 수 있는 신적인 존재라고 보여지지 않는다. 인간은 유한하고, 인간의 뇌도 무한의 영역에 존재하지 않는, 물리적 한계에 갇혀있는 신경세포들이 형성한 1.5kg 짜리 작은 신경망에 불과하다. 그렇다면 뇌가 하는 일은 비가산적이지 않고, 괴델수에 의하여 산술화되어 \(\N\) 안으로 사상될 수 있다. 그러면 무엇인가? 페아노 산술 \(\mathsf{PA}\) 의 증명 한계를 넘어선 논증에 대한 일도 모두 뇌들이 했는데, 그것들은 모두 어떤 방식으로든 유한한 생각을 진행하는 유한한 뇌의 신경망의 계산체계 안에서 이루어질 수 있었던 것이다.

뇌가 기계화가능하면 인간의 뇌의 구조가 지닌 계산능력보다 뛰어난 뇌 구조 또한 형성될 수 있다.

위너(Norbert Wiener)는 기계나 생명체나 사회 체계의 피드백과 커뮤니케이션을 포함하는 새로운 용어인 사이버네틱스(cybernetics) 라는 단어를 만들었다. 그의 책 Cybernetics 의 챕터 5 는 디지털 컴퓨터의 스위칭 메커니즘과 McCulloch 의 뇌의 모델을 비교한다.

두 챕터 이후에 위너는 "뇌와 계산 기계에 공통점이 많다는 발견은 정신병리학(psychopathology)과 정신과(psychiatric)에 새로운 접근법을 제시한다" 고 말했다.

McCulloch 와 Pitts 의 논문은 폰 노이만에게 영향을 주었다. 폰 노이만은 컴퓨터 스위칭 메커니즘에 대하여 이렇게 말했다. "모든 디지털 컴퓨팅 기기는 이산 평형을 지닌 요소를 갖는다. 이 요소는 무기한으로 존재할 수 있는 두 개 이상의 구별되는 상태를 포함한다." 그는 McCulloch 와 Pitts 의 논문을 인용하며 말했다. "고등 동물의 뉴런은 분명하게 이런 종류의 요소이다."

폰 노이만은 생명체와 기계의 연결점을 탐구하며 살아있는 특성을 나타내는 매커니즘을 위한 단어로 오토마톤(automaton)을 사용했다. 그에게 오토마톤이란 입력, 출력, 그리고 그 중간에 어떤 종류의 처리를 갖는 모든 것이었다. 그는 1948년 9월 발표를 통하여 인간의 뇌와 그 당시의 컴퓨터를 크기, 속도, 스위치들, 그리고 에너지 소모의 관점에서 비교했다. 그는 새로운 종류의 논리를 개발해야 할 필요성이 있다는 것을 알아챘고, 새로운 종류의 관심거리가 될 것이 있다는 것을 생각했다. 그것은 자기복제 오토마타(self-reproducing automata)였다.

그는 기계가 자기 자신의 레플리카를 생성하는 것을 제한하는 어떤 종류의 알려지지 않은 법칙이 존재하는지 생각했다. 오토마타와 튜링기계에 대한 연구가 계속되면서 『Automata Studies』 가 클로드 섀넌과 인공지능의 선구자 존 매카시에 의하여 출판되었다. 이 책은 폰 노이만, 스테판 클레이니, 인공지능의 선구자 마빈 민스키의 논문을 포함했고 섀넌과 마틴 데이비스의 튜링 기계에 대한 초기 논문을 포함했다.

자기복제 오토마타의 그의 초기 연구에서 폰 노이만은 키네마틱 오토마타(kinematic automata)를 구상한 적이 있었다. 폰 노이만은 이후에 더욱 간단한 모델인 셀룰러 오토마타(cellular automata)를 연구하기로 했다. 셀룰러 오토마타는 세포와 닮은 수학적 아이디어이다. 셀룰러 오토마타가 잠재적으로 다양한 차원에 존재할 수 있었지만, 대부분의 연구는 2차원 그리드에서 이루어졌다. 그리드의 각 세포는 그것의 이웃에게 영향을 받는다. 연속적인 이동과 세대를 통해 세포는 정해진 규칙을 따라 상태를 바꾼다. 간단한 규칙도 복잡한 행동으로 이어진다. 폰 노이만은 29개의 상태를 갖는 세포로 보편 기계를 구현할 수 있음을 증명했다.

영국 수학자 콘웨이가 Game of Life 라고 부르는 셀룰러 오토마타를 설계했을 때 셀룰러 오토마타는 학술적 경계를 넘어갔다. 간단한 규칙에도 Game of Life 는 복잡한 패턴을 보여주었고, 자식을 낳는 패턴도 보여주었으며, 튜링기계를 구축하기도 했다. Game of Life 는 튜링 완전했다.

우주는 양자 컴퓨터이다✔

콘라드 추제도 셀룰러 오토마타를 연구했다. 그는 1969년에 계산 공간이라고 번역되는 책을 출판했는데 이 책이 디지털 물리학의 선구자의 역할을 했다. 디지털 물리학은 우주의 법칙과 동작을 계산가능성으로 해석한다.

물리학의 법칙은 연속적이라고 여겨져왔다. 거리, 질량, 에너티는 실수로 기술되었고 미분방정식으로 다루어졌다. 양자론의 어떤 측면은 우주의 기반 구조가 이산적이고 디지털일 수 있다는 것을 제안했고, 현실의 연속적 특성은 환상에 불과할 것임을 암시했다. 추제는 자연이 디지털인지, 아날로그인지, 둘 다인지 질문했다. 디지털의 관점에서 물리학 법칙을 탐구하기 위하여 추제는 셀룰러 오토마타의 규칙으로 다루어지는 디지털 입자(digital particle)을 만들었다. 그의 책은 우주를 모델하기 위하여 디지털 물리학을 사용했다.

우주를 컴퓨터라고 상상하기는 힘들다. 그러나 빅뱅의 바로 직후에는 우주는 매우 균등하고 단순했다. 그리고 점차 복잡한 입자가 생성되었다. 이 초기 우주의 단순성은 셀룰러 오토마타를 연상시킨다.

우주의 계산 모델은 섀넌의 통신 이론에 의존한다. 정보를 측정하기 위한 엔트로피의 개념의 사용은 통신과 열역학적 사이의 단단한 결속을 만들어냈다.

It from bit 는 존재가 정보에서 기인한다는 말이다. 이것은 우주가 본질적으로 정보에 불과하다는 것이다. 그리고 정보는 우리가 관측하고 측정할 때 존재한다. 실재는 그 다음에 오는 것이다. 만약 실재가 존재의 근원이었다면, 고전역학에서 시간과 속도를 알 때 존재가 어디에 있을지 추측하는 것이 가능하다고 말하는 것이 사실이었을 것이다. 그러나 이중슬릿 실험으로 시간, 속도, 위치를 통하여 실재를 예측하는 것이 불가능하다는 것이 밝혀졌다.

고전역학으로 말하면, 즉, 실재가 존재의 근원이라는 관점에서 말하면, 달은 실재로 존재한다. 그런데 현대물리학, 즉 양자역학에서는 달이 실재로 존재하는 것이 아니라 관측된 것에 불과하다. 즉, 사물은 실재하는 게 아니라 정보에 불과하다. 달을 관측하기 전에 달이 존재할 수도 있고, 존재하지 않을 수도 있다.

그러면 존재는 어디에서 왔는가? 양자역학에 따르면 존재의 근원은 실재가 아니라 정보이고, 우주의 본질은 정보이다. 정보는 관측, 측정을 통해 얻어진다. 그러므로 측정 자체가 존재를 만든다. 우주에 실체는 없고 질문과 답, 측정과 정보만 있을 뿐이다.(쉽게 말해, 성경적으로 말해보면, 하나님이 빛이 있으라는 정보를 주시니 빛이 존재했고, 믿음으로 기도하니 산도 들려서 바다에 떨어졌다.)

정보로부터 만들어진 우주를 제안하면서도 휠러는 어떤 타입의 기계 종류의 우주의 개념은 거부했다. 왜냐하면 이런 우주는 암묵적으로나 명시적으로나 결국 우주가 무한히 다양하고 무한한 수로 존재한다는 것을 밝혀낼 어떤 초기계(supermachine)를 가정해야 했기 때문이다.

양자 컴퓨팅의 선구자인 데이비드 도이치는 다중 우주에 대하여 설명했다. 우리가 입자와 파동의 이중성에서 느끼는 모순은 실제로는 다중 세계의 간섭이라는 것이다. 이는 우리가 아는 우주는 완전한 다중우주(multiverse)의 한 가지 가능성에 불과하다는 설명이다.

그의 1997년도 책 『The Fabric of Reality』 에서 도이치는 네 가지 요소를 종합하여 우주의 본질을 설명하려 했다.

• 과학철학자 칼 포퍼에 의하여 특성이 부여되는 인식론
• 휴 에버렛의 다중 세계 해석의 구조의 양자물리학
• 다윈에 의해 설명되는 진화
• 튜링의 계산

가상 현실 생성자에 관한 논의에서 도이치는 튜링 원리를 개발했다. 처음에는, 튜링 원리는 계산을 수행하는 메커니즘에 대한 것처럼 보인다. "임의의 물리적으로 존재 가능한 대상이 수행할 수 있는 임의의 계산을 포함하는 추상 보편 컴퓨터가 존재한다." 도이치는 이 컴퓨터가 모든 종류의 물리적 절차를 수행해낼 수 있다는 것을 확인했다. 그는 이런 유의 계산이 가상 현실 우주를 생성하는 것과 동등하다는 것을 보였다. 튜링 원리는 더 강한 버전으로 발달하였다. "모든 물리적으로 가능한 환경을 포함하는 가상 현실 생성자를 만들 수 있다." 그리고 이 가상 현실 생성자는 명백하게 우리가 사는 우주 또한 포함한다.

양자 역학과 MIT 기계공학 교수 세스 로이드(Seth Lloyd)는 양자 물리학을 다중 세계의 관점이 아니라 "이상함" 의 관점에서 설명하기를 선호했다. 그는 우주와 그것의 부분을 계산과 정보의 관점에서 설명했다. "빅뱅은 또한 Bit Bang 이다." 그러나 로이드는 우주를 튜링 기계로 모델링하는 아이디어를 거부했다. "우주는 근본적으로 양자 역학적이고, 전통적인 디지털 컴퓨터는 양자 역학적 시스템을 흉내내기기 힘들다." 이것이 그가 양자 컴퓨터를 더 적합하다고 생각한 이유이다.

양자 컴퓨터가 전통적인 튜링 기계 보다 더 나은 한 가지는 양자적 절차로 진짜 난수를 생성해낼 수 있는 것이다.

셀룰러 오토마타는 스테판 울프람의 2002년 책 『A New Kind of Science』 의 연구에서 우주의 물리적 법칙의 모델로써 다시 등장했다. 울프람은 셀룰러 오토마타가 단순한 규칙으로 거대한 복잡도를 보여주는 점을 관찰하면서 영감을 얻었다. 그는 그의 오토마타를 튜링 기계의 보편성과 긴밀하게 연결시켰고, 그것이 물리적 절차를 어떻게 모델링할 수 있는지 보여주었다. 그는 그의 체계로 양자 역학을 도입하지는 않았지만 그는 그것이 필요하지 않다고 말했다. 왜냐하면 "나의 강력한 예감은 내가 논의한 프로그램의 종류들이 결국 양자 이론의 모든 주요한 특징은 아니더라도 많은 것을 실제로 보여줄 것이라는 것이다."

마음도 튜링 기계이다✔

『A New Kind of Science』 에서 그는 그가 정의한 계산적 동등성의 원리에서 계산적 보편성을 찾아내었다.

우주가 디지털 컴퓨터나 양자 컴퓨터에 의하여 계산불가능한 특성을 보이지 않는다는 확신이 생기면 우주의 어떤 부분이든지 이 규칙에 예외가 되지 않는다. 가령, 생명도 계산가능한 우주의 한 부분이다. 그러므로 생명의 가장 미스테리한 부분인 인간의 마음도 마찬가지로 계산가능하다.

지금까지 철학자, 생물학자, 심리학자, 그리고 평범한 사람들까지 인간의 마음의 본질과 씨름했다. 우리가 지금까지 육체적 기능의 대부분이 물리적이고 화학적인 기계적인 절차의 결과임을 인지하고 받아들였지만, 우리의 마음까지도 그와 같은 메커니즘을 갖는다는 것을 받아들일 준비는 되어 있지 않았었다. 마음은, 우리가 생각하기에, 무언가 특별한 것이었다. 뇌가 마음과 관련이 있다는 것은 분명하지만, 그것이 그 안에서 일어나는 모든 것을 제대로 설명할 수는 없다.

마음/몸 이원론(mind/body dualism)은 데카르트의 1641년 책 『Meditationes de Prima Philosophia』 (제1철학에 관한 성찰)에서 나왔다. 그는 대부분의 인간의 몸이 근본적으로 기계이지만, 마음은 다르게 작동한다고 믿었다.

1940년, 이원론이 공격받기 시작했다. 신경과학자, 컴퓨터 과학자 McCulloch, Pitts 는 그들의 1943년 논문에 있는 뉴런에 관한 질문을 해결했다. 뇌는 계산을 수행하기에 적합한 구조이고, 그러므로 McCulloch 과 Pitts 는 논리적으로 이해될 수 있는 임의의 충분히 유한한 것은 신경망으로 수행될 수 있다. 그들은 이원론을 끝냈다.

몇 년 후 철학자 Gilbert Ryle 은 그의 1949년 책 『The Concept of Mind』 에서 McCulloch 과 Pitts 의 논문에 대한 언급 없이 더 강한 케이스를 만들어서 이원론을 공격했다. 오늘날에는 이원론은 명백하게 저물었다. 철학적으로나 신경생물학적으로나 마음에 대하여 연구하는 연구자들은 마음을 인간의 육체의 물리적 작동의 결과로, 특히 뇌와 신경계의 결과로 본다.

이원론의 몰락은 계산과 알고리즘에 대한 이해가 높아지는 것과 함께했다. 튜링 기계는 인간 컴퓨터의 모델로 여겨졌다. 기계와 마음의 이 연결은 자동 계산이 시작될 때부터 있어왔다. 인공지능의 개념을 처음 탐구한 사람도 튜링이다.

마음은 물리적 뇌의 자연스러운 표상으로 보여지며, 더 이상 초자연적인 어떤 것으로 여겨지지 않는다. 이 결론이 감정적으로 받아들이기 힘든 것처럼 보이지만, 결국 우리는 이 결론을 피할 수 없다. 마음도 근본적으로 튜링 기계의 능력과 한계를 지니고 있는 튜링 기계에 불과하다. 그러므로 이론적으로 인공 마음을 만들 수 있다.

기계도 의식을 가질 수 있다✔

철학자 Daniel Dennett 는 이렇게 말했다. "튜링은 생각이 어떻게 존재할 수 있는가 라고 묻는 칸트의 질문을 공학적 질문으로 대체할 수 있도록 기본적인 조치를 취했다. 생각을 어떻게 존재하게 할 수 있는지 생각해보자."

뇌가 컴퓨터라는 제안과 튜링 테스트에서 우리를 가장 괴롭히는 것은 의식이다. 의식은 우리 머리 속에서 잔소리하는 1인칭 목소리이다.

그러나 의식은 파악하기 힘들고 불분명하다. 우리 중 대부분은 우리가 깨어있는 시간 동안 의식의 내적 독백이 계속된다고 주장할 것이다. 그러나 이 특징 때문에 이것이 작동하지 않을 때 의식은 보이지 않는다. 우리 중 대부분은 다른 사람이 우리와 같은 의식을 갖고 있다는 가정을 하며 그들과 상호작용하지만, 그들이 정말로 그러한지는 확신할 수 없고, 다른 사람에게 우리 자신의 의식의 존재를 납득시키기 위하여 어떻게 해야 하는지 알 수 없다.

뇌가 어떻게 자기 인식을 만들어내는지 판정하는 일은 철학자 데이비드 차머스에 의하면 뇌가 어떻게 장기들의 센서의 입출력과 상호작용하는지 밝혀내는 일보다 어려운 일이다.

튜링 테스트는 지능이 무엇인지 밝혀내기 위하여 암묵적으로 누군가 또는 어떤 것의 내부의 중앙 처리 장치 안에서 어떤 일이 일어나는지 아는 것이 불필요하다는 행동주의자들의 스탠스를 취한다. 그러나 우리가 기계를 인간과 구분할 수 없다고 하더라도 기계와 다른 것을 구분하기를 원한다.

우리가 컴퓨터에 대하여 안다고 생각하는 모든 것은 우리에게 그것들이 실제로 단지 규칙을 따르는 것일 뿐임을 말해준다. 그것들은 그것들이 우리 인간이 그러한 것처럼 무엇을 하는지 알지 못한다. 이 문제는 존 설이 말한 중국어 방 문제이다. 중국어를 모르는 사람이 중국어 대화를 알려주는 책을 가지고 질문 내용을 전혀 이해하지 못한채 튜링 테스트를 통과할 수 있다. 그러면 튜링 테스트를 진행하는 사람은 그 사람이 실제로 중국어를 이해한다고 착각한다는 문제이다.

큰 문제는 컴퓨터가 오직 문법을 다룬다는 것이다. 반면 사람은 오직 의미를 다룬다. 설에게 이것은 디지털 컴퓨터가 얼마나 정교하든간에 인간이 하는 것과 동일한 방식을 이해하지 못한다는 것이었다.

펜로즈는 마음이 단순한 계산 기관 이상이라고 확신했다. 그의 책 『The Emperor's New Mind』 (1989) 와 『Shadows of the Mind』 (1994) 에서 그는 의식이 계산 너머에 있는 것이고 뇌 속의 어떤 종류의 양자적 절차가 튜링 기계의 능력을 초월하는 비알고리즘적 일들을 수행한다고 추측했다.

펜로즈는 괴델의 불완전성 정리가 문제를 드러낸다는 것임을 알아냈다. 우리 인간은 괴델이 도출해낸 증명불가능하지만 참인 사실을 이해한다. 그러나 어떠한 계산도 그 진실이 진실이라는 것을 증명하지 못한다. 왜냐하면 그것은 공리로부터 도출되지 않았기 때문이다. 이는 새로운 발견이 아니었다. Ernest Nagel 과 James Newman 은 그들의 책 『Godel's Proof』 에서도 같은 주장을 했고, 철학자 John Randolph Lucas 도 그의 유명한 에세이 "Minds, Machines and Godel"(1961) 에서도 같은 주장을 했다. 이것은 기계가 공리적 수학을 수행하는데에는 탁월하지만 그것들이 공리 바깥에 있는 사실을 이해하기 위한 상위수학(metamathematic)을 수행할 수는 없다는 주장으로 보인다.

(실제로 인간과 마음이 튜링기계라면 결정불가능한 괴델 문장이나 산술의 무모순성 같은 증명 불가능한 사실을 어떻게 메타 논증에 의하여 증명할 수 있었는가? 이 메타 체계적 증명에 관한 내용을 \(\mathsf{PA}\) 의 서수 분석에서 엄밀하게 알아본다.)

Diniel Dennett 은 다르게 생각했다. 그는 다른 누구보다 더 마음의 묘사를 하기 위하여 철학자의 생각을 과학자의 경험주의와 결합한 사람이다. 그는 계산가능성의 개념을 진화에 대한 이해와 방대한 현대 신경생물학의 연구와 결합시켰다. 뇌와 마음에 대한 그의 시각은 튜링 기계를 위한 매체가 될 것 같지 않다. 그는 뇌가 신경체계의 한 부분이고 몸의 한 부분이며 분리가 있을 수 없다고 보았다. 인간이 흥미로운 생각을 하면, 심장은 더 빨리 뛰어서 산소를 뇌에 더 보낸다. 뇌는 눈, 귀, 다른 기관으로부터 몸을 통하여 현실 세계로부터 오는 자극들을 전달받는다.

뇌는 선형 처리 체계가 아니고, 어마어마하게 병렬하되고 탈중앙화(decentralization)된 체계이다. Dennett 은 대신 감각기관의 부분적인 입력, 시각 데이터, 단어가 완성되지 않고 불완전하게 남아있는 마음의 여러 모델을 제시했다. 만약 뇌가 컴퓨터였다면 어떠한 합리적인 엔지니어도 이런 식으로 컴퓨터를 설계하지는 않았을 것이다.

또한, 우리가 의식에 대하여 생각하는 것은 병렬 구조의 꼭대기에서 일어나는 연속 활동이다.(사실 이 주장은 『특이점이 온다』 에서도 대뇌피질에 관련시켜서 똑같이 주장된다.) 그는 이렇게 정했다.

의식은 최소한 자기 자신에게 말하는 것이고, 이는 언어의 문화적 구성물을 필요로 한다.

명백히 인간의 마음을 모방하기 위해 컴퓨터를 설계하는 것은 별 의미가 없다. 그것은 엄청난 양의 입력을 필요로 할 것이고, 수년의 교육과 학습 없이는 만족스럽게 작동하지 않을 것이다. 그럼에도 불구하고, 제한이 없는 튜링 테스트를 통과할 수 있는 컴퓨터를 이론적으로 만들 수 있는가? 그리고 그러한 컴퓨터는 의식을 갖는 것일까? Dennett 은 두 질문 모두에 그렇다 라는 대답을 했다.

결정불가능성이 자유의지이다✔

당신이 선호하는 뇌의 기계론적 관점에 상관없이, 기계가 우리의 의견을 결정한다. 그러면 자유의지는 어떻게 되었는가?

기계적 우주에서 사라지는 자유의지는 사실 오래전부터 모든 입자의 움직임이 엄격한 결정적인 법칙에 의하여 규정된다는 것이 밝혀진 시점에서 예견되었다. 라플라스는 그의 책 『Essai Philosophique sur les Probabilites』 (1814) 에서 이렇게 말했다.

이 개념은 라플라스의 악마로 알려져있다. 우리의 뇌의 세포를 구성하는 입자를 포함하는 우주의 모든 입자가 빅뱅 때로부터 그 움직임이 결정되었고, 이 입자들은 이미 결정된 패턴을 따라 움직인다는 결론을 피할 수 없어 보인다.

물론 라플라스의 악마는 존재하지 않는다. 모든 정보를 저장하려면 우주의 모든 입자를 추적할 수 있어야 하고, 이를 위해서는 우주보다 큰 컴퓨터가 필요하다. 불확정성 원리는 입자의 위치와 운동량을 동시에 알 수 없음을 말해준다. 수학적으로 입자들의 충돌의 결과를 예측하는 것은 다체문제(many-body problem)로 알려져있고, 심지어 삼체 문제를 해결하는 알고리즘도 생각하기 어렵다. 푸앵카레는 삼체 문제의 일반해는 존재하지 않음을 밝혔는데, 이는 카오스 이론을 시작시켰다.

우주가 정말 튜링 기계라면, 우리가 현재의 완전한 설정을 알고 있고 기계를 통제하는 모든 설정표를 알고 있어도, 정지 문제에 의하여 우리는 실제로 프로그램을 실행시키지 않고서는 우주가 어디로 가는지 예측할 수 없다. 그러므로 본질적으로 결정불가능성(undecidability)이 자유의지이다. 세스 로이드는 정지문제에 대하여 이렇게 말했다.

데이비드 도이치는 뇌가 전통적인 비양자 컴퓨터인지 양자 컴퓨터인지 신중하게 생각하며 이렇게 말했다.

그는 "계산의 튜링의 설명은 원칙적으로 의식이나 자유의지 같은 정신적 속성에 대하여 물리적으로 미래에 설명할 여지를 남기지 않은 것 같다" 고 말했다. 그러나 양자 물리학의 다중 세계 해석에서는 세계가 끊임없이 분기하며, 이 세계에서 당신이 이 선택을 하지만 다른 세계에서는 당신이 다른 선택을 한다. 이것이 자유의지가 아니면 무엇인가? 도이치는 이렇게 결론내렸다. "다중우주의 관점에서 이해된다면, 튜링의 계산에 대한 개념은 인간의 가치로부터 동떨어지지 않은 것처럼 보이고, 그것이 인간의 자유의지 같은 속성을 이해하는데에 장애물이 되지 않아보인다."

울프람이 셀룰러 오토마타에서 나오는 복잡한 구조에 대하여 연구하기 시작했을 때, 그는 결과를 예측하는 방법을 찾으려 했고, 세대를 통하여 지름길을 만드려 했다. 그러나 그는 이렇게 말했다. "체계의 진화의 계산 단계를 그대로 따라가는 방법 외에 체계를 예측하는 방법은 존재하지 않았다. 그러므로 그것의 진화 절차의 지름길을 마련하는 일반적인 방법은 없다." 이 예측불가능성은 체계가 자유의지를 행사할 수 있게 해주었고, 울프람은 심지어 셀룰러 오토마타의 행동이 자유의지와 비슷하다는 다이어그램까지 제공했다.

이 결과는 튜링의 논문 \(\S 8\) 에서 살펴본 정지 문제의 결론과도 같다. 즉, 우주와 인간의 뇌가 설령 단순한 규칙을 기반으로 하여 복잡한 구조를 얻게 된 셀룰러 오토마타이거나 튜링 기계여도, 우리는 그 규칙을 기반으로 미래를 예측할 수 없다. 그러므로 미래는 존재하지 않는다. 프로그램의 코드를 실제로 실행해보기 전까지. 미래는 아직 쓰여지지 않았다. 누구도 미래를 미리 가지고 있지 않다. 우리의 미래는 우리가 만드는 것이다.