튜링 머신

1. Mechanical Reasoning

기계적으로 가능한 추론 정의 (앨런 튜링의 논문 "계산 가능한 수와 결정성 문제에의 응용" 1936) :

→ 튜링머신으로 계산 가능한 추론을 기계적으로 가능한 추론이라고 정의

 

2. Turing Machine

유한 심볼, 유한 상태, 유한 규칙, 무한 테이프를 가지고 일련의 계산을 수행하는 일종의 기계이다. 이 튜링머신의 디자인은 현대의 컴퓨터에도 남아있는데, 가까운 미래에 심볼은 프로그래밍 언어가, 규칙표는 소프트웨어가, 테이프는 메모리가, 포인터는 프로세서가 되었다.

 

[그림] 튜링머신

 

위의 튜링머신을 실행시켜보자. 가장 처음 테이프에는 [*, $, *, *]가 적혀있고 포인터의 상태는 A인 채로 시작한다. (현재 포인터가 가르키는 곳은 붉은색으로 표시한다) 튜링머신을 실행시키면 튜링머신의 모든 행동은 위의 규칙표를 따라서 움직이게 된다. Start는 입력상태, End는 출력상태, R은 Read, W은 Write이고, Point는 Write 이후 포인터의 움직임 방향이다. 심볼로 작성된 규칙표는 미래에 프로그래밍 언어로 작성된 소프트웨어가 된다.

 

1) 상태A에서 *를 Read했기 때문에 그 자리에 다시 *을 Write하고 포인터를 우측으로 한칸 이동하고, 상태를 A로 유지한다. 때문에 현재 상태에서 테이프에는 [*, $, *, *]가 적혀있고 상태는 A이다.

 

2) 상태A에서 $를 Read했기 때문에 그 자리에 다시 $를 Write하고 포인터를 우측으로 한칸 이동하고, 상태를 B로 변경한다. 때문에 현재 상태에서 테이프에는 [*, $, *, *]가 적혀있고 상태는 B이다.

 

3) 상태 B에서 *를 Read했기 때문에 그 자리에 다시 *를 Write하고 포인터를 좌측으로 한칸 이동하고, 상태를 C로 변경한다. 때문에 현재 상태에서 태이프에는 [*, $, *, *]가 적혀있고 상태는 C이다.

 

4) 상태 C에서 $를 Read했기 때문에 그 자리에 *를 Write하고 포인터를 우측으로 한칸 이동하고, 상태를 C로 유지한다. 때문에 현재 상태에서 테이프에는 [*, *, *, *]가 적혀있고 상태는 C이다.

 

5) 상태 C에서 *을 Read했기 때문에 그 자리에 $를 Write하고 포인터를 우측으로 한칸 이동하고, 상태를 B로 변경한다. 때문에 현재 상태에서 테이프에는 [*, *, $, *]가 적혀있고 상태는 B이다.

 

6) 상태 B에서 *를 Read했기 때문에 그 자리에 *를 Write하고 포인터를 좌측으로 한칸 이동하고 상태를 C로 변경한다. 때문에 현재 상태에서 테이프에는 [*, *, $, *]가 적혀있고 상태는 C이다.

 

7) 상태 C에서 $를 Read했기 때문에 그 자리에 *를 Write하고 포인터를 우측으로 한칸 이동하고 상태를 C로 유지한다. 때문에 현재 상태에서 테이프에는 [*, *, *, *]가 적혀있고 상태는 C이다.

 

8) 상태 C에서 *를 Read했기 때문에 그 자리에 $를 Write하고 포인터를 우측으로 한칸 이동하고 상태를 B로 유지한다. 때문에 현재 상태에서 테이프에는 [*, *, *, $]가 적혀있고 상태는 B이다.

 

9) 이동한 칸에 아무 심볼도 적혀있지 않기 때문에 튜링머신을 종료한다. 최종 출력은 [*, *, *, $]이다. 사실 이 튜링머신이 하는 것은 $를 발견하여(A상태) 다음칸에 적을 공간이 있는지 체크하고(B 상태) $를 한칸 오른쪽에 옮겨 적는(C상태) 일을 자동으로 수행하는 기계이다.

 

3. Universal Machine (보편 만능의 기계) :

Universal Machine은 Turing Machine의 일종으로 다른 Turing Machine의 정보를 입력으로 받아서 그대로 흉내내는 Turing Machine이다. 이 Universal Machine은 기계적으로 구현되어 미래에 컴퓨터가 되었고 입력받는 다른 Turing Machine들의 정보는 미래에 프로그램 (소프트웨어)가 되었다. 마찬가지로 현대의 컴퓨터는 컴퓨터 스스로가 그 자체로는 아무것도 하지 않는다. 소스코드로 구현된 다른 소프트웨어를 입력으로 그 소프트웨어 그대로 수행한다.

 

1. 입력 W (흉내낼 기계의 실행 테이프)

2. 기계 M (흉내낼 기계를 설명하는 테이프)

3. Initial State (위치에 따른 State)

 

아래 그림과 같이 위의 3가지를 입력으로 받아서 이들 테이프를 교차해서 실행시킨다. 유니버셜 머신의 자세한 동작은 이 자료에서 다루지 않는다. 

 

[그림] 유니버셜 머신

 

4. Turing Machine을 이용한 괴델의 불완전성 정리 증명

튜링은 자신의 논문(계산 가능한 수와 결정성 문제에의 응용, 1936) 마지막부분에서 Turing Machine으로 직접 괴델의 불완전성 정리를 자신만의 방식으로 증명한다. 괴델의 괴델수처럼, 튜링 역시 튜링머신을 하나의 자연수로 맵핑한다. 즉, N개의 심볼이 존재하는 튜링머신을 N진수의 수로 맵핑 한다.

 

예를 들어 16개의 심볼 [A, B, C, ..., *, $, >, <]를 가지는 튜링머신이 있다고 해보자. 이 것을 [0, 1, 2, ... , C, D, E, F]와 같이 16진수로 맵핑한다면, 해당 튜링머신의 규칙표의 첫 규칙인 "A**>A"를 "0CCE0"과 같이 맵핑할 수 있다. 5개의 규칙이 있다면 다섯개의 규칙을 모두 자연수로 바꾸고 변환된 자연수들을 Concatenation 하여 하나의 규칙표(튜링머신)을 하나의 자연수로 만들 수 있다.

 

a = 가능한 Turing Machine의 수 : ∞

b = 자연수의 수 : ∞

 

라고 한다면 a와 b중 어떤 것이 더 클까? 두 수 모두 무한대의 값을 가지지만 무한대에도 급이 있다. 즉, 더 큰 무한대와 더 작은 무한대가 존재한다 (Cantor의 대각선 논법을 응용함) 때문에 b > a이라고 할 수 있고, 때문에 모든 참인 명제를 (정확히 말하면 자연수만큼의 튜링머신을) 만들어 낼 수 없다는 것이 튜링의 증명이다. 이 증명을 공부하기 전에 Cantor의 대각선 논법부터 알아보자.

 

5. Cantor의 대각선 논법

Cantor의 대각선 논법은 자연수를 집합으로 봤을 때, 자연수($N$)보다 자연수의 멱집합이 가진 원소의 수($2^N$)가 많은 것이 타당하다는 것이다. (멱집합은 부분집합들을 전부 모아놓은 집합을 의미한다)

 

 

$|N| < |2^N|$

자연수 < 자연수의 부분집합

 

 

만약, 자연수의 수와 멱집합이 가진 원소의 수가 동일하다면, 우리는 아래와 같은 정방행렬(열의 수 = 행의 수)를 생각해볼 수 있다. 표의 행($S_1$, $S_2$, ...)은 자연수의 부분집합들이고 표의 열(1, 2, ...)은 자연수이다. 아래 그림에서 O와 X는 해당 행의 부분집합 $S_n$에 해당 열의 자연수가 포함되었는지에 대한 여부이다.

 

[그림] 대각선 논법 (멱집합)

 

자연수의 부분집합이 만약 위 그림처럼 정의된다면, 우리는 좌측에 있는 모든 부분집합과 다른 집합 $X$를 만들 수 있다. 만약 $S_1$에 1이 들어있다면, $X$에는 1을 넣지 않는다. 만약 집합 $S_2$에 2가 들어있지 않다면 $X$에 2를 넣는다. 집합 $S_3$에 3이 들어있다면 $X$에는 3을 넣지 않는다. 이런식으로 대각선의 원소들을 보고 현재 존재하는 모든 집합의 상태와 반대로 집합을 구성하면 그 집합은 좌측 $S_n$에 포함되지 않는다. 때문에 자연수 개수만큼의 부분집합의 수보다 많으므로 $S_n$이 자연수 집합보다 크다.

 

6. Halting 문제를 푸는 Turing Machine은 없다.

Halting Problem(멈춤 문제)는 특정한 튜링머신이 입력되었을 때, 그 튜링머신이 종료되는 튜링머신인지 영원히 종료되지 않는 튜링머신인지 시뮬레이션하지 않고(돌려보지 않고) 아는 것을 말한다. 여기에서 명제 2개를 정의한다.

 

---

명제 $p$ : 모든 참인 명제를 만드는 Turing Machine이 존재한다.

명제 $q$ : Halting Problem을 푸는 Turing Machine이 존재한다.

 

---

 

만약 모든 참인 명제를 만들어내는 튜링머신 $A$가 있다면, 우리는 다음과 같은 명제를 하나 더 생각할 수 있다.

 

명제 $u$ : Halting Machine으로 A를 수행하면 끝난다

 

이 명제 $u$ 역시 참거짓을 밝힐 수 있으므로, 튜링머신 $A$로 모든 참인 명제를 만들면, 이 명제 $u$도 참인지 거짓인지 알 수 있다. 때문에 $\exists A \rightarrow \exists H$이다. 참인 명제는 대우도 반드시 참이므로 $\sim \exists H \rightarrow \sim \exists A$가 되므로 우리가 만일 Halting Problem을 풀 수 있는 튜링머신 H가 존재하는지만 알면 A의 존재 여부도 알 수 있게 되고, 이 A의 존재여부가 바로 힐베르트가 제안한 수리문제 자동판별문제의 답이 된다. 우리는 칸토어의 대각선논법을 확장하여 아래와 같은 테이블을 생각할 수 있다.

 

[그림] 튜링의 증명에 사용된 테이블 예시

 

위의 $I$는 가능한 모든 입력의 조합을 말한다. 좌측의 $TM$은 입력의 개수와 동일한 튜링머신을 말한다. 그리고 멈춤문제를 푸는 튜링머신인 $H$가 있다고 하자. 이 $H$는 $TM$과 $I$를 입력받아서 해당 튜링머신으로 해당 입력을 수행했을 때, 그 튜링머신이 종료되는지 종료되지 않는지를 위 테이블에 출력한다. 예를 들어 $M_1$은 $I1, I3, I4$를 입력받으면 동작 수행후 성공적으로 종료되지만 $I2, I5$를 받으면 종료되지 않고 무한히 실행된다 (무한루프) 만약 $H$라는 튜링머신이 존재한다면 위와 같은 테이블을 만들어낼 수 있다.

 

이때 새로운 튜링머신 $Z = H(TM, I) \times TM_n(I_n) + 1$을 정의한다. 즉, 만약 해당 튜링머신이 끝난다면 $H$에서 1이 리턴되므로 튜링머신의 리턴값에 1을 더한 값을 리턴하고, 튜링머신이 끝나지 않으면 $H$에서 0이 리턴되므로 그냥 1을 리턴하는 튜링머신이다. 이 튜링머신은 해당 튜링머신이 끝나던, 끝나지 않던 기존 튜링머신 $TM_n$의 출력과는 모두 다르다. $H$가 존재하면 $Z$도 존재할 수 있다. 그러나 $Z$가 존재하지 않기 때문에 $H$는 존재할 수 없고, $H$가 존재하지 않기 때문에 $A$도 존재할 수 없다. 튜링은 괴델처럼 어려운 방식이 아닌 간단하고 직관적인 방법으로 힐베르트의 수리문제 자동판별문제를 재해석하였다.

 

7. Reference