튜링 기계

 

형식 언어와 오토마타 : Peter Linz 저서, 장직현. 김응모. 엄영익. 한광록 공역, 사이텍미디어, 2001 (원서 : An Introduction to Formal Languages and Automata. 3rd ed, Jones and Bartlett. 2001), Page 233~260

 

1. 표준 튜링 기계

     (1) 튜링 기계의 정의

     (2) 언어 승인기로서의 튜링 기계

     (3) 변환기로서의 튜링 기계

     연습문제

2. 복잡한 태스크를 위한 튜링 기계 결합

     연습문제

3. 튜링 명제

     연습문제

 

앞서의 논의에서, 우리는 몇몇 기본적인 개념들, 특히 정규 언어와 문맥-자유 언어의 개념과 유한 오토마타와 푸시다운 승인기와의 연관들을 다루었다. 우리는 정규 언어가 문맥-자유 언어의 진부분 집합이고, 따라서 푸시다운 오토마타가 유한 오토마타보다 더 강력하다는 것을 밝혀냈다. 또한 우리는 문맥-자유 언어가, 프로그래밍 언어의 연구에 기초가 되지만, 범위에 있어서 제한되는 것을 확인하였다. 이러한 사실은 {anbncn} 과 {ww} 와 같은 몇몇 간단한 언어가 문맥-자유 언어가 아님을 밝힘으로써 앞장에서 명백해졌다. 이런 사실은 우리로 하여금 문맥-자유 언어를 능가하는 것을 찾아보게 하고 이 예들을 포함하는 새로운 언어군을 어떻게 정의할 수 있을지를 살펴보게 한다. 그렇게 하기 위하여, 우리는 오토마타의 일반적인 그림을 다시 보기로 하자. 유한 오토마타를 푸시다운 오토마타와 비교해 보면, 임시 저장장소의 특성이 둘 사이의 차이를 만들어 냄을 보았다. 만약 저장장소가 없다면 우리는 유한 오토마타를 갖게 되고, 만약 저장장소가 스택이면 우리는 더 강력한 푸시다운 오토마타를 갖게 된다. 이러한 관찰들을 합쳐서, 만약 오토마타에 좀더 유연한 저장장소를 부여한다면, 우리는 더욱 강력한 언어군을 발견하는 것을 기대할 수 있을 것이다. 예를 들어, 그림 1의 일반적인 구조에서, 만약 우리가 두 개의 스택, 세 개의 스택, 큐, 또는 다른 저장장치를 사용한다면 어떻게 될까? 각각의 저장장치는 새로운 종류의 오토마타를 정의하고 그것을 통하여 새로운 언어군을 정의할 것인가? 이러한 접근들은 많은 질문들을 제기하지만, 그들 대부분은 흥미가 없는 것으로 판명되었다. 오토마타의 개념이 어디까지 확대될 수 있을까 하는 더 야심찬 질문과 생각을 하는 것이 더 교육적이다. 우리는 가장 강력한 오토마타와 계산의 한계에 대하여 어떻게 말할 수 있을까? 이 질문은 튜링 기계 (Turing machine) 의 기초적인 개념을 이끌어 냈고, 이어서, 기계적인 또는 알고리즘적인 계산의 개념의 정확한 정의를 이끌어 냈다.

우리는 우리의 공부를 튜링 기계의 공식적인 정의로부터 시작하여, 몇몇 간단한 프로그램을 함으로써 무엇이 연관되어 있는가에 대한 느낌을 발전시켜 본다. 그 다음으로, 튜링 기계가 아주 원시적인데 반하여, 그 개념이 아주 복잡한 절차까지도 망라할 수 있을 정도로 충분히 광범위하다는 것을 논한다. 그 논의는, 현재의 컴퓨터로 처리될 수 있는 것들과 같은 모든 계산 절차는 튜링 기계에서 실행될 수 있다고 주장하는, 튜링 명제(Turing thesis)로 절정에 이른다.

1. 표준 튜링 기계

우리는 복잡하고 정교한 저장장소를 갖는 다양한 오토마타를 상상할 수 있지만, 튜링 기계의 저장장소는 실제로 아주 간단하다. 그 저장장소는 셀(cell)들의 1차원 배열로 구체화할 수 있다. 각 셀은 하나의 심볼을 저장할 수 있다. 이 배열은 양쪽으로 무한히 확장되고 따라서 무한한 양의 정보를 저장할 수 있다. 그 정보는 아무 순서로 읽혀질 수 있고 바뀔 수 있다. 우리는 그런 저장장소를, 실제 컴퓨터에서 사용되는 자성 테이프와 유사하기 때문에, 테이프 (tape) 라 한다.

(1) 튜링 기계의 정의

튜링 기계는 임시 저장장소가 테이프인 오토마타이다. 이 테이프는 셀들로 나뉘어 있고, 각 셀은 한 개의 심볼을 저장할 수 있다. 이 테이프와 관련해서 읽기-쓰기 헤드 (read-write head) 가 있다. 이 읽기-쓰기 헤드는 테이프에서 왼쪽 또는 오른쪽으로 움직일 수 있고 각 이동마다 하나의 심볼을 읽고 쓸 수 있다. 계산 이론 개요의 일반적인 구조로부터 약간 벗어나기 위하여, 튜링 기계로 사용하는 오토마타는 입력 파일이나 특별한 출력장치를 갖지 않을 것이다. 필요한 입력과 출력은 테이프에서 이루어질 것이다. 우리는 나중에 세가지 기초개념에 있는 이러한 일반적인 모델에 대한 수정이 별로 중요하지 않다는 것을 살펴볼 것이다. 우리는 우리가 내리려는 결론에 아무 영향을 주지 않고서 입력 파일이나 특별한 출력 장치를 유지할 수 있다.

튜링 기계의 직관적인 가시화를 제공하는 도표가 그림 1 에 주어져 있다. 정의 1 은 그 개념을 분명하게 한다.

그림 1

튜링 기계의 정의에서, Σ ⊆ Γ - {□} 임을 가정한다. 즉, 입력 알파벳은 공백 심볼을 포함하지 않는 테이프 알파벳의 부분집합이다. 앞으로 곧 명백해질 이유 때문에 공백 심볼들은 입력에서 제외한다. 전이 함수는 다음과 같이 정의된다.

일반적으로, δ 는 Q × Γ 에 대한 부분 함수 (partial function) 이다. 이에 대한 해석은 튜링 기계가 작동하는 원칙을 제시한다. δ 의 인수들은 제어 유닛의 현재 상태와 현재 읽혀지는 테이프 심볼이다. 그 결과는 제어 유닛의 새로운 상태, 전에 있던 심볼을 교체하는 새로운 테이프 심볼과 이동 심볼 (move symbol) L 또는 R 이다. 이동 심볼은 테이프에 새로운 심볼이 쓰여진 후 읽기-쓰기 헤드가 왼쪽 또는 오른쪽으로 이동하는지를 나타낸다.

그림 2 (a) 이동 전과 (b) 이동 후의 상황.

그림 3 일련의 이동들

튜링 기계에 대한 여러 다른 정의들을 만들 수 있기 때문에, 우리가 표준 튜링 기계 (standard Turing machine) 라고 부르는 모델의 주된 특징을 요약할 필요가 있다.

원래 이들 관례들은 계속되는 논의의 편의를 위하여 선택되었다. 튜링 기계의 다른 버전들을 살펴보고 우리의 표준 모델과의 관계를 논의할 것이다.

튜링 기계의 형상들을 표시하기 위하여, 순간적 묘사의 개념을 사용한다. 모든 형상은 제어 유닛의 현재 상태, 테이프의 내용과 읽기-쓰기 헤드의 위치로 완전히 결정된다. 우리는 다음과 같은 표기를 사용할 것이다.

또는

그림 4

이 표기는 그림 4에 나타나 있는 테이프를 가지고 상태 q 에 있는 기계의 순간적 묘사이다. 심볼들 a1, ..., an 은 테이프의 내용을 나타내고, 반면에 q 는 제어 유닛의 상태를 정의한다. 이 관례는 읽기-쓰기 헤드의 위치가 q 바로 뒤에 있는 심볼을 포함하고 있는 셀이 되도록 선택되었다.
순간적인 묘사는 단지 읽기-쓰기 헤드의 오른쪽과 왼쪽에 있는 유한한 양의 정보만을 보여주고 있다. 테이프의 특별히 표기하지 않은 부분은 모두 공백 심볼들을 포함하고 있다고 가정한다. 통상적으로 그러한 공백 심볼들은 아무 관계가 없고 순간적 묘사에는 명확하게 보여지지 않는다. 만약 공백 심볼의 위치가 논의에 관계가 있다면, 공백 심볼이 순간적 묘사에 나타날 수 있다. 예를 들면, 순간적 묘사 q □ w 는 읽기-쓰기 헤드가 w 의 첫 심볼 바로 왼쪽 셀에 있고 이 셀은 공백 심볼을 포함하고 있음을 나타낸다.

앞으로의 논의를 위하여, 방금 만들어진 다양한 관찰을 공식적인 방식으로 요약하는 것이 편리하다.

예제 3 은 빠져나올 수 없는 끝이 없는 루프에 진입하면서 튜링 기계가 전혀 정지하지 않을 가능성을 보여준다. 이 상황은 튜링 기계를 논의하는 데 있어서 기본적인 역할을 한다. 따라서 이에 대해 특별한 표기를 사용한다. 우리는 그 상황을 다음과 같이 표현한다.

이는 기계가 초기 형상 에서부터 시작하여 전혀 정지하지 않음을 가리킨다.

(2) 언어 승인기로서의 튜링 기계

튜링 기계는 다음의 의미로서 승인기로 볼 수 있다. 한 문자열 w 가 테이프에 적혀 있다. 사용되지 않은 부분은 공백 심볼들로 채워져 있다. 기계는 읽기-쓰기 헤드가 w 의 가장 왼쪽 심볼에 위치하여 있고 초기 상태 에서 시작된다. 일련의 이동 후에, 만약 튜링 기계가 종료 상태에 놓이고 정지하면, w 가 승인된 것으로 간주된다.

이 정의는 시작에 입력 w 가 테이프에 적혀있고 양쪽은 공백 심볼로 채워져 있음을 가리킨다. 공백 심볼을 입력에서 제외시키는 이유가 이제는 명백해진다. 이는 모든 입력은 오른쪽 왼쪽이 공백 심볼들로 채워져 있는 테이프의 잘 정의된 영역으로 제한되어 있음을 확실하게 한다. 이러한 관례가 없이는, 기계는 입력을 찾아보아야 하는 영역을 한정할 수가 없다. 얼마나 많은 공백 심볼들을 보든지 간에, 테이프의 다른 곳에 공백 심볼이 아닌 입력이 있다는 것을 확신할 수가 없다.

정의 3 은 w ∈ L(M) 일 경우 무슨 일이 일어나야 하는지를 말하고 있다. 이는 다른 입력에 대한 결과에 대해서는 아무 것도 말하지 않고 있다. w 가 L(M) 에 속하지 않을 경우, 두 가지 가운데 하나가 일어난다. 기계가 종료 상태가 아닌 상태에서 정지하거나 또는 무한 루프에 들어가서 전혀 정지하지 않을 수 있다. M 이 정지하지 않는 모든 문자열은 정의에 의하여 L(M) 에 속하지 않는다.

더 복잡한 언어의 인식은 더욱 어렵다. 튜링 기계는 원시적인 명령들을 가지고 있으므로, 우리가 고급 언어를 가지고 쉽게 프로그램할 수 있는 계산들은 튜링 기계에서는 자주 번거로워진다. 그래도 다음의 예제들에서 보여지듯이, 프로그램은 여전히 가능하고, 그 개념은 이해하기 쉽다.

이 예제로부터 우리가 내릴 수 있는 결론은 튜링 기계는 문맥-자유 언어가 아닌 언어를 인식할 수 있다는 것이다. 이것이 튜링 기게가 푸시다운 오토마타보다 더 강력하다는 첫 증거이다.

(3) 변환기로서의 튜링 기계

우리는 지금까지 변환기 (transducer) 를 공부할 이유가 거의 없었다. 언어 이론에서, 승인기가 사실상 적절하다. 그러나 우리가 곧 보게 될 것과 같이, 튜링 기계는 언어 승인기로서 흥미있을 뿐만 아니라 일반적인 디지털 컴퓨터에 대한 간단한 추상적 모델을 우리에게 제시한다. 컴퓨터의 주요한 목적이 입력을 출력으로 변환시키는 것이기 때문에, 컴퓨터는 변환기로서 작동한다. 만약 튜링 기계를 사용하여 컴퓨터의 모델을 만들기를 원한다면, 우리는 이 해석을 더 엄밀히 살펴보아야만 한다.

계산에 대한 입력은 초기에 테이프에 있는 공백 심볼이 아닌 모든 심볼들이다. 계산의 종결에서, 출력은 그때 테이프에 있는 모든 것이다. 따라서, 우리는 튜링 기계 변환기 M 을 아래와 같이 정의된 함수 f 의 구현으로 간주할 수 있다.

이 경우, M 은 어떤 종료 상태 에 대하여, 아래와 같은 계산을 수행할 수 있어야 한다.

우리가 곧 주장하려는 것처럼, 모든 일반적인 수학적인 함수들은, 얼마나 복잡하든 간에, 튜링-계산가능하다. 우선, 덧셈과 산술 비교와 같은, 몇몇 간단한 연산들을 살펴보자.

수를 더하는 것은 모든 컴퓨터의 기본적인 연산 가운데 하나이다. 기본적인 연산들은 더 복잡한 연산들을 합성하는 데 일부분으로 역할을 한다. 다른 기초 연산들은 문자열 복사와 단순 비교들이다. 이들 역시 튜링 기계에서 쉽게 수행될 수 있다.

연습문제

1. 고급 프로그래밍 언어로 튜링 기계 시뮬레이터 (simulator) 를 작성하라. 작성한 시뮬레이터는 튜링 기계의 묘사를, 초기 형상과 함께, 입력으로 받고, 계산의 결과를 출력으로 생성하여야 한다.

2. 많아야 세 개의 상태들을 가지고 언어 L(a(a + b)*) 을 승인하는 튜링 기계를 설계하라. Σ = {a, b} 임을 가정ㅎ나다. 같은 언어를 승인하는 두 개 상태를 가지는 튜링 기계가 존재하는가?

3. 예제 7 의 튜링 기계가 입력 aba 와 aaabbbb 가 주어질 경우 무엇을 하는지를 결정하라.

4. 예제 7 의 튜링 기계가 무한 루프에 들어가게 되는 입력이 있는가?

5. 어떤 언어가 아래와 같이 정의된 튜링 기계 M = ({q0, q1, q2, q3}, {a, b}, {a, b, ㅁ}, δ, q0, ㅁ, {q3}) 에 의하여 승인되는가?

6. 만약 문자열 w 가 1 이 아닌 심볼을 포함할 경우 예제 10 에서 어떤 일이 일어날 것인가?

7. 알파벳 {a, b} 에 대한 다음 언어들을 승인하는 튜링 기계를 구성하라.

        (a) L = L(aba*b)

        (b) L = {w : |w| 는 짝수이다}

        (c) L = {w : |w| 는 3 의 배수이다}

        (d) L = {anbm : n ≥ 1, n ≠ m}

        (e) L = {w : na(w) = nb(w)}

        (f) L = {anbman+m : n ≥ 0, m ≥ 1}

        (g) L = {anbnanbn : n ≥ 0}

        (h) L = {anb2n : n ≥ 1}

    각 문제에 대하여, δ 를 자세히 완전하게 작성하고 여러 예들을 추적하여 제시된 답을 확인하라.

8. 다음의 언어를 승인하는 튜링 기계를 설계하라.

        L = {ww : w ∈ {a, b}+}

9. 다음의 함수를 계산하는 튜링 기계를 구성하라.

        f(w) = wR

    여기서 w ∈ {0, 1}+ 이다.

10. 길이가 짝수인 문자열의 중간을 찾아내는 튜링 기계를 설계하라. 명확하게, 만일 입력 문자열이 이면 (여기서 이다), 튜링 기계는 문자열 을 출력하여야 한다, 여기서 c ∈ Γ - Σ 이다.

11. 일진법으로 주어진 양의 정수들 x 와 y 에 대한 다음의 함수를 계산하는 튜링 기계를 설계하라.

        (a) f(x) = 3x

        (b) f(x, y) = x - y        x > y
                 = 0             x ≤ y

        (c) f(x, y) = 2x + 3y

        (d) f(x) = ,               만일 x 가 짝수이면

                   = ,           만일 x 가 홀수이면

        (e) f(x) = x mod 5

        (f) f(x) = , 여기서 는 보다 작거나 같은 가장 큰 정수를 나타낸다.

12. 공백 심볼이나 1 을 포함하고 있는 임의의 셀에서 시작할 경우, 테이프가 어느 곳에든지 0 을 가지고 오직 그럴 때에만 정지하는 Γ = {0, 1, ㅁ} 인 튜링 기게를 설계하라.

13. 예제 8 에 대한 완전한 해를 작성하라.

14. 예제 10 의 튜링 기계가 입력 111 이 주어졌을 경우 거쳐가야 할 일련의 순간적 묘사들을 제시하라. 만약 이 기계가 테이프에 110 을 가지고 시작할 경우 어떻게 될 것인가?

15. 예제 10 의 튜링 기계가 실제로 지적한 계산을 수행한다는 납득될 수 있는 논증을 제시하라.

16. 예제 11 의 모든 세부사항들을 완성하라.

17. 예제 9 에서 우리는 x 와 y 를 이진법으로 표현하기로 결정하였다고 하자. 지시된 계산을 이진법 표현에서 하는 튜링 기계 프로그램을 작성하라.

18. 만약 x 와 y 가 십진법으로 표현되었다면 예제 9 가 어떻게 해결되는지를 개략적으로 설명하라.

19. 이 절의 모든 예제들의 튜링 기계들이 오직 하나의 종료 상태만을 가지는 것을 알아차릴 수 있을 것이다. 일반적으로 모든 튜링 기계에 대하여 같은 언어를 승인하는 종료 상태를 오직 하나만 가지는 또 다른 튜링 기계가 존재하는 것이 사실인가?

20. 정의 2 는 튜링 기계에 의하여 승인되는 언어에서 빈 문자열을 제외시켰다. λ 를 포함하는 언어가 승인될 수 있도록 정의를 수정하라.

2. 복잡한 태스크를 위한 튜링 기계 결합

우리는 모든 컴퓨터에서 찾아질 수 있는 몇몇 중요한 연산들이 튜링 기계에서 어떻게 수행될 수 있는지를 분명하게 보였다. 디지털 컴퓨터에서, 그러한 기초적인 연산들이 더욱 복잡한 명령어들을 구성하는 요소가 되기 때문에, 어떻게 이들 기초 연산들이 튜링 기계에서 짜맞추어질 수 있는지 살펴보기로 하자. 튜링 기계들이 어떻게 결합될 수 있는지를 보이기 위하여, 우리는 프로그래밍에서의 보편적인 관습을 따른다. 우리는 고급 묘사로부터 시작하여, 우리는 프로그램이 우리가 작업하는 실제 언어로 작성될 때까지 계속해서 다듬어 간다. 튜링 기계는 고급 수준에서 작업하는 실제 언어로 작성될 때까지 계속해서 다듬어 간다. 튜링 기계는 고급 수준에서 여러 가지 방법으로 기술될 수 있다. 블록 도표 (block diagram) 와 의사코드 (pseudocode) 는 앞으로의 논의에서 가장 자주 사용하게 될 두 가지 방법이다. 블록 도표에서, 계산들은 상자 (box) 안에 놓인다. 상자 안에 그 계산의 기능이 설명된다. 그러나 내부적인 세부사항들은 보여지지 않는다. 그러한 상자들을 사용하여, 그 계산들이 실제로 구성될 수 있다는 것을 암시적으로 주장한다. 첫 번째 예로서, 예제 9 와 11 의 기계들을 결합해 본다.

그림 5

튜링 기계를 고급 수준으로 보이는 또 다른 유용한 방법은 의사코드 (pseudocode) 와 연관된 것이다. 컴퓨터 프로그래밍에서, 의사코드는 우리가 이해할 필요가 있는 의미를 표현하는 서술적인 문구를 사용하여 계산의 윤곽을 나타내는 방법이다. 이 서술은 컴퓨터에서는 사용될 수 없지만, 우리는 이 서술이 필요할 때 적절한 언어로 번역될 수 있다고 가정한다. 의사코드의 간단한 한 종류는, 예로서, 매크로명령어의 개념을 들 수 있다. 매크로명령어는 일련의 저급 문장들 (lower level statements) 에 대한 단일-문장 약어 (single-statement shorthand) 이다. 우선 매크로명령어를 저급 언어를 사용하여 정의한다. 우리는 매크로명령어가 있는 곳마다 연관된 저급 코드가 대체된다는 가정하에 프로그램에서 매크로명령어를 사용한다. 이 개념은 튜링 기계 프로그램에서 아주 유용하다.

한 걸음 더 나아가서, 우리는 매크로명령어를 부프로그램으로 교체할 수 있다. 일반적으로, 매크로명령어는 매번 나타날 때마다 실제 코드로 교체된다, 반면에 부프로그램은 필요할 때마다 반복적으로 호출되는 하나의 코드이다. 이를 그럴 듯하게 만들기 위하여, 튜링 기계가 어떻게 다른 튜링 기계에 의하여 반복적으로 호출될 수 있는 부프로그램처럼 사용될 수 있는지를 대략적으로 설명해 보자. 이는 새로운 기능이 필요하다. 부프로그램으로부터 귀환시 호출한 프로그램의 형상을 재생성할 수 있도록 그 형상에 대한 정보를 저장하는 능력, 예를 들어, 상태 에 있는 기계 A 가 기계 B 를 호출한다고 하자. B 가 끝났을 때, 우리는 상태 에서 프로그램 A 를, 읽기-쓰기 헤드는 원래의 위치에서 (헤드는 B 의 작업중에 움직였을 것이다), 다시 시작하고자 한다. 다른 경우에는, A 가 상태 에서 B 를 호출할 수도 있을 것이다. 그 경우에는 제어는 로 돌아와야 할 것이다. 제어 이동 문제를 해결하기 위하여, 우리는 A 로부터 B 로 그리고 또 역으로 정보를 전달할 수 있어야 하고, 제어가 B 로부터 돌아왔을 때 A 의 형상을 재생성할 수 있고 임시로 보류된 A 의 계산이 B 의 실행으로 영향을 받지 않는다는 것을 보장할 수 있어야 한다. 이를 해결하기 위하여, 그림 6 에서 보여진 것과 같이 테이프를 여러 영역으로 나눌 수 있다.

그림 6

A 가 B 를 호출하기 전에, A 는 B 가 필요한 정보를 (예를 들면, A 의 현재 상태, B 에 대한 인수들) 테이프의 한 영역 T 에 적는다. A 는 상태를 B 의 시작 상태로 옮김으로써 제어를 B 로 전달한다. 옮긴 후에, B 는 입력을 찾기 위하여 T 를 사용한다. B 의 작업공간은 T 와 A 의 작업 공간과는 분리되어 있다. 따라서 어떤 방해도 발생할 수 없다. B 가 작업을 마쳤을 때, B 는 관련된 결과를, A 가 결과를 찾기를 기대하는, T 로 돌려줄 것이다. 이는 진짜 컴퓨터에서 프로그램이 호출될 때 실제로 일어나는 것과 아주 유사하다는 것을 유의하라.

이들 의사코드를 어떻게 실제의 튜링 기계 프로그램으로 번역하는지를 (적어도 이론적으로라도) 알고 있다면, 튜링 기계를 의사코드로 프로그램할 수 있다.

그림 7

이 예제들의 서술적인 성질에도 불구하고, 튜링 기계가, 원칙적으로 다소 원시적이지만, 아주 강력하게 만들기 위하여 여려 가지 방법으로 결합될 수 있다는 것을 추측 (conjecture) 하게 하기 위하여 너무 억지를 부린 것은 아니다. 제시된 예들이 모든 것을 증명하였다고 주장할 만큼 일반적이고 자세하지는 않지만, 튜링 기계가 어떤 아주 복잡한 일들을 할 수 있다는 것이 이 시점에서는 그럴 듯하여야 할 것이다.

연습문제

1. 예제 14 에 대한 완전한 해를 작성하라.

2. 양의 정수와 음의 정수를 표현하는 관례를 성립하라. 제시한 관례를 사용하여, x - y 를 계산하기 위한 감산기 (subtracter) 의 구성을 개략적으로 보여라.

3. 가산기, 감산기, 복사기, 또는 승산기 (multiplier) 들을 이용하여, 모든 양의 정수 n 에 대한 아래의 함수들을 계산하는 튜링 기계들에 대한 블록 도표를 그려라.

        (a) f(n) = n(n + 1)

        (b) f(n) =

        (c) f(n) =

        (d) f(n) = n!

        (e) f(n) =

4. 모든 에 대하여 다음과 같이 정의된 함수 f 의 구현을 개략적으로 보여주기 위하여 블록 도표를 사용하라.

        

    여기서, 만약 어떤 두 w 도 길이가 같지 않다면, i 는 을 만족하고, 그 외의 경우, i = 0 이다.

5. {a, b} 에 대한 다음의 언어들을 승인하는 튜링 기계들에 대한 "고급-수준 (high-level)" 으로 설명하라. 각 문제에 대하여, 구현하기에 합리적으로 쉽다고 생각되는 적절한 매크로명령어들의 집합을 정의하여 답을 사용하라.

        (a)

        (b)

        (c) (a) 에서의 언어의 여집합

        (d)

        (e) L = {an : n 은 소수이다}

6. 튜링 기계에서 유리수를 표현하는 방법을 제안하고, 유리수들을 더하고 빼는 방법들을 개략적으로 설명하라.

7. 보통의 십진법으로 주어진 양의 정수들 x 와 y 의 덧셈과 곱셈을 수행할 수 있는 튜링 기계의 구성을 개략적으로 설명하라.

8. 아래의 매크로명령어를 구현하라.

        

    이 매크로명령어는 기계가 현 위치의 오른쪽으로 첫 번째로 나타나는 심볼 a 를 찾는 것을 나타낸다. 만약 공백 심볼 이전에 a 를 만난다면, 기계는 상태 에 놓이고, 그렇지 않으면, 기계는 상태 에 놓인다.

10. 연습문제 8 의 매크로명령어 searchright 를 사용하여 가장 왼쪽에 있는 a 의 바로 왼쪽에 있는 심볼을 공백 심볼로 교체하는 튜링 기계 프로그램을 작성하라. 만약 입력이 a 를 포함하고 있지 않다면, 가장 오른쪽의 공백이 아닌 심볼을 b 로 교체한다.

3. 튜링 명제

앞서의 논의는 튜링 기계가 어떻게 간단한 부분들로부터 구성될 수 있는가를 보여주었을 뿐 아니라, 저급-수준 오토마타를 가지고 작업하는 것에 대한 부정적인 견해를 보여주었다. 블록 도표나 의사코드를 대응되는 튜링 기계로 번역하는 것이 아주 작은 상상력 또는 영리함을 요하는 것에 반하여, 실제로 그렇게 하는 것은 많은 시간이 걸리고, 실수하기 쉽고 우리의 이해에 큰 도움이 되지 않는다. 튜링 기계의 명령어들의 집합은 아주 제약적이어서 평범하지 않은 문제들에 대한 논의, 해법, 또는 증명이 아주 지루하다.

우리는 지금 난관에 놓여 있다. 우리는 튜링 기계가 명확한 프로그램들이 마련된 간단한 연산들뿐 아니라, 블록 도표나 의사코드로 설명될 수 있는 더욱 복잡한 절차들도 수행할 수 있다고 주장하고 싶다. 반대 의사에 대하여 이 주장을 지키기 위하여, 관련된 프로그램을 명확하게 보여야 한다. 그러나 그러는 것은 유쾌하지 않고 정신을 산만하게 한다. 따라서 가능하면 피해야 한다. 어떻게 해서든지, 우리는 저급-수준의 긴 코드를 작성하지 않고서 튜링 기계에 대한 상당히 엄밀한 논의를 할 수 있는 방법을 찾으려 한다. 불행하게도 이 궁지에서 빠져 나올 완전하게 만족할 방법은 없다. 우리가 할 수 있는 최선의 방법은 적당한 타협에 도달하는 것이다. 우리가 어떻게 그러한 타협을 이룰 수 있는지를 알아보기 위하여, 우리는 다소 철학적인 토의를 해보자.

우리는 앞절의 예제로부터 약간 간단한 결론들을 내릴 수 있다. 첫째는 튜링 기계가 푸시다운 오토마타보다는 강력하다 (이 언급에 대해서는, 이 절 끝에 있는 연습문제 2 를 보아라). 예제 8 에서, 문맥-자유가 아닌 언어 (결론적으로, 그 언어에 대한 어떤 푸시다운 오토마타도 존재하지 않는) 에 대한 튜링 기계의 구성을 개략적으로 설명하였다. 예제 9, 10 과 11 은 튜링 기계들이 몇몇 산술 연산들을 계산하고, 문자열 조작을 수행하고 그리고 몇몇 간단한 비교들을 할 수 있음을 보였다. 또한 어떻게 원시적인 연산들이 더 복잡한 문제들을 해결하기 위하여 결합될 수 있고, 어떻게 여러 튜링 기계들이 조립될 수 있고, 어떻게 한 프로그램이 또 다른 프로그램의 부프로그램으로 작동할 수 있는지를 논의하였다. 아주 복잡한 연산들이 이런 식으로 만들어질 수 있기 때문에, 우리는 튜링 기계가 능력면에서 전형적인 컴퓨터에 접근하기 시작하는 것이 아닌가 생각할 수 있다.

튜링 기계가, 어떤 의미로, 능력면에서 전형적인 디지털 컴퓨터와 같을 것이라는 추측을 한다고 하자. 어떻게 우리는 그러한 가설을 정당화할 수 있을까? 그것을 정당화하기 위하여, 우리는 일련의 점점 더 어려운 문제들을 택하고 그 문제들이 어떤 튜링 기계에 의하여 어떻게 해결되는지를 보일 수 있을 것이다. 또한 우리는 특정 컴퓨터의 기계 언어 명령어 집합을 택하고 그 집합에 속한 모든 명령어들을 수행할 수 있는 튜링 기계를 설계할 수도 있을 것이다. 이것은 의심할 여지도 없이 참을성을 요구하나, 만약 우리의 가설이 옳다면, 원칙적으로 반드시 가능할 것이다. 이 방향으로의 모든 성공은 가설이 참이라는 것에 대한 신념을 강하게 하지만, 여전히 증명에 이르지는 못한다. 그 어려움은 우리가 전형적인 디지털 컴퓨터가 정확히 무엇을 의미하는지를 모르고 또한 자세한 정의를 내릴 방법을 가지고 있지 않다는 사실에 있다.

또한 그 문제를 다른 면에서부터 접근할 수 있다. 우리가 컴퓨터 프로그램으로 작성할 수 있지만 어떤 튜링 기계로도 프로그램할 수 없는 어떤 프로시저를 찾으려고 시도할 수 있을 것이다. 만약 이것이 가능하다면, 이 가설을 부정할 수 있는 근거를 갖게 될 것이다. 그러나 이제까지 어느 누구도 반례를 만들어 낼 수가 없었다. 모든 그러한 시도가 실패하였다는 사실은 그런 시도가 이루어질 수 없다는 정황적인 증거로 간주될 수 있을 것이다. 모든 징후는 튜링 기계가 원칙적으로 모든 컴퓨터만큼 강력하다는 것이다.

이런 타입의 논의는 1930 년대 중반의 A. M. Turing 과 다른 사람들로 하여금 튜링 명제 (Turing thesis) 라 불리는 유명한 추측 (conjecture) 을 만들어 내게 하였다. 이 가설은 기계적인 방법으로 수행될 수 있는 모든 계산은 어떤 튜링 기계에 의하여 실행될 수 있다는 것을 말한다.

이는 개략적인 진술이다. 따라서 튜링 명제가 무엇인지를 계속해서 마음에 간직하는 것이 중요하다. 이것은 증명될 수 있는 어떤 것은 아니다. 그렇게 하기 위해서는, 우리는 "기계적인 방법" 이라는 말을 정확하게 정의해야만 한다. 이는 어떤 다른 추상적인 모델을 필요로 할 것이고 우리에게 전보다 더 이상의 진전을 주지 않는다. 튜링 명제는 무엇이 기계적인 계산을 구성하는가의 정의로서 더 적절하게 보여진다. 계산이 어떤 튜링 기계에 의하여 수행될 수 있고 오직 그럴 때에만 기계적이라 한다.

우리가 이런 자세를 택하여 튜링 명제를 단순히 정의로 간주한다면, 우리는 이 정의가 충분하게 광범위한가와 같은 질문을 제기한다. 이것이 우리가 현재 컴퓨터로 하고 있는 (그리고 아마도 미래에 할 수 있을) 것을 망라할 수 있을 정도로 충분히 광범위한가? 확실한 "yes" 는 가능하지 않지만, 긍정적인 증거는 매우 강하다. 튜링 기계를 기계적인 계산에 대한 정의로 받아들이는 몇몇 논거들은 다음과 같다.

이러한 논거들은 정황적이며, 그리고 튜링 명제는 그런 논거들로 증명될 수 없다. 그런 그럴싸함에도 불구하고, 튜링 명제는 여전히 가정이다. 그러나 튜링 명제를 단순하게 임의의 정의로 보는 것은 중요한 점을 잃게 된다. 어떤 의미에서, 튜링 명제는 물리학과 화학의 기본 원칙들이 하는 것처럼 컴퓨터 과학에서 같은 역할을 한다. 예를 들어, 고전적인 물리학은 주로 Newton의 운동 법칙들에 근거를 두고 있다. 우리가 비록 그것들을 법칙이라 부르고 있으나, 그들이 논리적인 필연성을 가지고 있는 것은 아니다. 차라리, 그들은 물리적인 세계의 많은 것을 설명하는 그럴듯한 모델들이다. 그 법칙으로부터 우리가 내린 결론들이 우리의 경험과 관찰과 일치하기 때문에 우리는 그 법칙들을 인정하는 것이다. 그러한 법칙들은, 비록 무용지물이 될 수는 있지만, 참이라고 증명될 수 없다. 만약 실험적인 결과가 법칙들에 근거한 결론과 상반된다면, 우리는 그 법칙들의 정당성에 대하여 의심하기 시작할 것이다. 반면에, 어떤 법칙을 무력화하는 것에 대한 반복된 실패는 그 법칙에 대한 우리의 확신을 강하게 한다. 이것이 튜링 명제에 대한 입장이다. 따라서 우리가 이 명제를 컴퓨터 과학의 기본 법칙으로 생각하는 이유가 된다. 이로부터 내린 우리의 결론은 우리가 실제의 컴퓨터에 대하여 알고 있는 것과 일치하고, 지금까지, 이 결론을 무용지물로 만들려고 하는 모든 시도들이 실패했다. 그러나 어느 누군가가 튜링 기계에 의하여 망라되지 않지만 여전히 기계적인 계산의 직관적인 개념에는 포함되는 어떤 포착하기 어려운 상황을 설명하는 또 다른 정의를 제안할 가능성은 항상 존재한다. 그러한 일이 일어나면, 그 결과로 일어나는 우리의 논의 가운데 일부는 심각하게 수정되어야 할 것이다. 그러나 그렇게 될 가능성은 매우 작아 보인다.

튜링 명제를 받아들임으로써, 우리는 알고리즘의 정확한 정의를 제시할 시점에 있다.

알고리즘을 튜링 기계 프로그램과 동일시함으로써, 우리는 "...알고리즘이 존재한다" 혹은 "...알고리즘이 존재하지 않는다" 와 같은 주장들을 엄밀하게 증명할 수 있게 된다. 그러나, 상대적으로 간단한 문제들일지라도 그에 대한 알고리즘을 명확하게 구성하는 것은 아주 긴 작업이다. 그러한 유쾌하지 않은 예상을 피하기 위하여, 튜링 명제에 호소하여 모든 컴퓨터에서 할 수 있는 모든 일은 또한 튜링 기계에서 할 수 있다는 것을 주장한다. 결론적으로, 정의 1 에서 "튜링 기계" 를 "Pascal 프로그램" 으로 대체할 수 있다. 이렇게 하면 알고리즘을 표시하는 데에 대한 부담을 상당히 줄여줄 것이다. 실제로, 우리가 이미 하였던 것과 같이, 우리는 한 단계 더 나아가서, 말로 된 설명 또는 블록 도표들을, 만약 우리가 감히 하려 한다면 튜링 기계 프로그램으로 작성할 수 있다는 가정하에, 알고리즘으로 인정할 것이다. 이는 논의를 굉장히 간단하게 하나, 당연히 우리에게 비판의 여지를 남긴다. "Pascal 프로그램" 은 확실하게 정의되어 있으나, 명확한 말로된 설명은 그렇지 않다. 그리고 존재하지 않는 알고리즘을 존재한다고 주장하는 위험이 있다. 그러나 이런 위험은 우리가 논의를 간단하고 직관적으로 명확하게 유지할 수 있고, 다소 복잡한 절차들에 대해서 간명한 설명을 제시할 수 있다는 사실로 그 이상으로 상쇄된다. 이러한 주장들의 정당성에 대하여 의구심을 가지는 독자들은 적당한 프로그램을 어떤 프로그래밍 언어로 작성함으로써 그런 의구심들을 쫓아버릴 수 있을 것이다.

연습문제

1. 선택한 컴퓨터에 대한 기게 언어 명령어들의 집합을 고려하자. 이 집합에 속한 여러 명령어들이 어떻게 튜링 기계에 의하여 수행될 수 있는지를 개략적으로 설명하라.

2. 위의 논의에서, 우리는 튜링 기계가 푸시다운 오토마타보다 강력한 것처럼 생각된다고 말하였다. 튜링 기게의 테이프를 스택처럼 작동할 수 있게 만들 수 있기 때문에, 실제로 튜링 기계가 더 강력하다고 주장할 수 있다고 보여진다. 이 논의에서 어떤 중요한 요소가 고려되지 않았는가?

3. 널리 알려진 문헌에 튜링 기계에 대한 여러 재미있는 논문들이 있다. 그 중 우수한 것은 Scientific American, May 1984 에 게재된, 제목이 "Turing Machines" 인, J. E. Hopcroft 의 논문이다. 이 논문은 우리가 여기서 소개한 개념들에 대하여 이야기하였고 또 Turing 과 다른 사람들의 작업들이 행해진 역사적인 정황을 제시하였다. 이 논문을 찾아 읽고, 그에 대한 비평을 써보아라.