6주차 1차시

2-Tape DTM

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

 

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

$(p,a,b) \rightarrow (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 \Leftrightarrow \exists ~M,~M(X)\begin{cases}halts & X \in L ~[Yes] \\doesn't~halt & X \notin L~[No] \end{cases}$

 

$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 \Leftrightarrow \exists ~M,~M(X) \begin{cases} halts & X \notin L ~[No] \\doesn't~halt & X \in L~[Yes] \end{cases} $

 

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

 

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

``Class D``: Decidable

$L \in D \Leftrightarrow \exists ~M,~M(X)=\begin{cases}Yes & X\in L\\No & X \notin L \end{cases},~halts~always$

 

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

 

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