이동식 저장소

2-Tape DTM

테이프 2개를 사용하는 DTM을 생각해보자. 이 기계는 테이프가 1개인 DTM보다 더 많은 계산을 할 수 있을까? 결론부터 말하면, 실행 시간이 조금 빨라질 수는 있어도 두 기계의 계산능력 자체는 동일하다.

테이프가 2개인 DTM의 전이함수는 다음과 같다.

$(p,a,b)\to (q,c,d,s,t)$

$p$: 현재 상태

$a$: 첫 번째 테이프에서 읽은 글자

$b$: 두 번째 테이프에서 읽은 글자

$q$: 전이할 상태

$c$: 첫 번째 테이프에 쓸 글자

$d$: 두 번째 테이프에 쓸 글자

$s$: 첫 번째 테이프의 이동 방향(왼쪽, 오른쪽, 정지 중 하나)

$t$: 두 번째 테이프의 이동 방향(왼쪽, 오른쪽, 정지 중 하나)

어쨌든 테이프가 2개 있으니 테이프 1개짜리보다 더 많은 계산을 할 수 있을 것 같지만, 그렇지 않다고 했다. (6주차 1차시 15:00~) 굉장히 비효율적이긴 하지만 테이프 1개짜리 DTM으로 테이프 2개짜리 머신을 시뮬레이션할 수 있다. 같은 방법으로 테이프 $n$개나 심지어 2차원 테이프를 갖는 DTM도 테이프 1개짜리 기계로 모두 시뮬레이션할 수 있다.

스택 2개만 있어도 되는 이유

사실 지난 시간에 이와 유사한 문제를 생각해 보았다. 스택 $n$개짜리 DPDA는 모두 스택 2개짜리 DPDA로 시뮬레이션할 수 있다고 했는데, 그 이유를 지금부터 따져 보자.

스택 2개를 갖는 DPDA는 테이프를 2개 갖는 DTM으로 시뮬레이션할 수 있다. 테이프 하나를 스택처럼 쓰면 가능하다. 마찬가지로 스택 $n\ge 2$개를 갖는 DPDA 혹은 NPDA는 테이프 하나를 갖는 DTM으로 시뮬레이션할 수 있다.

그런데 DTM은 스택 2개를 갖는 DPDA로 시뮬레이션할 수 있다. DTM의 헤드를 왼쪽으로 움직이는 것은 첫 번째 스택에서 글자를 읽는 것으로, 헤드를 오른쪽으로 움직이는 것은 두 번째 스택에서 글자를 읽는 것으로 대체할 수 있다. 마찬가지로 글자를 쓰는 행위는 첫 번째 혹은 두 번째 스택에 글자를 push하는 것으로 대체할 수 있다. 따라서 스택 2개짜리 DPDA는 DTM을 시뮬레이션할 수 있다.

결론적으로 스택 3개, 4개, 혹은 그 이상을 갖는 DPDA는 모두 스택 2개를 갖는 DPDA로 시뮬레이션할 수 있다. (6주차 1차시 27분부터)

그래서 이걸 어디다 써먹어요?

재밌잖아? (실제로 하신 말)

Universal Turing Machine (UTM)

UTM은 단 하나의 Turing machine으로 모든 튜링 머신을 시뮬레이션하기 위해 고안되었다. 그런데 이는 매우 어려운 문제처럼 보인다. 튜링 머신마다 사용하는 알파벳, 전이함수, 상태가 전부 다른데 어떻게 이러한 것들을 일반화할 수 있을까?

UTM은 $\{0,1\}$을 알파벳으로 사용한다. 그러면 $\{0,1\}n$개를 사용하여 최대 $2^n$개의 다른 알파벳을 표현할 수 있고, 마찬가지로 $\{0,1\}m$개를 사용하여 최대 $2^m$개의 상태를 표현할 수 있다. 이진수로 모든 정보를 인코딩하여 표현하는 것이다. 마치 현대의 컴퓨터 같지 않나?

UTM은 상태를 표현하는 테이프, 전이함수를 표현하는 테이프, 입력이 주어지는 테이프까지 총 3개의 테이프를 사용한다. 임의의 튜링 머신의 상태, 전이함수, 입력은 모두 $\{0,1\}$만을 이용하여 인코딩할 수 있으므로 UTM은 임의의 튜링 머신을 시뮬레이션할 수 있다.

당연한 얘기같지만 절대로 그렇지 않다, UTM 이전에 고안되었던 컴퓨터는 정렬, 암호 해독 등의 특정한 목적만을 위해 설계되었다. UTM이 제안된 이후 상태, 전이함수, 입력을 하나로 묶어 소프트웨어라는 새로운 개념이 생겨났고, 흔히 최초의 컴퓨터라고 언급되는 ENIAC은 일반적인 일을 할 수 있는 하드웨어에 탄도를 계산하는 소프트웨어를 탑재하여 만들어졌다.

...그렇구나. 끄덕끄덕

Classes

이제는 튜링 머신의 Class에 대해 생각해 보자. Class는 Language의 집합이다. 까먹은 건 아니겠지?

튜링 머신의 Class는 다음과 같이 나눌 수 있다.

Class E: Enumerable Class

$L\in E\iff \mathrm{\exists }M,M(X)\{\begin{array}{ll}halts& X\in L[Yes]\\ does{n}^{\prime }thalt& X\notin L[No]\end{array}$

$E$는 Turing Machine으로 풀리는 문제의 집합이다. '문제를 푼다'의 정의를 명확하게 하기 위해 위의 식을 제시한 것이다. 뒤쪽의 $M(X)$~ 부분은 M이 L을 Enumerate 방식으로 푼다고도 한다.

그런데 $M(X)$가 멈추지 않는 게 문제를 푼 건가? 답이 Yes일 때와 No일 때 $M$의 행동이 다르므로 논리적으로는 $M$이 $X$를 푼 게 맞다. 아니 근데 계산이 끝나지 않는 건지, 아니면 단지 계산이 오래 걸릴 뿐인 건지 어떻게 구분할 건데?

어떤 $X$에 대해서는 머신을 들여다보면 $M(X)$가 끝날지 끝나지 않을지 알 수 있다. 물론 모든 $X$에 대해 알 수 있는 것은 아니다. 그래서 사실 이 정의는 조금 애매하다.

Class co-E: Complementary Enumerable

$L\in E\iff \mathrm{\exists }M,M(X)\{\begin{array}{ll}halts& X\notin L[No]\\ does{n}^{\prime }thalt& X\in L[Yes]\end{array}$

Class E에서 Yes와 No만 바꾼 형태이다. 이 정의를 이용하면 $L\in E\iff L^c\in co-E$임을 증명할 수 있다. 여기서 $L^c=\sum ^{\ast }-L$, 즉 $L$의 여집합이라 생각하면 된다. 

$L\in E$일 때 $L^c\in E$이 아닐 수도 있지만 $L^c\in co-E$는 참이며 그 역도 성립한다.

Class D: Decidable

$L\in D\iff \mathrm{\exists }M,M(X)=\{\begin{array}{ll}Yes& X\in L\\ No& X\notin L\end{array},haltsalways$

이 정의는 Class E보다 더 그럴듯해 보인다. 문제를 풀 수 없을 때에도 답을 줘야 하지 않겠는가? 

다음 시간에 Class E와 Class D가 같은지 다른지에 대해 알아보도록 하자.