[계산이론] - (16) 튜링 기계 (Turing Machines)

 

 

 

 

서론

앞서 배운 유한 오토마타와 푸시다운 오토마타를 비교해보면, 임시 저장장소의 특성이 둘 사이의 차이를 만들어냄을 알 수 있습니다.

만약 저장장소가 없다면 유한 오토마타이며, 저장장소가 스택이라면 유한 오토마타보다 더 강력한 푸시다운 오토마타를 갖게 됩니다.

 

만약 오토마타에 좀 더 유연한 저장장소를 더해준다면, 더욱 강력한 언어군을 발견할 수 있을 것입니다.

예를 들어 두 개, 세 개의 스택, 큐, 또는 다른 저장 장치를 사용한다면 어떤 결과가 나올까요?

각각의 저장장소는 새로운 종류의 오토마타를 정의하고, 그것을 통하여 새로운 언어군을 정의할 수 있을까요?

 

이러한 접근은 대부분의 경우 흥미로운 결과를 이끌어내지는 못했습니다.

 

가장 강력한 오토마타와 계산의 한계에 대하여 무엇을 이야기할 수 있을까요?

이 질문은 튜링 기계의 기초적인 개념을 이끌어내고, 이어서 기계적인 혹은 알고리즘적인 계산이라는 개념의 정확한 정의를 이끌어냅니다.

 

우리는 튜링 기계의 공식적인 정의로부터 시작하여, 몇몇 간단한 프로그램을 통해 무엇이 연관되어 있는가에 대해 알아볼 것입니다.

이후 튜링 기계는 꽤나 원시적인데 반하여, 매우 복잡한 계산과정을 처리할 수 있을 정도로 그 개념이 광범위하다는 것을 알아볼 것입니다.

이는 현재의 컴퓨터로 처리할 수 있는 모든 계산은, 튜링 기계에서 처리될 수 있다고 이야기하는 튜링 명제(Turing thesis)로 마무리됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

튜링 기계의 저장장소

강력한 오토마타는 복잡하고 정교한 저장장소를 갖는다고 생각할 수 있습니다.

그러나 튜링 기계의 저장장소는 실제로 아주 간단합니다.

그 저장장소는 셀(cell)들의 1차원 배열로 구체화 할 수 있습니다.

 

각 셀은 하나의 심벌을 저장할 수 있습니다.

이 배열은 양쪽으로 무한히 확장되고, 따라서 무한한 양의 정보를 저장할 수 있습니다.

그 정보는 임의의 순서로 읽을 수 있고 변경할 수 있습니다.

 

이러한 저장장소를 오래전의 컴퓨터에서 사용되었던 자성 테이프와 유사하기 때문에, 테이프(tape)라 부릅니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

튜링 기계

튜링 기계는 임시 저장장소가 테이프인 오토마타입니다.

이 테이프는 셀들로 나뉘어있고, 각 셀은 한 개의 심벌(symbol)을 저장할 수 있습니다.

 

테이프에는 읽기-쓰기 헤드(read-write head)가 부착되어 있습니다.

 

읽기-쓰기 헤드는 왼쪽 또는 오른쪽으로 움직일 수 있고, 각 이동마다 하나의 심벌을 읽고 쓸 수 있습니다.

 

튜링 기계로 사용하는 오토마타는 입력 파일이나 특별한 출력장치가 없습니다.

 

필요한 입력과 출력은 테이프에서 이루어집니다.

 

 

 

정의

튜링 기계 M은 다음과 같이 정의됩니다.
$$M =(Q, \Sigma, \Gamma. \delta, q_0 , B, F)$$
$Q$  : 내부 상태들의 집합
$\Sigma$  : 입력 알파벳 $(\Sigma \subseteq (\Gamma - B))$
$\Gamma$  : 테이프 알파벳이라 불리는 심벌들의 유한 집합
$\delta$  : 전이 함수
$B \in \Gamma$  : 공백(Blank)이라 불리는 특별한 심벌
$q_0 \in Q$  : 초기 상태
$F \subseteq Q$  : 승인 상태들의 집합

튜링 기계의 정의에서, $\Sigma \subseteq \Gamma - \left\{ B \right\}$ 를 가정합니다.

 

즉 입력 알파벳은 공백 심벌을 포함하지 않는 테이프 알파벳의 부분집합입니다.

 

전이 함수 $\delta$ 는 다음과 같이 정의됩니다.

$$\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R \right\}$$

이에 대한 해석은 튜링 기계가 작동하는 원칙을 제시합니다.

$\delta$ 의 인수들은 제어 장치의 현재 상태와 현재 읽혀지는 테이프 심벌입니다.

 

그 결과는

제어 유닛의 새로운 상태
기존의 심벌을 교체하는 새로운 테이플 심벌
이동 심벌인 $L$ 또는 $R$ 입니다

이동 심벌을 테이프에 새로운 심벌이 쓰여진 후 읽기-쓰기 헤드가 왼쪽 또는 오른쪽으로 이동하는지를 표현합니다.

 

 

 

튜링 기계는 전이함수 $\delta$ 가 정의되지 않은 형상(configuration)에 도달할 때 정지(halt)한다고 말합니다.

종료 시 상태가 최종상태라면 성공,
그렇지 않다면 실패합니다.

 

 

 

예시

다음과 같이 정의된 튜링 기계에 대하여,

$$Q = \left\{    q_0, q_1\right\}$$

$$\Sigma = \left\{   a,b \right\}$$

$$\Gamma = \left\{ a,b,B    \right\}$$

$$F = \left\{  q_1  \right\}$$

 

그리고

$$\delta(q_0, a) = (q_0 , b, R)$$

$$\delta(q_0, b) = (q_0, b, R)$$

$$\delta(q_0, B) = (q_1 , B, L)$$

 

만약 이 튜링 기계가 읽기-쓰기 헤드 아래에 심벌 a를 가지고 상태 q_0에서 시작한다면, 적용할 수 있는 전이 규칙은 $\delta(q_0, a) = (q_0 , b, R)$ 입니다.

 

그러므로 읽기-쓰기 헤드는 테이프에서 a를 b로 교체한 뒤 오른쪽으로 이동합니다.

 

현재 상태는 그대로 $q_0$ 입니다.

 

그림으로 전체 동작을 확인해 보겠습니다.

 

 

 

 

 

 

 

 

 

전이표

튜링 기계를 전이표를 이용하여 표현할 수 있습니다.

예시

다음 튜링 기계에 대하여

$$M = (Q, \Sigma, \Gamma, \delta, q_0, B, \left\{ q_1 \right\} )$$

 

전이함수를 이용한 표현이 다음과 같을 때,

$$Q = \left\{ q_0, q_1 \right\}$$

$$\Sigma = \left\{ 0,1\right\}$$

$$\Gamma = \left\{ 0,1,B\right\}$$

$$\delta : \delta(q_0, 0) = (q_0, 0, R) $$

$$\delta(q_0, B) = (q_1, B, R) $$

 

 

이를 전이표를 이용하여 표현하면 다음과 같습니다.

$$\delta$$	0	1	B
$$q_0$$	$$(q_0, 0, R)$$	-	$$(q_1, B, R)$$
$$q_1$$	-	-	-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

표준 튜링 기계

1. 튜링 기계는 왼쪽과 오른쪽 이동을 여러번 허용하는 양방향으로 한정되지 않은 하나의 테이프를 가집니다.

2. 튜링 기계는 $\delta$ 가 각 형상에 대하여 최대 하나의 전이를 정의한다는 의미로서 결정적입니다.

3. 특별한 입력 장치가 없습니다. 우리는 시작에 테이프가 어떤 특별한 내용을 가지고 있다고 가정합니다.

유사하게 특별한 출력 장치가 없습니다. 기계가 정지할 때마다 테이프의 내용의 일부 혹은 전체를 출력으로 볼 수 있습니다.

 

 

 

 

 

 

 

 

순간적 묘사

pda의 경우와 마찬가지로 튜링 기계의 형상들을 표시하기 위하여 순간적 묘사를 사용합니다.

모든 형상은 제어 유닛의 현재 상태, 테이프의 내용, 읽기-쓰기 헤드의 위치로 완전히 결정됩니다.

 

다음과 같이 표기합니다.

$$x_1 q x_2$$
또는
$$a_1a_2...a_{k-1} q a_k a_{k+1} ... a_n$$

 

심벌 $a_1, ..., a_n$ 들은 테이프의 내용을 나타내고,

반면 $q$ 는 제어 장치의 상태를 설명합니다.

이는 읽기-쓰기 헤드의 위치가 $q$ 의 바로 뒤에 있는 심벌에 해당하는 셀이 되도록 한 것입니다.

 

 

공백은 일반적으로 표시하지 않으나, 공백이 계산이 사용되는 경우 표기헙니다.

 

 

 

예시

다음과 같은 전이 함수를 가진 튜링 기계와

$$\delta(q_0, a) = (q_0 , b, R)$$

$$\delta(q_0, b) = (q_0, b, R)$$

$$\delta(q_0, B) = (q_1 , B, L)$$

 

입력 스트링 aab에 대한 순간적 묘사는 다음과 같습니다.

$$q_0 aab \vdash bq_0ab   \vdash bbq_0b  \vdash bbb q_0 B$$
$$\vdash bb q_1 b $$

$$q_0abb \overset{*}{\vdash} bbq_1 b$$

 

 

 

 

 

 

 

 

 

 

 

 

 

 

계산 (computation)

만약 임의의 $q_j$ 와 $a$ 에 대하여 $x_1 q_i x_2 \overset{*}{\vdash} y_1 q_j a y_2$ 이고, $\delta(q_j, a)$ 가 정의되어 있지 않으면 정지한다고 말합니다.
이때 정지 상태에 이르는 형상들의 순서열을 계산이라 부릅니다.

 

튜링 기계가 종료되어야 계산이라 부를 수 있으며, 만약 무한루프 상태에 있어 종료되지 않는 경우 다음과 같이 표기합니다.

$$x_1 q x_2  \overset{*}{\vdash} \infty$$

 

 

 

 

 

 

 

 

 

언어 승인기로서의 튜링 기계

튜링 기계는 다음의 의미로서 승인기로 볼 수 있습니다.

한 문자열 w가 테이프에 적혀 있습니다.

사용되지 않은 부분은 공백 심벌로 채워져 있습니다.

기계는 읽기-쓰기 헤드가 w의 가장 왼쪽에 위치하며, 초기 상태 $q_0 $ 에서 시작합니다.

일련의 이동 후에, 만약 튜링 기계가 승인 상태에 놓이고 정지하면 w가 승인된 것으로 생각합니다.

$M =(Q, \Sigma, \Gamma. \delta, q_0 , B, F)$ 을 튜링 기계라 하면, M에 의하여 승인되는 언어는 다음과 같이 정의됩니다.
$$L(M) = \left\{ w \in \Sigma^{+} : q_0 w \overset{*}{\vdash} x_1 q_f x_2 \;\; for \; some \; q_f \in F , (x_1, x_2) \in \Gamma^{*}\right\}$$

 

 

 

 

 

 

 

 

 

 

 

 

 

변환기로서의 튜링 기계

튜링 기계는 일반적인 컴퓨터에 대한 간단한 추상적 모델을 제시합니다.

컴퓨터의 주요한 목적은 입력을 출력으로 변환시키는 것이기 때문에, 컴퓨터는 변환기로서 작동합니다.

만약 튜링 기계를 사용하여 컴퓨터를 모델링하려 한다면, 변환기로서의 튜링 기계에 대한 해석을 자세히 살펴보아야 합니다.

 

계산에 대한 입력은 초기에 테이프에 있는 공백 심벌이 아닌 모든 심벌들입니다.

계산의 종결에서 출력은 그때 테이프에 있는 모든 것입니다.

 

 

따라서, 우리는 튜링 기계 M이 어떤 승인상태 $q_f$ 에 대하여, 다음과 같은 계산을 수행한다면

$$q_0 w \overset{*}{\vdash} q_f \hat{w} $$

 

해당 튜링 기계 M은 변환기로서, 다음과 같이 정의된 함수 $f$ 의 구현으로 간주할 수 있습니다.

$$\hat{w} = f{w}$$

 

 

 

정의

정의역이 D인 함수 $f$ 에 대하여, 만약 아래의 조건을 만족하는 튜링 기계 $M =(Q, \Sigma, \Gamma. \delta, q_0 , B, F)$ 가 존재한다면, 함수 $f$ 를 튜링 계산 가능(Turing-computable) 또는 계산 가능(computable)이라 부릅니다.

$$q_0 w \overset{*}{\vdash} q_f f(w)$$
이때 $w \in D$ 이며, $q_f \in F$ 입니다.