This reposity has been abandoned. Please see https://ccss17.github.io/ProgrammerBase/readme/
이 레포지토리는 더 이상 관리되지 않습니다. https://ccss17.github.io/ProgrammerBase/readme/ 에 방문해주세요.
참고/출처 : 『컴퓨터과학이 여는 세계』, 이광근
아래의 내용은 위 서적을 기반으로 작성되었습니다.
1900년대 초 수학자들은 수학의 기초를 위하여 수학의 공리체계를 만들려고 했다는 것을 이미 언급했습니다. 그 중에서 힐베르트도 비유클리드 기하학, 유클리드 기하학, 해석학, 수론 등 모든 수학 체계의 정합성을 결정할 수 있는 규칙 체계를 만들려 했습니다. 힐베르트는 공리 체계가 다음 조건을 만족해야 한다고 말했습니다. 이것이 힐베르트의 프로그램입니다.
-
정합성 : 어떤 명제가 증명되면 그 명제는 참이다. 그리고 그 명제의 부정문이 증명되서는 안된다.
-
완전성 : 모든 명제는 참이나 거짓으로 증명되어야(공리로부터 연역되어야) 한다.
-
결정성 : 명제가 증명 가능한지(공리로부터 연역 가능한지) 확인하는 일반적인 과정이 존재해야 한다.
이것은 힐베르트가 적절한 공리와 추론규칙을 설정한 다음 그것의 형식적인 조작을 통하여 연역되는 정리들의 집합체(형식적 연역체계)로 수학을 구성한 것입니다. 즉, 힐베르트는 유한한 공리와 몇가지 추론규칙을 통하여 수학의 모든 사실을 도출해내는 것을 자동으로 할 수 있도록 만들고 싶었던 것입니다. 그래서 이러한 자동기계를 만들기만 하면 근의 공식이나 도함수 구하는 공식같은 수학적 사실들이 모두 자동으로 만들어질 수 있을 것이라고 생각했습니다. 이 생각들은 수학적 사고를 순수한 기호 조작의 규칙으로 규명할 수 있다는 믿음에 근거하고 있었습니다.
하지만 이미 살펴보았듯이 괴델의 불완전성 정리로 인하여 자연수를 설명할 수 있을만큼 포괄적인 공리체계가 정합성(무모순성)을 가지면 그 체계는 반드시 불완전 체계라는 것이 밝혀졌습니다. 체계가 불완전하면 올바르지만 공리와 추론규칙으로 증명될 수 없는(연역될 수 없는) 명제가 반드시 존재한다는 것입니다. 괴델은 공리 체계가 자연수를 설명할 수 있기만 하면 반드시 그 수학 체계는 불완전 체계라는 것을 증명했었습니다. 따라서 괴델은 "공리와 추론규칙의 자동적인(기계적인) 조작으로(연역으로) 수학의 모든 사실들을 만들 수 없다." 는 것을 증명한 것입니다. 이에 따라 힐베르트 프로그램의 첫번째, 두번째 규칙이 무의미해졌습니다.
힐베르트 프로그램의 세번째 규칙 "결정성" 은 어떤 계산식을 공리와 정해진 추론규칙으로 계속 풀다보면 언젠가 풀 수 있는지, 풀 수 없는지를 미리 알 수 있느냐 하는 정지문제(halting problem) 과 관련이 있습니다. "결정성" 은 "명제가 증명 가능한지(공리로부터 연역 가능한지) 확인하는 일반적인 과정이 존재한다." 고 주장하는데 이것은 공리로부터
그런데 이때 앨런 튜링이 나타나 세번째 규칙 "결정성" 도 무의미하게 만들어버렸습니다. 튜링은 1935년 케임브리지 수학과를 졸업한 대학원생이었는데 이때 막스 뉴먼 교수가 개설한 괴델의 불완전성 정리 강의를 수강 중이었습니다. 뉴먼 교수는 힐베르트 프로그램 중 아직 부정되지 않은 세번째 조건을 소개했는데, 이때 튜링은 괴델의 증명에서 아이디어를 착안하여 불완전성 정리를 다시 증명할 수 있고 세번째 조건 "결정성" 또한 부정할 수 있겠다는 생각을 했습니다.
몇 주 후, 튜링은 괴델이 증명한 "기계적인 방식(형식적인 방식)으로는 수학의 모든 사실을 만들어낼 수 없다." 를 독창적으로 다시 증명하고 세번째 조건 "결정성" 또한 부정하는 내용을 담은 논문 《On Computable Numbers, with an Application to the Entscheidungsproblem》(계산가능한 수에 대해서, 수리명제 자동생성 문제에 응용하면서) 를 런던 수리학회에 제출했습니다.
튜링은 논문 《On Computable Numbers, with an Application to the Entscheidungsproblem》(계산가능한 수에 대해서, 수리명제 자동생성 문제에 응용하면서) 에서 먼저 매우 근본적인 것들을, 즉 "계산 가능한 것", "기계적인 것" 이 무엇인지 정의합니다.
-
계산 가능한 수 : 소수 부분을 유한한 자리까지 계산할 수 있는 실수이다.
-
자동 기계 : 네모 칸으로 이루어진 테이프에 있는 기호를 읽어서 그 기호에 해당하는 "명령" 을 수행하는 기계이다. 여기서 "명령" 이란 본질적으로 "이것이면 저것을 하라" 이다. 이 "명령" 이란 (1) 네모칸 이동, (2) 네모칸 쓰기, (3) 네모칸 읽기 에 불과하다.
튜링은 자신이 정의내린 "자동 기계" 의 범주에 상상할 수 있는 모든 자동 기계가 포함된다고 충분히 설득합니다. 그리고 자신의 방식대로 정의한 자동 기계를 튜링기계 라고 부릅니다. 그리고 튜링 기계를 텍스트로 사상시키는 방법을 보이고 텍스트로 사상된 기계를 읽어서 기계의 동작을 그대로 흉내내는 보편만능기계(컴퓨터) 를 만들어서 보여줍니다. 그러므로 이 보편만능기계는 기계적이고 자동적인 범주 내에 있는 모든 일을 수행할 수 있는 기계인 것입니다.
이 보편만능기계를 사람들이 전자회로를 통하여 구현하여 오늘날의 컴퓨터가 된 것입니다. 그러므로 사실 구현 재료가 전기가 아니어도 됩니다. 물로도 보편만능기계를 구현할 수 있고 빛으로도 보편만능기계를 구현할 수 있습니다. 다만 현 시점에서 가장 현실적으로 효율이 높은 재료가 전기일 뿐입니다. 그러나 앞으로 더 효율적인 자연 현상과 재료를 발견한다면 새로운 재료로 보편만능기계를 구현할 수 있을 것입니다. 가령 양자 컴퓨터처럼 말이죠.
기계를 텍스트로 표현(프로그램)하여 보편만능기계(컴퓨터)에 입력하면 보편만능기계가 텍스트로 사상된 기계의 동작(프로그램)을 그대로 흉내내 줍니다. 그러니 사실 여러분도 이미 수많은 튜링기계를 텍스트로 사상시켜 보았고(코딩) 그것을 보편만능기계(컴퓨터)에 입력시켜서 실행시켜보았던 것입니다. 여러분은 코딩을 하면서 지금까지 많은 튜링 기계를 만들었지만 그것을 물리적으로 구현할 필요가 없었습니다. 단지 보편만능기계에 입력해주기만 하면 되었기 때문입니다.
이 보편만능기계를 중심으로 튜링은 다음과 같은 논증으로 증명을 마무리했습니다.
-
(튜링 기계의 정의) 5 가지 부품을 정의한다. 이 5 가지 부품들로 만든 기계로 실행할 수 있는 것이 "기계적이 방식" 이다. 이 "기계적인 방식" 은 세상 모든 자동 기계를 포괄할 수 있을만큼 충분히 광범위하다.
-
(보편만능기계의 정의) 그런데 이 튜링기계의 정의대로 어떤 특별한 튜링기계를 만들 수 있다. 이 튜링기계를 보편만능기계라고 부른다. 보편만능기계는 다음과 같이 설계된다.
-
모든 튜링기계를 일관된 기호로 표현할 수 있도록 보편만능기계의 테이프 기호를 정의한다.
-
그러면 보편만능기계의 기호를 기반으로 모든 튜링기계를 순수한 텍스트로 사상시킬 수 있는데, 이 텍스트를 입력받아서 튜링기계의 동작을 그대로 흉내낼 수 있도록 작동규칙표를 정의한다.
그러므로 이 시점에서 보편만능기계는 세상에 존재하는 모든 기계적인 동작과 자동 기계를 대표한다.
-
-
핵심 논증
-
무한의 크기(대각선 논법) : (1) 실수의 개수가 자연수의 개수보다 많고, (2) 자연수의 부분집합의 개수가 자연수의 개수보다 많다.
-
튜링기계의 개수(튜링기계에 자연수 부여하기) : 튜링기계는 자연수만큼 많다.
-
보편만능기계로도 해결할 수 없는 정지문제 : 만약 모든 참인 명제를 기계적으로 만들어내는 튜링기계
가 존재하면,
이 멈출지 멈추지 않을지 판단하는 튜링기계
를 만들 수 있다. 그런데
-
튜링은 먼저 다음과 같은 5 가지 부품을 정의합니다.
-
(1번 부품) 무한히 많은 칸을 가진 테이프 (불변)
-
(2번 부품) 테이프에 기록되는 유한 개의 기호들 (튜링기계마다 가변)
-
(3번 부품) 테이프의 기호를 읽고 쓰는 입출력 장치 (불변)
-
(4번 부품) 입출력 장치의 상태를 나타내는 유한 개의 기호들 (튜링기계마다 가변)
-
(5번 부품) 기계의 작동 규칙표 (튜링기계마다 가변)
위 그림의 튜링기계가 테이프를 읽고 명령어를 실행하는 세 단계만 보이겠습니다.
-
현재 상태가 A 이고 테이프에서 읽은 기호가 * 이므로 테이프에 * 를 쓰고, 입출력 장치를 오른쪽 테이프로 한칸 옮기고, 다음 상태 A 가 된다.
-
현재 상태가 A 이고 읽은 기호가 $ 이므로 테이프에 $ 를 쓰고, 입출력 장치를 오른쪽 테이프로 한칸 옮기고, 다음 상태 B 가 된다.
-
현재 상태가 B 이고 읽은 기호가 * 이므로 테이프에 * 를 쓰고, 입출력 장치를 왼쪽으로 한칸 옮기고, 다음 상태 C 가 된다.
튜링은 이 부품으로 구성된 기계로 0 과 1 을 반복해서 쓰는 기계, 사칙연산을 하는 기계 등 다양한 일을 할 수 있는 기계를 만들어 보여주었습니다. 그리고 존재할 수 있는 모든 "자동 기계" 가 이렇게 만든 기계로 실행할 수 있는 것의 범주 내에 충분히 들어간다고 설득합니다. 그리고 그는 이 부품들로 만들어진 기계를 튜링 기계라고 불렀습니다.
그리고 튜링은 이 5 가지 부품들로 어떤 특별한 튜링기계를 만들어서 보여주었는데, 그것이 바로 보편만능기계(universal machine) 였습니다. 보편만능기계는 다음 두 가지 아이디어대로 설계됩니다.
-
(임의의 튜링기계를 보편만능기계의 기호로 구성된 텍스트로 환원하기) 모든 튜링기계를 일관된 기호로 표현할 수 있도록 보편만능기계의 테이프 기호를 정의한다. 그러면 보편만능기계의 기호를 기반으로 모든 튜링기계가 순수한 텍스트로 사상될 수 있고, 텍스트로 사상된 튜링기계는 보편만능기계의 테이프 입력으로 전달될 수 있다.
-
(텍스트로 사상된 튜링기계를 입력받아 실행하는 작동규칙표) 텍스트로 사상된 튜링기계를 입력받아서 그 튜링기계의 동작을 그대로 따라할 수 있도록 보편만능기계의 작동규칙표를 정의한다.
튜링이 이 튜링기계를 보편만능기계라고 부른 것은, 이 하나의 튜링기계로 존재하는 모든 튜링기계의 동작을 수행할 수 있었기 때문이었습니다. 즉, 보편만능기계는 모든 기계적인 계산을 수행할 수 있는 기계인 것입니다.
이제 이 보편만능기계의 두 가지 아이디어가 실제로 어떻게 구현되는지 살펴보겠습니다.
튜링은 보편만능기계의 유한 개의 기호를 정의하고, 모든 튜링기계를 보편만능기계의 기호로 테이프에 사상시키는 방법을 보였습니다. 기호로 사상되어야 하는 튜링기계의 5 가지 부품은 다음과 같습니다.
-
무한히 많은 칸을 가진 테이프
-
테이프에 기록되는 유한 개의 기호들
-
테이프의 기호를 읽고 쓰는 입출력 장치
-
입출력 장치의 상태를 나타내는 유한 개의 기호들
-
기계의 작동 규칙표
여기에서는 3 개의 테이프에 튜링기계의 5 가지 부품을 사상시켜보겠습니다.
-
테이프 A : 1 번 부품과 3 번 부품, 즉 테이프와 입출력 장치가 사상된다.
-
테이프 B : 4 번 부품, 즉 입출력 장치의 상태를 나타내는 기호가 사상된다.
-
테이프 C : 5 번 부품, 즉 작동규칙표가 사상된다.
2 번 부품, 즉 유한 개의 상태 기호와 테이프 기호는 무수히 많은 튜링기계마다 다양하겠지만, 그것들을 모두 각각
(상태기호) S0, S1, S2, ...
(테이프기호) T0, T1, T3, ...
로 변환할 수 있기 때문에 이 일반적인 기호를 사용하는 튜링기계 M 이 모든 튜링기계를 대표한다고 하겠습니다.
테이프 A 에는 튜링기계 M 의 테이프와 입출력 장치가 사상됩니다. 사상되는 방법은 다음과 같습니다.
-
튜링기계 M 의 테이프의 네모칸들 왼쪽에 빈칸을 하나 더 추가한다. 그러면 빈칸과 테이프 기호가 반복되어 나타난다.
-
M 의 입출력 장치가 현재 가르키고 있던 칸의 빈칸에만 위치기호 * 를 표시한다.
이 방식대로하면 원래의 튜링기계 M 의 테이프가
| T0 | T1 | T3 | ... |
|---|
였고, 입출력 장치가 T0 을 가르키고 있었다면 테이프 1 로 사상된 튜링기계는
| * | T0 | T1 | T3 | ... |
|---|
가 됩니다.
테이프 B 에는 튜링기계 M 의 상태기호(S0, S1, S2, ...) 가 쓰여집니다. 그래서 튜링기계 M 의 현재상태가 S0 이었다면 테이프 B 는
| S0 | ... |
|---|
가 됩니다.
테이프 C 에는 5 번 부품, 즉 튜링기계 M 의 작동규칙표가 사상됩니다. 튜링은 무수히 많은 튜링기계들이 무수히 많은 작동규칙표를 갖겠지만, 그 모든 작동규칙표들을 유한한 기호로 표현할 수 있다는 것을 보여주었습니다.
여기에서는 고정된 기호
| S | T | > | < | || | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | X | * |
|---|
를 사용하겠습니다. 이때 기호 X 는 각각의 규칙의 경계를 표시하는데 사용됩니다.
-
튜링기계 M 의 작동규칙표가
S0 T0 T1 > S1 S1 T2 T12 < S0 와 같았다면, 규칙들을 X 로 구분하여 다음과 같은 텍스트로 사상시킬 수 있습니다.
XS0T0T1>S1XS1T2T12<S0X
최종적으로 이 작동규칙표를 테이프 C 에 사상시키면 다음과 같습니다.
X S 0 T 0 T 1 > S 1 T 2 T 1 2 < S 0 X 지금까지 설명의 간소화를 위하여 T0 같은 문자를 테이프 한 칸에 표시했는데, 실제로는 위와 같이 한 문자가 하나의 테이프 칸에 표시되어야 한다.
이 방식으로 존재하는 모든 튜링기계의 작동규칙표를 고정된 기호 S,T,>,<,||,0,1,2,3,4,5,6,7,8,9,X,* 를 기반으로 테이프 C 에 사상시킬 수 있습니다.
이로써 모든 튜링기계를 대표하는 튜링기계 M 이 성공적으로 테이프 A, 테이프 B, 테이프 C 에 사상되었습니다. 이제 이 테이프를 입력받아서 원래의 튜링기계의 동작을 그대로 흉내내는 보편만능기계의 작동규칙표를 설계해보겠습니다. 그런데 이 작업은 생각보다 매우 쉬우며 다음과 같이 이루어집니다.
-
테이프 B 에서 현재 상태 기호
를 읽는다.
-
테이프 A 에서 위치 기호(*) 를 찾아 그곳의 테이프 기호
를 읽는다.
-
현재 상태 기호
이 작업을 반복하면 테이프로 사상된 임의의 튜링기계를 입력받아서 그 동작을 그대로 똑같이 흉내낼 수 있습니다. 그리고 이렇게 설계된 보편만능기계가 컴퓨터의 본질이자 원시 모델인 것입니다.
그런데 튜링기계란 하나의 테이프를 갖고 있어야 하는데, 여기서 살펴본 방식대로라면 임의의 튜링기계가 3 개의 테이프로 사상되어 보편만능기계의 입력으로 들어옵니다. 이 문제를 해결하는 것은 매우 쉬우며 설명의 간소화를 위하여 미리 언급하지 않았습니다. 가령 한 가지 방법은 3 개의 테이프를 하나씩 번갈아가며 써서 하나의 테이프로 합치는 것입니다. 그래서 만약 테이프 A, 테이프 B, 테이프 C 이 각각 다음과 같았다면
이렇게 하나의 테이프로 합칠 수 있습니다.
그러면 각 테이프를 읽기 위하여 일정한 거리를 건너뛰어서 읽기만 하면 되는 것입니다.
이제 본격적인 튜링의 증명에 도달했습니다. 튜링의 증명을 이해하기 위해서는 먼저 무한의 크기를 이해해야 합니다.
칸토어는 (1) 실수의 개수가 자연수의 개수보다 훨씬 크다는 것과 (2) 자연수의 부분집합의 개수가 자연수의 개수보다 훨씬 더 크다는 것을 증명했습니다. 칸토어는 무한이 자연수만큼 있으면 셀 수 있을만큼 많다고 표현했고 무한이 실수만큼 있으면 셀 수 없을만큼 많다고 표현했습니다.
아래의 칸토어의 증명을 대각선 논법이라고 하는데 이 증명이 너무 직관적이고 아름다워서 에르되시 팔은 이 증명이 "하나님이 갖고 있는 수학책에 있는 증명이다." 라고 말했습니다.
실수의 개수가 자연수의 개수보다 훨씬 크다는 칸토어의 증명은 다음과 같습니다.
-
먼저 실수집합 전체 대신 구간
을 상정하자. 다음의 탄젠트 함수
을 살펴보면 구간
-
그리고 이 구간
정말로 구간
는 자연수
로 번호매겨진 실수를 뜻하고,
는
부터
사이의 자연수이다.
-
이제 어떤 실수
를 이렇게 만들어보자. 실수
의 소수
를 위와 같은 실수
가
로 정하고,
그러므로 만약 실수들이
라고 되어 있었다면
이 될 것이다.
-
그렇다면 이 실수
-
자연수로 모든 실수에 번호를 매겼다고 가정했지만, 그 이외의 실수
자연수의 개수보다 자연수의 부분집합의 개수가 훨씬 많다는 칸토어의 증명은 다음과 같습니다.
-
자연수의 부분집합이 자연수만큼 있다면 그 집합들 모두에 다음과 같이 자연수로 번호를 매길 수 있다.
-
자연수의 부분집합이므로
은 대강
{2}, {42, 882}, {1}, {5, 8}, {}, {0}, {9, 2, 888}, {9292111}, ...
와 같은 모습일 것이다.
-
-
그러면 자연수를 원소로 갖는 집합
를 이렇게 만들어보자.
에
이 없다면
에
가 없다면
에
-
그렇다면
-
자연수의 부분집합 모두에 자연수로 번호를 매겼다고 가정했지만, 그 이외의 자연수의 부분집합
그렇다면 튜링기계의 개수는 셀 수 있을만큼(자연수만큼) 많을까요, 셀 수 없을만큼(실수만큼) 많을까요? 결론만 말하면 튜링기계의 개수는 셀 수 있을만큼(자연수만큼) 많습니다. 즉, 튜링기계의 개수는 자연수의 개수를 넘지 못합니다. 왜냐하면 튜링기계를 테이프로 사상시킬 수 있고, 그 테이프를 고유한 자연수로 사상시킬 수 있기 때문입니다.
우리는 튜링기계를 테이프로 사상시킬 때 유한한 기호
| S | T | > | < | || | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | X | * |
|---|
를 사용했습니다. 그러므로 테이프를 자연수로 표현할 수 있는 한가지 방법은 다음과 같이 테이프를 17진수의 자연수로 사상시키는 것입니다.
| 기호 | 0 | 1 | 9 | S | T | > | < | || | X | * | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 자연수 | 0 | 1 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
그런데 존재하는 모든 튜링기계는 이 유한한 기호로 표현될 수 있습니다. 따라서 존재하는 모든 튜링기계를 고유의 자연수로 사상시킬 수 있습니다.
-
가령 XS1T2>* 와 같이 표현된 매우 간단한 튜링기계를 생각하자. 그러면 이것을 다음과 같이 17진수 자연수로 해석하여
X S 1 T 2 > * 15 10 1 11 2 12 16 고유의 자연수
를 부여할 수 있다. 이렇게 존재하는 모든 튜링기계에 고유의 자연수를 부여할 수 있기 때문에 튜링기계의 개수는 자연수의 개수를 넘지 못한다.
이로써 우리는 튜링기계(프로그램)의 개수가 자연수의 개수를 넘지 못한다는 결론에도 도달할 수 있습니다. 더 나아가 프로그램에 입력되는 입력 또한 텍스트에 불과하므로 비슷한 방식으로 고유의 자연수로 사상될 수 있습니다. 따라서 프로그램의 입력도 자연수의 개수를 넘지 못합니다.
이제 튜링의 증명을 이해할 모든 준비가 끝났습니다.
튜링의 증명의 목표는 모든 참인 명제를 기계적으로 만들 수 있는 튜링기계가 존재하지 않는다는 것을 보이는 것이었습니다. 튜링은 먼저 모든 참인 명제를 만들어낼 수 있는 튜링기계 가 존재한다고 가정하고 다음과 같은 논증을 펼쳤습니다.
- 이 튜링기계
-
보편만능기계는 임의의 튜링기계를 입력받아 흉내낼 수 있으므로 튜링기계
-
이때 어떤 튜링기계
-
그러면
-
이것은 곧 튜링기계
) 는 결론을 얻는다.
그런데 튜링기계 가 존재한다면 튜링기계의 개수가 자연수의 개수보다 많아집니다. 그러나 튜링 기계의 개수는 자연수를 넘지 못합니다. 그러므로 튜링기계
는 존재할 수 없고 결국 튜링기계
도 존재해서는 안됩니다. 다음의 논증을 보겠습니다. 무한의 크기를 증명할 때 사용되었던 대각선 논법이 사용됩니다.
-
튜링기계의 개수는 자연수의 개수보다 많지 않다. 그러므로 모든 튜링기계에 자연수로 번호
를 붙힐 수 있다.
-
그리고 어떤 튜링기계에 입력되는 테이프도 유한개의 기호로 이루어져있으므로 자연수로 사상될 수 있으며, 이에따라 입력 또한 자연수의 개수보다 많지 않다. 따라서 튜링기계에 입력될 수 있는 모든 입력에도 자연수로 번호
를 부여할 수 있다.
-
그런데
위 표에 따르면 튜링기계
에 입력
를 입력시켜서 실행한 결과가
-
그러면 튜링기계
를 이렇게 만들어보자.
와 기계
를 입력으로 받아서
- 그러므로
)을 얻는다.
- 그러므로
-
번째 입력
-
존재하는 모든 튜링기계에 자연수로 번호
-
그러므로 튜링기계
이로써 우리는 모든 참인 명제를 만들어내는 튜링기계 는 존재할 수 없다는 결론에 도달했습니다. 이로써 튜링의 증명이 완료되었습니다.
튜링은 아마 괴델이 불완전성 정리에서 괴델이 상위 수학명제를 순수학 수학명제로 사상시키는 것을 보고 튜링기계(상위 수학명제)를 순수한 텍스트로 구성된 테이프(수학명제)로 사상시키자는 생각을 했던 것 같습니다. 그리고 괴델이 수학명제에 고유의 괴델수를 부여한 것처럼 그 테이프에 고유의 자연수를 부여할 수 있다는 것을 깨달은 것 같습니다. 이 관점에서 바라본다면 모든 튜링기계는 PM 속으로 사상될 수 있는 상위 수학명제이고, 테이프로 사상된 튜링기계(프로그램의 소스코드)는 PM 속의 형식문 모임(증명)과 같습니다.
| 괴델의 불완전성 정리 | 튜링의 증명 | 컴퓨터 |
|---|---|---|
| 상위 수학명제 | 튜링기계 | |
| 수학명제 | 테이프로 사상된 튜링기계 | 하드웨어와 프로그램 |
| 괴델수 | 테이프에 부여된 고유의 자연수 | |
| 힐베르트 프로그램 | 튜링기계 |
모든 문제를 해결할 수 있는 알고리즘을 자동으로 생성하는 프로그램 |
| 세번째 조건 결정성(명제가 증명가능한지 확인하는 알고리즘이 존재한다) | 튜링기계 |
어떤 프로그램이 끝날지 끝나지 않을지 판단하는 프로그램 |
증명가능한지 확인한다는 것 자체가 공리로부터 그 결론이 도달 가능한지(연역 가능한지) 검증한다는 것이기 때문에, 프로그램을 구성하는 코드 한 줄 한 줄이 형식문 한 줄 한 줄에 대응되고 그것이 끝날지 끝나지 않을지 결정하는 알고리즘은 공리로부터 결론이 도달 가능한지 도달할 수 없는지 확인하는 방법과 같다?
물리학 -> 해석학, 기하학 -> 자연수를 설명할 수 만큼 포괄적인 체계(형식적 연역체계) = 프로그램
튜링기계의 1 번 부품 테이프는 컴퓨터의 RAM 으로, 3 번 부품 테이프 입출력 장치는 RAM 입출력 장치로, 5 번 부품(보편만능기계) 의 작동규칙표는 컴퓨터의 CPU 로 구현되었습니다. 이것으로 우리는 컴퓨터가 튜링기계의 특수한 경우의 보편만능기계의 물리적 구현체이므로 컴퓨터는 튜링기계의 범주내에 속한다는 것을 알 수 있습니다. 컴퓨터가 모든 참인 명제를 만들어낼 수 없고, 세상에 존재하는 모든 문제를 자동적으로 해결할 수 없다는 것을 뜻합니다.
이로써 컴퓨터(하드웨어)란 튜링기계의 특수한 경우인 보편만능기계를 물리적으로 구현한 것이고, 컴퓨터에 입력되는 프로그램은 보편만능기계에 입력되는 모든 튜링기계라는 것을 알 수 있습니다. 보편만능기계를 비단 물리적으로 구현해야만 하는 것이 아니고 소프트웨어로 구현할 수도 있기 때문에 Windows 시스템에서 Ubuntu Linux 같은 가상머신을 설치하여 또 다른 보편만능기계를 실행시킬 수 있는 것입니다.
하지만 튜링기계를 능가하는 기계가 존재하는가에 대한 의문은 아직 풀리지 않았습니다. 지금의 컴퓨터는 튜링의 정의일 뿐입니다. 따라서 튜링 기계를 능가하는 컴퓨터의 탄생은 아직 오지 않았을지도 모릅니다.
또한 우리는 괴델이 『수학 원리』의 모든 논증과 명제와 논리 패턴들을 순수한 수로 사상시킨 것처럼, 그 아이디어가 그대로 컴퓨터에 사용된 것을 알 수 있습니다. 즉 컴퓨터는 수를 다루는 기계이지만 수가 모든 종류의 패턴과 구조를 표현할 수 있는 보편적인 매개 수단이므로 컴퓨터로 세상에 존재하는 모든 종류의 패턴(논리적 패턴, 비논리적 패턴, 정합적인 패턴, 부정합적인 패턴 등)을 자동화시킬 수 있다는 것입니다.
이에 따라 컴퓨터로 인간의 이성을 대체하려는 인공지능 연구자들은 다시 기운을 되찾을 수 있습니다. 왜냐하면 인간의 뇌 속의 뉴런의 구조와 패턴 또한 수로 사상시킬 수 있고, 수로 사상된 것은 무엇이든지간에 컴퓨터 프로그램으로 대체시킬 수 있기 때문입니다. 실제로 우리는 이미 뉴런과 그것이 이루는 신경망을 프로그램으로 구현하는 시대에 살고 있습니다.
근데 임의의 튜링기계에 대하여 이 표를 만들 수 있다면, 그 표를 기반으로 자연수 개수를 초월하는 존재해서는 안되는 튜링기계를 만들 수 있는 거 아닌가. 그렇다면 이 표는 절대로 만들어져서는 안된다. 그 말 뜻은 모든 튜링기계는 반드시 어떤 입력에 대하여 출력을 하지 않는다. 즉, 종료되지 않는다.