2023-2학기/계산이론

[계산이론] #05. Turing Machine

AlriC 2023. 10. 6. 00:54

지금까지 저희는 Finite Automata, 그러니까 유한한 메모리를 가진 Machine을 다루었는데요. 이번 글에서는 무한한 메모리를 이용해 명령을 처리하는 새로운 방식의 Machine인 Turing Machine에 대해 알아볼 것입니다.

 

Turing Machine의 정의

Turing Machine의 예시

먼저 Tape에 대해 알아보겠습니다. 하나의 Turing Machine은 $k \geq 1$개의 Tape을 가질 수 있습니다. 각 Tape은 Cell로 구성되어 있으며, 좌우로 무한개의 Cell이 쭉 늘어져있습니다. 각각의 Cell은 유한 집합 $\Gamma $의 원소 중 하나를 저장하고 있습니다. 여기서 $ \Gamma $는 Tape Alphabet이라고 불립니다. 여기서 Tape Alphabet은 항상 $\square$라는 원소를 포함하는데요, 이는 Blank(공백)를 의미합니다. 즉, Cell이 이 $\square$를 가지면, 그 Cell은 비어있다는 뜻입니다.

각 Tape은 각자의 Tape Head를 가지고 있는데요, (그림에서의 빨간 화살표) 이 Tape Head는 하나씩의 Cell을 가리키면서 Tape을 따라 움직일 수 있습니다. 이 Tape Head는 Cell에 존재하는 Symbol을 읽고, 다른 Symbol로 교체하는 작업을 수행할 수 있습니다.

마지막으로 State Control에 대해 알아보겠습니다. State Control은 유한개의 State 중 하나를 가집니다. 이 State Control이 어떤 State에 있느냐에 따라 Tape Head가 어떤 동작을 하는지가 결정됩니다. 가능한 모든 State의 집합을 보통 $Q$라고 표시합니다. $Q$의 원소 중 Start State, Accept State, Reject State는 특별한 State로, 각자의 역할이 존재합니다.

Turing Machine은 여러개의 Computation Step을 순서대로 진행하는 방식으로 동작합니다. 하나의 Step에서, Turing Machine은 아래의 작업을 수행합니다.

  1. Computation Step 직전, Turing Machine의 State를 $r$이라고 하겠습니다. 각 $k$개의 Tape Head는 특정 Cell에 존재하는 상태입니다.
  2. 현재 State $r$, 그리고 Tape Head가 읽은 $k$개의 Symbol에 따라서,
    1. 현재 State를 $r'$으로 변경합니다. ($r=r'$일 가능성도 있습니다.)
    2. 각 Tape Head가 있는 Cell에 새로운 Symbol을 작성합니다.
    3. 각 Tape Head가 왼쪽이나 오른쪽으로 한 칸 이동하거나, 제자리에 가만히 있습니다.

 

그리고, 이런 과정들을 저희는 수학적 표현으로 바꿀 수 있습니다. Deterministic Turing Machine은 아래와 같은 7-tuple로 표현 가능합니다.

$$M=\left ( \Sigma, \Gamma, Q, \delta, q, q_{accept}, q_{reject} \right )$$

  • $\Sigma$는 Input Alphabet이라 불리는 유한집합으로, Cell에 들어갈 수 있는 Symbol의 집합입니다. 이때, Blank Symbol은 $\Sigma$에 포함되지 않습니다.
  • $\Gamma$는 Tape Alphabet이라 불리는 유한집합으로, $\Gamma =\left\{ \square \right\} \cup \Sigma \subseteq$입니다.
  • $Q$는 State들의 집합입니다.
  • $\delta$는 Transition Function이라 불리는 함수로, $\delta : Q\times \Gamma^k \to Q\times \Gamma^k \times \left\{ L, R,N \right\}^k$입니다.
    • Transition Function은 하나의 Computation Step에 Turing Machine이 어떤 짓을 할지 결정합니다. 
    • 함수의 입력값 $ Q\times \Gamma^k $는 현재 State와 $k$개의 Tape Head가 읽은 각 Symbol을 의미합니다.
    • 함수의 출력값 $ Q\times \Gamma^k \times \left\{ L, R,N \right\}^k $는 이 Computation Step 이후의 State와 각 Tape Head가 있는 Cell에 새로 작성할 $k$개의 Symbol과 각 Tape Head가 어디로 이동할지를 의미합니다. ($L$은 왼쪽, $R$은 오른쪽, $N$은 자리를 유지한다는 의미입니다.)
  • $q \in Q$는 Start State입니다.
  • $q_{accept} \in Q$는 Accept State입니다.
  • $q_{reject} \in Q$는 Reject State입니다.

 

그리고, 하나의 Computation Step은 아래와 같이 표시합니다.

$$ra_1a_2\cdots a_k \to r'a_1'a_2'\cdots a_k'\sigma_1\sigma_2\cdots \sigma_k $$

Turing Machine이 어떤 행동을 하는지 이해하셨다면, 위 기호들이 무엇을 의미하는지 대충 감이 오실 겁니다. $r$은 현재 State, $a_i$는 각 Tape Head가 읽은 Sybmol을 의미합니다. $r'$은 Computation Step 이후의 State, $a_i'$는 각 Tape Head가 새롭게 작성할 Symbol, $\sigma_i$는 $L,R,N$중 하나로 Tape Head가 어디로 이동할지를 의미합니다.

 

TM(Turing Machine)에 문자열을 집어넣는다는 의미는, 그 문자열을 첫번째 Tape에 쭉 밀어 넣고 나머지 Cell에는 $\square$를 넣은 뒤, Tape Head를 가장 왼쪽 Symbol에 놔두는 것을 의미합니다. 그리고 Computation Step을 쭉 진행하다가, $q_{accept}$ 혹은 $q_{reject}$에 도달했을 때 작동이 중지됩니다. 작동이 중지되었을 때의 State가 $q_{accept}$일 경우, Input String을 $M$이 Accept 한다고 표현합니다. (이 부분은 DFA와 거의 동일합니다.)

또한, DFA와 마찬가지로 TM $M$이 Accept하는 모든 문자열의 집합을 $L\left(M \right)$ 이라고 표기합니다.

 

TM의 활용 : Palindrome

Palindrome은 앞으로 읽으나, 뒤로 읽으나 같은 문자열을 부르는 말입니다. $\Sigma=\left\{a, b\right\}$에 대해 생각해 보자면, $abbabba$는 Palindrome입니다. $abbaaba$는 아니고요.

이 Palindrome만을 포함하는 Language는 Nonregular Language인데요. 이 말은 이 Language를 Accept하는 Finite Automata가 존재하지 않는다는 뜻입니다. 그런데, 이 Language를 Accept하는 TM은 존재합니다. 나중에 더 자세하게 다루겠지만, TM은 Finite Automata보다 훨씬 강력합니다.

그럼 이제 TM을 한번 설계해볼까요?

 

이렇게 $abbaaba$를 읽는다고 생각해 봅시다. 이 문자열은 Palindrome이 아니므로 TM은 위 문자열을 Reject 해야겠죠? 가장 처음에는 첫 번째 Symbol과 마지막 Symbol이 같은지를 확인할겁니다. 그 이후 두번째 Symbol과 마지막에서 두번째 Symbol이 같은지를 확인하고, 그렇게 계속 반복하다가 Symbol이 남지 않을때 까지 진행하는게 전략입니다.

먼저 이 상태에서, Tape Head가 $a$를 읽고 State를 $q_a$로 바꾸는 방식으로 첫 번째 문자가 $a$라는 사실을 저장할겁니다. 그리고, 첫번째 Symbol을 $\square$로 바꾸고 Head를 가장 오른쪽으로 이동시킬 겁니다.

이제 Head가 $\square$를 읽었으니 가장 끝에 도달했다는 사실을 TM이 알아챌 수 있습니다. 가장 오른쪽에 도달했다는 사실 역시 TM이 저장하고 있어야 하므로, State를 $q_a$에서 $q_a'$으로 변경한 뒤 왼쪽으로 한 칸 이동합니다.

이제 현재 State $q_a'$과 읽은 Symbol $a$를 바탕으로, 첫 문자와 마지막 문자가 같다는 사실을 확인할 수 있습니다. 이제 가장 마지막에 있는 $a$도 지우고 다시 제일 왼쪽으로 이동합니다.

이제 두 번째 Symbol이 $b$라는 사실을 저장하기 위해 State를 $q_b$로 바꾸고, 두번째 자리에 $\square$를 넣은 뒤 같은 과정을 반복하면 되겠죠?

이렇게 두번째 Symbol과 마지막에서 두번째 Symbol이 $b$로 동일함을 확인하고, 세 번째 Symbol로 돌아왔습니다. 이제 똑같은 과정을 다시 해볼까요?

제일 왼쪽에서 $b$를 읽었는데, 오른쪽에는 $a$가 있죠? 이 사실을 바탕으로 이 TM은 Reject라는 결과를 뱉어냅니다.

 

이제 이 TM이 어떻게 동작하는지는 대충 이해하셨을 듯합니다. 이제 그럼 이렇게 작동하는 TM을 수학적 표현으로 나타내보겠습니다. 먼저 $\Sigma, \Gamma$는 간단하죠? $\Sigma=\left\{a, b \right\}$이고 $\Gamma=\left\{a, b, \square \right\}$입니다.

State는 아래와 같습니다.

  • $q_0$ : Start State
  • $q_a$ : 가장 왼쪽에 있는 Symbol이 $a$임을 나타냅니다. 이 상태에서 Head는 오른쪽으로 움직입니다.
  • $q_b$ : 가장 왼쪽에 있는 Symbol이 $b$임을 나타냅니다. 이 상태에서 Head는 오른쪽으로 움직입니다.
  • $q_a'$ : 오른쪽 끝에 도착했다는 사실을 나타냅니다.
  • $q_b'$ : 역시 오른쪽 끝에 도착했다는 사실을 나타냅니다.
  • $q_L'$ : 가장 왼쪽 Symbol과 가장 오른쪽 Symbol이 같았음을 나타냅니다. 이 상태에서 Head는 왼쪽으로 움직입니다.
  • $q_{accept}, q_{reject}$

 

Transition Function은 아래와 같습니다.

TM이 동작하는 과정은 위에 예시를 통해 자세히 설명해 두었으니, 하나하나 읽어보시면 이해가 될 것이라고 생각이 됩니다.

 

이제 정확히 같은 행동을 하는 TM인데, 2개의 Tape을 사용하도록 만들어보겠습니다.

시작은 이런 모습일 겁니다. 이제 2개의 Tape이 동시에 오른쪽으로 움직이면서, 위쪽 Tape에 있는 문자를 그대로 아래쪽 Tape에 복사할 겁니다.

이렇게요. 이렇게 $\square$가 읽히면, 일단 두 Tape 전부 왼쪽으로 한 칸 이동합니다.

이제 이 상태에서, 첫 번째 Tape만 다시 왼쪽 끝으로 이동합니다.

이 상태가 되었으면 첫번째 Tape은 오른쪽으로, 두 번째 Tape은 왼쪽으로 이동하며 두 Tape이 같은 Symbol을 읽어 들이는지를 확인하는 겁니다. 이 상태에서 같은 Symbol을 읽는다는 말은, 첫 번째 Symbol과 마지막 Symbol이 같다는 것을 의미하니까요.

이 상태에서 또 같은 Symbol이 읽히겠죠? 그 말은 두 번째 Symbol과 마지막에서 두번째 Symbol이 같다는 것을 의미합니다. 이제 같은 행동을 계속 반복하다가, 다른 Symbol이 읽히는 순간이 오면 이 문자열은 Palindrome이 아닙니다.

이렇게요. 이 시점에서 이 TM은 이 문자열을 Reject 하게 됩니다. 이 TM도 수학적 표현으로 바꿔볼까요? 일단 $\Sigma, \Gamma$는 위와 동일합니다.

State는 아래와 같습니다.

  • $q_0$ : Start State. 이 상태에서 두 Head는 오른쪽으로 이동하며, TM은 첫 번째 Tape의 문자열을 두 번째 Tape으로 복사합니다.
  • $q_1$ : 문자열 복사가 완료되었다는 것을 의미합니다. 이 상태에서는 첫 번째 Head만 왼쪽으로 이동합니다.
  • $q_2$ : 실제 문자열을 확인하는 상태입니다. 이 상태에서는 첫번째 Head는 오른쪽으로, 두 번째 Head는 왼쪽으로 이동합니다.
  • $q_{accept}, q_{reject}$

 

Transition Function은 아래와 같습니다.

 

또 다른 TM의 활용 예시

이번에는 $\left\{a^nb^nc^n:n\geq 0 \right\}$를 Accept 하는 TM을 한번 설계해 보겠습니다. 이제 다들 아시겠지만, 이는 Nonregular Language로 DFA로는 표현할 방법이 없습니다.

일단, 먼저 주어진 문자열이 $a^* b^* c^*$인지를 먼저 확인해야 합니다. 가장 왼쪽에서부터 시작해서 $a$를 읽으면 $q_a$ 상태로 변경하고, 이 상태에서 $b$를 읽으면 $q_b$ 상태로 변경하고, 이 상태에서 $c$를 읽으면 $q_c$ 상태로 변경하고, 이 상태에서 가장 오른쪽에 도달하면 주어진 문자열이 $a^* b^* c^*$ 형태라는 뜻이겠죠. 

여기까지의 과정 먼저 수학적 표현으로 바꿔보겠습니다. 이 과정에서 각 State는 아래와 같습니다.

  • $q_a$ : Start State (어차피 첫 Symbol은 $a$여야 하므로)
  • $q_b$ : $b$ 구역을 통과하는 과정을 의미합니다.
  • $q_c$ : $c$ 구역을 통과하는 과정을 의미합니다.
  • $q_L$ : 가장 마지막 Symbol에 도달했음을 의미합니다.

 

그리고 Transition Function은 아래와 같습니다.

$d$라는 문자가 보이는데, 이건 다음 단계에서 필요한 Symbol이기 때문에 이 단계에서는 고려할 필요가 없습니다.

이제 주어진 문자열이 $a^* b^* c^*$형태임을 확인했으니, $a$의 개수와 $b$의 개수와 $c$의 개수가 같은지를 확인해 보면 되겠죠. 전략은 이겁니다. 왼쪽에서부터 시작해서 Symbol을 읽어나가다가, 가장 처음 $a$를 읽으면 그 자리에 있던 $a$ 대신에 $d$를 넣습니다. 그리고 그 이후에는 $a$는 무시하고, $b$를 읽으면 그 자리에 $d$를 넣습니다. 그 이후에는 $b$는 무시하고 $c$를 읽으면 그 자리에 $d$를 넣습니다.

여기까지의 과정을 $aabbbcc$를 예시로 보여드리겠습니다.

이 상태가 되면 $a, b, c$ 하나씩이 $d$로 바뀐 형태가 되겠죠. 이제 Head를 다시 왼쪽 끝으로 이동시킨 뒤 과정을 반복합니다.

똑같은 과정을 한번 더 합니다.

어? $a$를 먼저 입력받아야 하는데 $b$가 입력됐죠? 그 말은 문자열 전체에 $a$가 2개 있었는데, $b$는 3개 이상이 존재한다는 것을 의미합니다. 이 시점에서 이 TM은 위 문자열을 Reject 하는 겁니다.

이제 이 단계를 수학적 표현으로 나타내볼까요? 각 State는 아래와 같습니다.

  • $q_a'$ : 2번째 단계에 진입했으며, $a$를 찾고 있음을 의미합니다.
  • $q_b'$ : 가장 왼쪽에 있는 $a$가 $d$로 교체되었으며, $b$를 찾고 있음을 의미합니다.
  • $q_c'$ : 가장 왼쪽에 있는 $a$와 $b$가 $d$로 교체되었으며, $c$를 찾고 있음을 의미합니다.
  • $q_L'$ : 가장 왼쪽에 있는 $a$, $b$, $c$가 전부 $d$로 교체되었으며, 다시 왼쪽 끝으로 돌아가고 있음을 의미합니다.

 

Transition Function은 아래와 같습니다.

 

이렇게 $\left\{a^nb^nc^n:n\geq 0 \right\}$를 Accept 하는 TM을 만들 수 있었습니다. 그런데, 새로운 문자 $d$를 사용하지 않고는 만들 수 없을까요? 

제가 이 말을 하는 이유가 뭐겠습니까. 당연히 있습니다. 기본적인 전략은 먼저 왼쪽에서 오른쪽으로 진행하면서, 가장 왼쪽에 있는 $a$와 가장 왼쪽에 있는 $b$, 그리고 가장 오른쪽에 있는 $c$를 지워줍니다. 아래는 그 예시로 $aaabbbccc$를 TM에 입력했다고 생각한 것입니다.

여기까지를 1단계라고 합시다. 2단계에서는, Head를 다시 오른쪽으로 보내면서 중간에 있는 $\square$를 없애면서 $bbcc$를 한 칸 왼쪽으로 옮기는 겁니다.

이렇게 진행되면 $a$, $b$, $c$가 각각 하나씩 줄어든 꼴이므로, 위 과정을 반복하면 저희가 원하는 결과를 얻을 수 있겠죠? 

 

Multi-Tape TM

아까 TM의 첫 번째 예시로 Palindrome을 Accept 하는 TM을 들었었는데요. Tape가 1개인 TM도 있었고, Tape가 2개인 TM도 있었습니다. 저희가 보기에는 1개의 Tape을 가진 TM이 훨씬 더 간단해 보였잖아요? 그러면 2-Tape TM이 1-Tape TM보다 더 강력할까요? 사실 그건 아닙니다. 왜냐하면 어떠한 Multi-Tape TM이라도 1-Tape TM으로 변환 가능하기 때문입니다.

2-Tape TM인 $M$을 1-Tape TM인 $N$으로 변환하는 과정을 한번 생각해 보겠습니다. 기본적인 아이디어는 아래와 같습니다.

먼저, 2개의 Tape을 한 줄로 합치고 처음과 그 사이, 마지막에 #을 추가하여 영역을 구분해 줍니다. 하나의 Step에서, $N$은 $M$의 현재 상태를 기억합니다. $N$의 Head는 가장 왼쪽에 있는 #에서 시작하여 오른쪽으로 이동합니다. 그러다가 처음 점이 달린 Symbol에 도달하면, 그 Symbol이 무엇인지를 기억하고 계속 진행합니다.

그러다가 2번째 점이 달린 Symbol에 도달하면, $N$의 Head는 도달한 Cell의 값을 "$M$이 2번째 Tape에 주는 변화와 같도록" 업데이트합니다. 이제 다시 $N$의 Head는 왼쪽으로 이동해서 1번째 점이 달린 Symbol에 다시 도달하면, $M$이 1번째 Tape에 주는 변화와 같도록 Cell의 값을 업데이트합니다.

이런 방식을 반복하게 되면 $M$이 수행하는 것과 정확히 같은 동작을 수행하는 1-Tape TM $N$을 만들 수 있습니다.

 

Church-Turing Thesis

지금까지 저희는 TM에 의해 나타내질 수 있는 알고리즘을 여러 개 알아보았는데요, 과연 모든 알고리즘이 TM에 의해 해결 가능할까요?

결론부터 말하자면 아닙니다. 하나의 예시로, 다항방정식이 정수해를 가지는지 판별하는 알고리즘을 TM으로 작성하는 방법은 현재 알려져 있지 않습니다.

1-Tape TM, k-Tape TM, Non-deterministic TM, Java 프로그램, C++ 프로그램. 이 모든 모델들은 전부 Equivalent 합니다. 1-Tape TM이 해결 가능한 문제는 C++ 프로그램으로 해결 가능하고, Java 프로그램으로 해결 불가능한 문제는 k-Tape TM으로도 해결 불가능합니다. 이런 문제들을 우리는 Church-Turing Thesis, 처치-튜링 문제라고 부릅니다.

 

마무리

이번 글에서는 Turing Machine이 무엇인지, 그리고 DFA로는 나타낼 수 없었던 Language들을 어떻게 하면 TM으로 나타낼 수 있는지에 대해 알아보았습니다.

감사합니다.

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.
저작자표시 변경금지 (새창열림)