Turing Machine

AlanTuring의 계산모델로서, 현재의 VonNeumann형 컴퓨터는 모두 이 TuringMachine을 기반으로 만들어져있다.

개요 ¶

Standard TuringMachine(STM)은 무한한 길이의 re-writable tape과 그 위를 왼쪽 오른쪽으로 한칸씩 움직일 수 있는 head, 그리고, 그 head를 제어하는 장치로 이루어져있다. TuringMachine이란 수학적인 모델로서 7개의 변수 혹은 변수의 집합들로 정의되지만, 여기서는 그런 내용은 생략하기로 한다.

TuringMachine은 STM에서부터 테잎과 head의 움직임에 따라 그 변이가 가능하지만, 그러한 변형된 형태의 TuringMachine도 STM과 equivalent하다.

어떤 계산 기계나 계산 체계(system)를 TuringMachine으로 코딩할 수 있고, 그 기계가 어떤 TuringMachine이라도 그 동작을 흉내내도록 코딩될 수 있으면, 그 기계가 TuringMachine과 동등(equivalent)하다, 그 체계가 turing-complete하다 또는 그 기계가 TuringMachine이다 라고 말하기도 한다.

STM과 equvalent함을 보이는 것은 흔히 simulation이라는 증명기법이 사용되는데, 이 simulation이라는 것은 우리가 흔히 말하는 시뮬레이션과 별 차이는 없다. 다만, 그 시뮬레이션이라는 게 그냥 입출력이나 움직이는 모양이_{'어이쿠 같네.' 이게 아니라} --; transition function이 mapping이 가능한지, 즉, 내가 증명하고자 하는 어떤 변종머쉰과 STM의 모든 가능한 transition function이 서로 isomorphic한지 보이는 과정이라는 것이다. 이 과정은 결코 간단하지 않으며(교재의 것들은 당연히 간단함.), 처음에 약간의 흥미진진함(아이디어제공과정)을 빼면 그 이후로는 상당히 지루하면서, 복잡하기까지 할 때도 있다.

Universal TuringMachine(UTM)는, STM이 사실상 transition function에 의해 고정된 하나의 머쉰밖에 될 수 없으므로, Computational Universality, 즉, ChurchTuringThesis에서 말하는 것과 같이 임의의 모든 계산이 가능한 능력이 없음을 극복하기 위해서 만들어진 것이다. 그래서, reprogrammable하게 만든 것이 UTM이다. transition function도 tape에 쓰고 internal state도 tape에 쓴다.

예 >
{{|
TuringMachine A는 0/1 두 가지 상태를 가질 수 있다. (내부 메모리가 1비트이다)

(기계상태, 테이프내용)	동작
(0,0)	한 칸 앞으로 가서 Tape에 1을 쓰고 상태를 1로 바꾼다.
(0,1)	한 칸 앞으로 가서 Tape에 0을 쓰고 상태는 0을 유지한다.
(1,0)	제자리에서 Tape에 1을 쓰고 상태를 0으로 바꾼다.
(1,1)	제자리에서 Tape에 0을 쓰고 상태는 1을 유지한다.

그리고 테이프는 처음에 헤더가 있는 곳부터 110100... 이라고 쓰여있고, 기계의 처음 상태는 0이라고 가정하자.

단계	(기계상태, 테이프내용)	동작 후 기계상태	동작 후 테이프내용
step 1	(0,1)	0	1*00100
step 2	(0,0)	1	10*1100
step 3	(1,1)	1	10*0100
step 4	(1,0)	0	10*1100
step 5	(0,1)	0	101*000
..	..	..	..

간단해 보이지만 이와 같은 방식으로 현재의 범용 컴퓨터가 계산할 수 있는 계산 중에 못하는 것이 있음이 밝혀지지 않았다.(ChurchTuringThesis)
|}}

[edit]

정지 문제 ¶

임의의 TuringMachine과 그에 대한 어떤 입력에 대해 그 결과로 다음의 두 가지만이 예측됨을 쉽게 이해할 수 있다.

언젠가 계산을 멈춘다.
안 멈추고 영원히 계산한다.

이런 두 가지 상황에 대해서, 정지문제란 '이렇게 어떤 특정한 기계 M과 입력 I의 쌍 (M, I)가 주어졌을 때에 이 계산이 유한한 시간 내에 정지되겠는가?'를 말한다.

이 문제를 푸는 기계를 함수 H(M, I)라고 표시해보자. 이 기계는 입력으로 M과 I를 받아서 M에 I를 넣었을 때, 즉, M에 input I를 넣었을 때, M이 유한한 시간 내에 정지할지 정지하지 않을지를 유한한 시간 안에 결정해 준다. 그러나 결론적으로 이러한 기계 H는 존재하지 않는다:

만일 그러한 H가 존재한다고 하자. 즉, M이 I를 인풋으로 해서 무한루프를 돌면 YES, 무한루프를 돌지 않으면 NO를 출력으로 한다. 즉,

procedure H(procedure M, input I){

if( M(I) loops infinite) return YES;
else NO

}

이제 청개구리 함수 K(P)를 만들어보자. 이게 모순을 이끌어내는 핵심이다. 즉, 자신을 입력으로 받는 함수 P를 입력으로 삼는 함수이며, H(P,P)의 반대로 작동한다. 즉, H(P,P)가 YES면 K(P)는 유한한 시간 내에 끝나고, H(P,P)가 NO면, 무한루프를 돈다. 이러한 K(P)는 H가 존재한다는 가정하게 간단히 다음과 같이 짤 수 있을 것이다.

procedure K(procedure P){

if(H(P,P) is YES) return;
else while(1);

}

이번에는 H(K,K)에 대해서 생각해보자.
1. 답이 YES 라고 해보자. H의 정의에 의해 K(K)는 무한루프를 돌아야 한다. 그러나 K의 정의에 의해 H(K,K)가 YES이므로 K(K)는 유한한 시간 내에 끝나야 한다. --> 모순
2. 답이 NO라고 해보자. H의 정의에 의해 K(K)는 유한한 시간 내에 끝나야 한다. 그러나 K의 정의에 의해 H(K,K)가 NO이므로 K(K)는 무한루프를 돌아야 한다. --> 모순

따라서, 이와같은 H가 존재한다는 가정이 잘못되었음을 알 수 있으며, 이 문제는 undecidable problem으로 분류된다. --naya

TuringMachine은 CellularAutomata의 일종이라고 할 수 있나요?

CellularAutomata의 Turing Compatibility에 대해서 Von Neumann이 말한 바가 있었고, CellularAutomata의 여러 변종들이 TuringMachine으로 구현되는 것을 80년대 말~90년대 논문에서 많이 찾아볼 수 있습니다. --naya

universality에 대해서 설명해 주세요...

SeeAlso

TuringMachine.html TuringTest

컴퓨터분류