어떠한 인간도 열거가능한 무한 집합의 모든 원소들을 (그 이름들을 어떤 표기법으로 하나하나 써냄으로써) 열거할 수 있을 만큼 원소들의 이름들을 빨리 또는 오랫동안 또는 작게 (주석 : 세상에는 종이가 유한한 양만큼만 있다. 그러므로 당신이 무한한 수의 기호들을 종이에 쓰려면 한정없이 점점 더 작게 써야만 한다. 결국 당신은 분자 크기로, 원자 크기로, 전자 크기로, ... 써야 한다는 말이다.) 쓸 수 없다. 그러나 인간들은 어떤 열거가능한 무한 집합들의 경우에는 원소들을 하나하나 쓰는 것과 동등하게 유용한 무엇인가를 할 수 있다. 즉 인간들은 임의의 유한 수 n 에 대해 그 집합의 n 번째 원소가 무엇인지를 결정할 수 있는 명확한 계산 방법을 제시할 수 있다. 그러한 방법은 계산 기계나 또는 매우 기초적인 기호들만을 다룰 수 있는 인간도 그 방법에 따라 계산을 수행할 수 있을 정도로 매우 명백한 형식으로 제시될 수 있다. 물론 계산에 사용될 수 있는 시간의 한계, 계산의 각 과정이 수행되는 속도의 한계, 기호로서 사용될 수 있는 우주에 존재하는 물질적 재료의 양의 한계 등으로 인해, n 의 유한한 수의 투입값들을 제외한 많은 투입값들에 대해서는 어떠한 인간이나 어떠한 기계도 실제적으로 계산을 수행해 내는 것은 물리적으로 불가능하다는 문제는 남아 있다. 그러나 만약 우리가 이러한 한계들을 무시하고 실제 인간들이나 기계들이 현실적으로 확실히 계산할 수 있는 범위를 넘어서는 영역까지도 포용하는 계산가능성 (Computability) 의 개념을 받아들인다면 이것은 명료성과 단순성에 도움이 될 것이다. 이 때 필수적인 요건은 우리의 계산가능성 개념이 너무 좁지 않아야 한다는 것이다. 왜냐하면 우리는 곧, 비록 시간, 속도, 재료의 양에 대한 물리적 한계가 어떤 방식으로 극복될 수 있다 할지라도, 어떤 함수들은 계산가능하지 않으며, 어떤 집합들은 열거가능하더라도 효율적으로 (기계적으로) 열거가능하지는 않다는 것을 증명하기 위해 이 개념을 이용할 것이기 때문이다.

계산의 개념은 아래와 같은 질문들에 대해 어떤 방식으로 대답을 하느냐에 따라 서로 다른 많은 방식으로 명료화할 수 있다. '계산이 직선 테이프 위에서 또는 직사각형 격자 위에서 또는 무엇 위에서 수행되는가? 만약 직선 테이프가 사용된다면, 이 테이프는 시작은 있으나 끝은 없는가 아니면 양쪽으로 모두 끝이 없는가? 테이프가 칸으로 구획 지어져 생긴 사각형들은 (길거리에 있는 집들의 번지수와 같은) 번지수를 가지고 있는가 아니면 (나무들에 표지를 함으로써 등산로를 표시하듯이) 적절한 사각형들에 특별한 기호들을 씀으로써 우리가 어디에 있는지를 추적하여야 하는가?' 등등. 그러한 질문들에 어떤 대답들이 주어지느냐에 따라, 계산에 대한 정의들은 상세하게 될 때 서로 다른 모습을 띨 것이다. 그러나 우리의 목적은 계산의 개별적 과정들을 충실히 묘사하는 것이 아니다. 실제로, 이러한 질문들이 어떻게 대답되든 간에, 동일한 함수들의 집합이 계산가능한 것으로 판명되었다. 우리는 이제 계산가능한 함수들의 집합에 대한 한 가지 규정을 얻기 위해, 위의 질문들과 다른 질문들에 어떤 한 방식으로 대답을 할 것이다. 이런 계산가능성 개념에 대해 적절한 양의 경험을 쌓으면 그 질문들이 어떠한 적절한 방식으로 대답되든 그 실질적 결과는 같다는 것을 알게 될 것이다. 실제로 이미 주어진 계산가능성에 대한 규정 이외에 또 다른 어떠한 합당하고 정확한 규정이 주어진다고 해도, 우리는 조심스럽고 고된 추론을 통해, 이미 주어진 규정에 의거해 계산가능한 함수는 새로운 규정에 의거해서도 역시 계산가능하다고 하는 의미에서 우리의 계산가능성의 개념이 새로이 달리 규정된 계산가능성의 개념과 동치라는 것을 증명할 수 있다. 그러나 계산가능성과 효율성 (effectiveness) 개념들에 대한 상세한 규정들의 가능성은 무한히 많기 때문에, 우리는 종국적으로 (수학적 증명을 허용하지 않는) 다음과 같은 입론을 받아들이든가 거부하여야 한다 : 우리가 의미하는 계산가능한 함수들의 집합은 만약 시간, 속도, 재료에 대한 제한들이 극복된다면, 인간과 기계가 효율적인 방법으로 (그 효율적인 방법이 무엇이든) 계산할 수 있는 함수들의 집합과 동일하다. 비록 이 입론 ('처치 (Church) 의 입론') 은 증명 가능하지는 않지만, 만약 틀리다면 반증가능하다. 왜냐하면 만약 틀리다면, 직관적인 의미에서 계산가능하나 우리의 의미에서 계산가능하지 않은 어떤 함수가 있을 것이기 때문이다. 그러한 함수가 직관적인 의미에서 계산가능하다는 것을 보이기 위해서는 모든 (임의의) 투입값들에 대해 그것의 산출값을 계산할 수 있게 해 주는 계산 방법을 제시하고 진정으로 이 계산 방법이 효율적이라는 것을 보여주기만 하면 충분하다. (아마도 우리는 구체적 경우들에서 여러 방법들이 효율적이라는 것을 볼 수 있을 것이다.) 그러한 함수가 우리의 의미에서 계산가능하지 않다는 것을 보이기 위해서는, 모든 가능한 튜링 기계 (Turing Machine) 들을 조사하고, (적절한 증명을 함으로써) 그 기계 중 어느 것도 그 함수를 계산하지 못한다는 것을 입증하여야 한다. (당신은 곧 4 장과 5 장에서 그러한 증명들의 예들을 볼 것이다. 그러나 거기에서 튜링 계산가능하지 않다고 입증된 함수들은 효율적으로 계산가능하다는 것의 직관적인 의미가 무엇이든 간에 그런 의미에서 효율적으로 계산가능하다고 입증되지 않고 있다. 따라서 그것들은 처치의 입론에 대한 반대 사례들이 되지 않는다.) 따라서 처치의 입론이 거짓이면, 반대 사례를 찾아냄으로써 반증될 수 있다. 그리고 어떠한 반대 사례도 찾지 못한 채 계산에 대한 경험이 더 많이 쌓이면 쌓일수록, 그 입론은 그만큼 더 확실시되는 것이다.

이제 우리의 의미에서의 계산가능성인 튜링 계산가능성을 상세하게 살펴보자. 우리는 사각형들의 연속으로 된 테이프 위에서 계산이 이루어진다고 상상한다. 그리고 이 테이프는 양쪽으로 끝이 없다. 왜냐하면 테이프가 실제로 무한하거나, 또는 테이프 양쪽 끝에 필요할 때마다 여분의 빈 사각형들을 덧붙이는 사람이 있기 때문이다. 많아야 유한 수들의 사각형들을 제외하고는 계산의 첫 단계와 그것에 잇따른 각 단계에서 모든 사각형들은 비어 있다. 만약 사각형이 비어 있지 않으면, 그 사각형 속에는 유한 수의 기호들 S₁, ..., S_n 중 꼭 하나만이 씌어 있다. 빈 사각형들은 어떤 기호, 곧 빈 칸을 표시하는 기호가 씌어진 것으로 간주하면 간편하다. 빈 칸을 표시하는 기호로 'S₀' 을 사용하자.

계산의 각 단계에서, 인간이나 기계적 계산기 (Computer) 는 테이프의 어떤 한 사각형을 읽는다. 계산기는 읽은 사각형 속에 어떤 기호가 씌어져 있는지를 식별할 수 있다. 계산기는 읽은 사각형 속에 씌어 있는 기호를 지우고 거기에 새로운 기호를 써넣을 수 있다. 또 계산기는 한 사각형 오른쪽으로 또는 한 사각형 왼쪽으로 움직일 수 있다. 만약 당신이 원한다면, 그 기계를 계산의 단계마다 테이프의 어떤 사각형 위에 놓여 있는 바퀴 달린 상자라고 아주 소박하게 생각할 수 있다. 테이프는 기차의 철로와 같이 생각할 수 있다. 철로의 받침목들은 사각형들의 경계를 표시한다. 기계는 그림 1 과 같이 철로를 따라 양쪽으로 움직일 수 있는 매우 짧은 차와 같이 생각할 수 있다. 이 차의 밑바닥에는 받침목들 사이에 무엇이 씌어 있는지를 읽을 수 있고, 씌어 있는 것을 지울 수 있고, 거기에 기호들을 써넣을 수 있는 장치가 있다.

이 기계는 계산의 각 단계마다 유한한 내적 상태들 q₁, ..., q_m 중의 한 상태 속에 있도록 고안되어 있다. 이 기계가 어떤 특정한 한 상태 속에 있다는 것은 m 개의 톱니들을 가진 어떤 톱니바퀴의 특정한 톱니가 가장 위로 올라와 있거나 또는 기계 속에 있는 어떤 단자에 m 개의 서로 다른 수준의 전압들 중에 어떤 특정한 전압이 걸려 있거나 하는 일로 표시될 수 있다. 그러나 우리는 이런 종류의 기계 공학이나 전자 공학에는 관심이 없다. 아마도 위에서 설명한 것을 쉽게 이해하는 가장 간편한 길은 다음과 같이 매우 소박하게 생각하는 것일 것이다. 곧 상자 안에 읽고, 쓰고, 지우고, 움직이는 모든 일을 하는 사람이 있다고 말이다. (이 상자는 밑바닥이 없다. 이 불쌍한 얼간이는 그 상자를 스스로 밀면서 철로를 따라 받침목들 사이를 걷는다.) 이 사람은 종이 위에 씌어진 m 개의 지시 사항들의 목록을 가지고 있다. 그가 m 개의 것들 중에서 지시 사항 i 를 실행할 때 그는 q_i 의 상태 속에 있다.

각 지시 사항들은 조건문의 형태를 띠고 있다. 즉 지시 사항들은 그 사람이 읽을 사각형 안에 씌어진 기호가 무엇이냐에 따라, 즉 S₀ 또는 S₁ 또는 ... S_n 이냐에 따라 무엇을 할 것인지를 말해 주고 있다. 그가 할 수 있는 일은 아래와 같이 n + 4 가지가 있다.

         (1) 계산을 멈추어라.
         (2) 오른쪽으로 사각형 하나만큼 움직여라.
         (3) 왼쪽으로 사각형 하나만큼 움직여라.
         (4) 읽은 사각형 안에 씌어진 것 대신에 S₀ 을 써라.
         (5) 읽은 사각형 안에 씌어진 것 대신에 S₁ 을 써라.
         .
           .
           .
         (n + 4) 읽은 사각형 안에 씌어진 것 대신에 S_n 을 써라.

따라서 그가 무슨 지시 사항을 실행하고 있느냐 (= 그가 무슨 상태에 있느냐) 와 그가 무슨 기호를 읽고 있느냐에 따라 그는 n + 4 가지의 외적 행위들 중 한 가지를 수행할 것이다. 또한 만약 그가 계산을 멈추지 (외적 행위 1 번을 하지) 않았다면, 그는 그의 상자 속에서 다음 지시 사항 (다음 상태) 이 무엇인지를 결정하는 내적 행위를 수행할 것이다. 따라서 현재 상태와 현재 읽고 있는 기호가 무슨 외적 행위가 수행될 것인지 그리고 다음 상태가 무엇이 되는지를 결정한다.

이 사람이 따라야 할 지시 사항들의 전반적인 프로그램은 기계 도표 (machine table) 또는 흐름 도식 (flow graph) 또는 사중체들의 집합 (set of quadruples) 과 같은 여러 방식들에 의해 명시될 수 있다. 빈 테이프 위에 기호 S₁ 을 세 번 쓰고, 이 세 S₁ 중 맨 왼쪽에 있는 S₁ 을 읽으면서 그 위에서 멈추는 기계의 경우에 대한 세 종류의 기술들이 그림 2 속에 나타나 있다.

보기 1. S₁S₁S₁ 을 써라

기계는 처음에 읽고 있는 사각형에 S₁ 을 쓰고, 왼쪽으로 사각형 하나만큼 움직여서 거기에 S₁ 을 쓰고, 왼쪽으로 사각형 하나만큼 더 가서 거기에 세번째 S₁ 을 쓰고 멈춘다. (기계는 더 이상의 지시가 없을 때 멈춘다.) 씌어질 기호인 S₁ 각각에 대해 한 상태씩 모두 세 상태가 있을 것이다. 그림 2 에서 기계 도표의 (수평선 아래의) 맨 위 행에 있는 항목들은 상태 q₁ 에 있을 때 따라야 할 지시 사항의 내용을 알려 주고 있다. (1) 만약 읽은 기호가 S₀ 이면 S₁ 을 쓰고 지시 사항 q₁ 을 반복하고, (2) 만약 읽은 기호가 S₁ 이면 왼쪽으로 움직여서 다음 지시 사항 q₂ 를 수행하라. 흐름 도식에서도 ' q₁' 이라고 씌어진 마디에서 빠져 나온 두 개의 화살표가 똑 같은 정보를 말해 주고 있다. 또 처음 두 개의 사중체들도 똑 같은 정보를 말해 주고 있다. 도표의 항목과, 흐름 도식의 화살표와, 사중체가 뜻하는 바는 그림 3 이 보여 주고 있다.

특별히 명시되어 있지 않으면 기계는 번호가 가장 낮은 상태에서 출발한다고 이해한다. 우리가 고려하고 있는 기계는 S₁ 을 읽으면서 상태 q₃에서 멈춘다. 도표의 항목이나 화살표나 사중체나 모두 그 경우에 무엇을 해야 할지 전혀 말해 주지 않기 때문이다.

흐름 도식이 기계 프로그램을 표시하는 방법으로서 갖는 장점 가운데 한 가지는 출발 상태만 어떤 방식으로든 알려진다면 (이를테면 다른 지적이 없는 한, 가장 왼쪽에 있는 마디가 출발 상태라고 이해된다면) 그 상태들의 이름들이 없어도 괜찮다는 것이다. 그 상태들을 뭐라고 불러도 상관없다. 그러면 흐름 도식은 그림 4 와 같이 그릴 수 있다.

우리는 그런 기계가 어떻게 작동하는지를 그 기계가 진행 과정에서 띠게 될 일련의 형태들을 기술함으로써 보여줄 수 있다. 각 형태는 계산의 어떤 단계에서 테이프 위에 무엇이 씌어 있는지를 보여주고, 기계가 그 단계에서 어떤 상태에 있는지를 보여주고, 어느 사각형을 읽고 있는지를 보여준다. 우리는 테이프 위에 무엇이 씌어 있는지 그 내용을 적고, 아울러 읽고 있는 사각형에 씌어 있는 기호 아래에다가 현재 상태의 이름을 적음으로써 그렇게 할 것이다.

우리는 여기서 공연히 번거롭게 하지 않기 위해 기호 S₀ 과 S₁ 대신에 0 과 1 을 썼고, 마찬가지로 상태 q₁, q₂, q₃ 대신에 1, 2, 3 을 쓴 것이다. 따라서 마지막 형태는

을 줄여 쓴 것이다. 물론 테이프 처음과 끝에 있는 일련의 S₀ 들을 마음대로 줄이거나 늘여도 내용상 아무런 의미 변화가 없다. 테이프는 양 끝에 빈 칸을 당신이 원하는 만큼 많이 가지고 있다고 이해할 수 있기 때문이다. 이제 좀더 복잡한 보기를 살펴보자.

이 기계는 연속된 일련의 1 들을 제외하고는 모두 빈 칸인 테이프의 맨 왼쪽 1 을 읽으면서 출발해서, 두 배가 된 일련의 1 들을 제외하고는 모두 빈 칸인 테이프의 맨 왼쪽 1 을 읽으면서 멈출 것이다. 흐름 도식은 다음과 같다.

이 기계는 어떻게 이 일을 수행하는가? 개괄적으로 말하자면, 왼쪽에다가 1 을 두 개 쓰고, 그 다음에 맨 오른쪽에 있는 1 을 하나씩 지워 나가는 작업을 반복한다. 구체적으로, 출발할 때의 최초 형태가 이라고 가정하여 보자. 그러면 우리는 이제 연속된 세 개의 1 들을 제외하고는 모두 빈 칸인 테이프의 맨 왼쪽 1 을 읽으면서 상태 1 에서 출발한다. 그 다음 단계의 형태들을 몇 개 그려보면,

와 같다. 이렇게 해서 우리는 본디 형태인 111 로부터 0 에 의해 분리된 첫 두 개의 1 들을 왼쪽에다가 쓴 셈이다. 그 다음에 우리는 오른쪽으로 향해서 0 을 지나 애초의 형태의 오른쪽 끝으로 가서 가장 오른쪽에 있는 1 을 지운다. 이상을 두 단계로 나누어서 보자. 단계 1 :

이제 우리는 애초의 일련의 1 들 중 마지막 1 을 그냥 지나쳤다는 것을 알게 되고, 그래서 (단계 2) 다시 돌아와 그 1 을 지운다.

이제 우리는 우리가 맨 처음에 있던 위치로 돌아와서 애초의 일련의 1 들에서 남아 있는 1 들 중 가장 왼쪽에 있는 것을 읽는다. 우리가 반복 고리를 한 번 더 돌고 나면, 즉 위의 과정을 한 번 더 반복하고 나면, 다음과 같은 형태에 있게 될 것이다 : 우리는 그 다음에 다음과 같은 과정을 밟는다.

이제 테이프에는 여섯 개의 1 들이 있게 된다. 그런데 우리는 애초의 세 개의 1 들 중 맨 마지막 것을 지우고, 우리가 썼던 여섯 개의 1 들 중 맨 왼쪽 것을 읽으면서 멈추고 싶다. 그 과정은 다음과 같다.

이제 우리는 1 을 읽으면서 상태 12 에 있게 되었다. 그 마디에는 그 경우에 우리가 무엇을 해야 하는지를 말해 주는 화살표가 하나도 없으므로 우리는 멈춘다. 기계는 예고된 바의 일을 수행한 것이다. (주의 : 기계가 애초의 1 의 개수가 3 일 때 그 개수를 두 배로 한다는 사실은 기계가 예고된 바의 일을 수행한다는 것에 대한 증명은 되지 못한다. 그러나 애초에 세 개의 1 이 있는 특별한 경우를 잘 들여다보면 애초의 1 의 개수가 세 개라는 사실이 증명상 본질적이지 않음을 알 수 있을 것이다. 이 특별한 경우의 증명은 애초에 일련의 1 들의 개수가 몇 개이든지 상관없이 항상 그 1 들의 개수를 두 배로 함을 보여주는 증명으로 바꿀 수 있다.)

보기 3. 비어 있는 테이프에 2n 개의 1 들을 쓰고 맨 왼쪽의 1 을 읽으면서 멈추어라

2n 개의 상태들을 이용하는 직접적인 방식이 있다. 우리는 보기 1 의 방식을 이용할 수 있다. 일반적으로 흐름 도식은

과 같은 모양의 것을 2n 개만큼 연결하고 마지막 화살표를 잘라 냄으로써 얻을 수 있다. 그러나 n + 11 개의 상태들을 이용하는 다른 방법도 있다. 즉 테이프에 직접적인 방식으로 n 개의 1 들을 쓰고, 그 다음에 그 1 들을 두 배로 하기 위해 보기 2 의 방식을 이용하는 것이다. 개요를 말하면, 빈 칸에 n 개의 1 들을 쓰는 기계의 흐름 도식의 마디 n 과 보기 2 의 흐름 도식의 마디 1 을 하나로 중첩시킴으로써 두 개의 도식을 붙일 수 있다. 만약 n 이 크다면 2n 개의 1 들을 쓰는 직접적인 방식은 우리가 방금 기술한 간접적인 방식보다 훨씬 더 많은 상태들을 필요로 할 것이다. (만약 n 이 11 보다 크다면 2n 은 n + 11 보다 크다.) 우리는 물론 두 배로 하는 기법을 반복함으로써 상태들을 더 줄일 수도 있다. 예를 들어, 100 개의 1 들을 쓰기 위해서 우선 25 개를 쓰는 데 25 상태들을 이용하고, 그것을 두 배로 하는 데 11 상태들을 이용하고, 다시 그것을 두 배로 하는 데 다른 11 상태들을 이용할 수 있다. 이렇게 하면, 직접적인 방식에서는 100 개의 상태들이 필요했고, 두 배로 하는 기법을 오직 한 번만 이용할 경우에는 61 개의 상태들이 필요했음에 비해, 47 개의 상태들만이 필요하게 된다.

1. 연속된 일련의 1 들을 제외하고는 모두 빈 칸인 테이프의 맨 왼쪽 1 을 읽으면서 출발해서, 종국적으로 애초에 1 들이 짝수 개만큼 있었느냐 아니면 홀 수 개만큼 있었느냐에 따라 각각 빈 칸 또는 1 을 읽으면서 멈추는 기계를 설계하라. 단, 멈출 때 테이프는 읽고 있는 사각형을 제외하고는 모두 빈 칸이다.

2. 연속된 일련의 1 들과 2 들을 제외하고는 모두 빈 칸인 테이프 (1 들과 2 들은 어떤 순서여도 상관이 없고 모두 다 1 들이거나 2 들이어도 괜찮다) 에서 맨 왼쪽의 것을 읽으면서 출발해서 결국은 다음 사항을 알려주면서 멈추는 기계를 설계하라. 그 기계가 멈추는 시점의 테이프의 내용은 애초의 배열에서 1 들과 2 들 중 정확히 어느 것이 더 많은가를 (당신이 정한 어떤 규정에 따라) 말해 주어야 한다.

3. 십진법 표기로 1 을 더하라. 기계는 처음에 일련의 십진법 숫자들을 제외하고는 모두 빈 칸인 테이프에서 맨 오른쪽의 숫자를 읽고 있다. 그 기계가 멈출 때 테이프는 '1 + 애초의 수' 를 십진법으로 표시하고 있다. 이것을 수행하는 간단한 기계를 설계하라. (기계 도표로 나타내라 - 흐름 도식으로 나타내면 복잡할 것이다.)

4. 일진법 표기로 곱셈을 하라. 테이프는 처음에 한 개의 빈 칸으로 분리된 두 개의 1 들의 일련체들만을 제외하고는 모두 빈 칸이다. 첫 번째 일련체에는 p 개의 1 들이 있고 두 번째 일련체에는 q 개의 1 들이 있다고 하자. 테이프에서 가장 왼쪽에 있는 1 을 읽으면서 출발해서 결국은 pq 개의 연속된 1 들을 제외하고는 모두 빈칸인 테이프에서 가장 왼쪽에 있는 1 을 읽으면서 멈추는 기계를 설계하라.

5. 일진법 표기로 덧셈을 하라. ('pq' 대신에 'p + q' 라는 것만 빼고는 연습문제 4 와 똑같다.)

6. 양의 정수에서 양의 정수로 가는 모든 함수들이 튜링 계산가능한 것은 아니다. 당신은 2 장의 연습문제를 통해 그런 함수들이 튜링 기계의 개수보다 더 많이 있어서, 튜링 기계가 계산할 수 없는 함수들이 있다는 것을 알았을 것이다. 그것을 좀더 자세히 설명하라.

7. 생산성 (productivity). 빈 칸 외에 1 만을 기호로 사용하는 튜링 기계를 생각해 보아라. 테이프는 처음에 완전히 비어 있다. 만약 기계가 연속된 일련의 1 들을 제외하고는 모두 빈 칸인 테이프에서 가장 왼쪽에 있는 1 을 읽으면서 결국 멈추게 되면 그 때의 1 들의 길이를 그 튜링 기계의 생산성이라고 한다. 그러나 기계가 결코 멈추지 않거나 어떤 다른 형태로 멈춘다면, 그 생산성은 0 이다. 이제 p(n) = '가장 생산적인 n - 상태 튜링 기계의 생산성' 이라고 정의하자. 다음을 증명하라 :

8. 바쁜 해리의 문제 (the busy beaver problem) (Tibor Rado, Bell System Technical Journal, 1962 년, 5 월). 연습문제 6 에 따르면 계산가능하지 않은 함수들이 존재한다. 그러나 그런 함수는 어떻게 생겼는가? 당신은 방금 그런 함수와 실제로 마주쳤었다. 연습문제 7 에서 정의한 함수 p 가 그것이다. 그것이 계산불가능하다는 증명은 '바쁜 해리의 문제' 가 해결불가능하다는 사실에 달려 있다. 그 문제는 빈 칸 외에 1 만을 기호로 사용하고, 연속된 일련의 n 개의 1 들을 제외하고는 모두 빈 칸인 테이프에서 가장 왼쪽에 있는 1 을 읽으면서 출발해서, 결국에는 연속된 일련의 p(n) 개의 1 들을 제외하고는 모두 빈 칸인 테이프의 맨 왼쪽 1 을 읽으면서 멈추는 튜링 기계를 설계하는 문제이다. 실제로 그런 기계는 존재하지 않는다. 그것을 증명하기 위해서 (이를테면 k 개의 상태를 갖는) 그런 기계가 있다고 가정하여, 모순을 이끌어 내자. 그러기 위해서는 다소 기발한 아이디어가 필요하다. 힌트 : 만약 그런 기계가 있다면, 그것을 두 개 만들어 빈 칸에 n 개의 1 들을 쓰는 n - 상태 기계에 (아래 그림과 같이) 연결함으로써 p(p(n)) 의 생산성을 갖는 n + 2k 상태의 기계를 얻을 수 있다. 이것과 연습문제 7 에서 증명한 마지막 사실과 함께 모순을 이끌어 낼 수 있다.

9. 대각화를 통한 계산불가능성 빈 칸 외에 1 만을 기호로 사용하는 모든 튜링기계들은 다음과 같은 규약에 따라 양의 정수에서 양의 정수로 가는 어떤 함수를 계산한다. 투입값 n 에 함수가 부여하는 산출값을 계산하기 위해서, 기계는 연속된 일련의 n 개의 1 들을 제외하고는 모두 빈 칸인 테이프에서 가장 왼쪽에 있는 1 을 읽으면서 가장 낮은 번호의 상태에서 출발한다. 함수가 투입값 n 에 대해서 정의될 경우 그리고 오직 그 경우에만 기계는 결국에 연속된 일련의 1 들을 제외하고는 모두 빈 칸인 테이프에서 가장 왼쪽에 있는 1 을 읽으면서 멈춘다. 멈출 경우에 함수의 산출값은 1 들의 (일련체의) 길이이다. 튜링 기계들은 열거가능하기 때문에 (연습문제 6 참조), 튜링 기계들이 계산하는 함수들도 열거가능하다. '반대각' 함수를 정의하고, 어떠한 튜링 기계도 그 함수를 계산할 수 없음을 증명하라. (풀이는 5 장을 보라.)

10. 멈춤 문제 (halting problem). 를 빈 칸 외에 1 만을 기호로 쓰는 모든 튜링 기계들을 열거한 것이라고 하자. 자기 멈춤 문제란, 이 연속된 일련의 n 개의 1 들을 제외하고 모두 빈 칸인 테이프에서 가장 왼쪽에 있는 1 을 읽으면서 최초의 상태에서 출발한 다음에 결코 멈추지 않을 경우 그리고 오직 그 경우에만 s(n) = 1 인 전체 또는 부분함수 s 를 계산하는 일정한 효율적인 절차를 규정하는 문제이다. 완전한 멈춤 문제란, 이 연속된 일련의 n 개의 1 들을 제외하고 모두 빈 칸인 테이프에서 가장 왼쪽에 있는 1 을 읽으면서 최초의 상태에서 출발한 다음에 결코 멈추지 않을 경우 그리고 오직 그 경우에만 h(m, n) = 1 인 그러한 전체 또는 부분함수 s 를 계산하는 일정한 효율적인 절차를 규정하는 문제이다.

(a) 자기 멈춤 문제는 해결불가능함을 증명하라.
(b) 다음의 따름정리를 증명하라. 멈춤 문제는 해결불가능하다.

힌트 : 어느 시점에서든 처치의 입론을 이용해야 한다. 연습문제 6 에서 어떠한 튜링 기계에 의해서도 계산가능하지 않다고 보여준 함수들 중 하나가 만약 자기 멈춤 문제가 해결가능하다면 일상적이지 않은 형태로 (두 대의 튜링 기계를 동시에 이용해서) 계산가능함을 증명하라.

1. 처음에 1 들이 0 개 또는 2 개 또는 4 개 ... 있으면 이 기계는 빈 테이프에서 빈칸을 읽으면서 상태 1 에서 멈춘다. 또 처음에 1 들이 1 개 또는 3 개 또는 5 개 ... 있으면 이 기계는 한 사각형에만 1 이 씌어 있고 모두 빈 칸인 테이프에서 그 1 을 읽으면서 상태 5 에서 멈춘다.

2. 기계가 멈출 때, 테이프가 빈 것일 경우 그리고 오직 그 경우에만 애초의 배열에는 1 들과 2 들이 똑같은 개수만큼 이었다.

이것을 할 수 있는 다른 방식들이 있다. 가령 기계가 1 과 2 이외의 기호들은 쓰지 않는 방식 말이다. 그렇게 하는 가장 간단한 방식 - 이 방식은 문제에서 제시된 표현에 들어맞긴 하지만 그 정신을 반영하지는 못한다 - 은 다음과 같은 규정을 채택해서 기계가 멈출 때의 테이프의 내용을 통해 애초에 있었던 1 들과 2 들의 개수가 같은가 같지 않은가를 말해 주는 것이다. 그 규정은 애초에 있었던 1 들과 2 들이 같은 개수만큼 있을 경우 그리고 오직 그 경우에만 그 기계가 멈출 때 테이프에는 1 들과 2 들이 같은 개수만큼 있다는 내용이다. 그럴 경우, 테이프의 마지막 내용은 애초에 있던 내용과 똑같으면 되는데, 그러기 위해서는 기계가 곧바로 멈추면 된다. 그런 기계의 도식은 다음과 같다 : ①

3. 기계가 읽을 수 있는 기호들은 모두 11 개가 있을 수 있는데 그 기호들 중 B 는 빈 칸이고 0 은 빈 칸이 아니라 십진법 숫자들 중 하나다. 1, ..., 9 는 일상적인 십진법 숫자들이다. 아래 도표에서 순서쌍은 각각 순서대로, 수행해야 할 동작과 다음 상태를 표시한다. 두 번째 열에 있는 많은 빈 칸들은 기계가 따라야 할 지시사항이 없고 따라서 멈추라는 상황을 표시한다.

4. 일진법으로 곱셈을 하는 비슷하게 효율적인 방법들은 많다. 그 방법들 중 많은 방법들이 테이프에 처음과 마지막에 나타나는 B 와 1 말고도 다른 기호들을 쓰는데, 그것은 아무래도 괜찮다. 그런 기호들은 기계가 진행 과정 중 어디에 있는지를 알기 위해서 사용되고 멈추기 전에 모두 지워진다. 그러나 지금 보여줄 방식은 진행 과정 중에도 B 와 1 만을 사용한다. 우리가 그렇게 한 까닭은 다음과 같은 점을 드러내기 위해서였다. 양의 정수에서 양의 정수로 가는 임의의 계산가능한 함수는 B 와 1 만을 기호로 사용하는 기계에 의해서 일진법으로 계산가능하다.

이제 이 기계가 어떻게 곱셉을 수행하는지를 보자. 첫 번째 일련체인 p 개의 1 들은 기계가 오른쪽에 있는 그룹에 q 개의 1 들을 몇 회나 더했는지를 알려주는 셈표지 (counter) 로 쓰인다. 기계는 p 개의 1 들 중 가장 왼쪽에 있는 1 을 지우고, 셈표지 그룹에 1 들이 아직 남아 있는지를 살펴보면서 시작한다. 만약 남아 있지 않으면 pq = q 이고 기계가 할 일이라고는 테이프의 가장 왼쪽으로 옮겨가서 멈추는 것뿐이다. 그러나 셈표지 그룹에 1 이 아직 남아 있다면 기계는 등짚고 넘기 과정 (leapfrog routine) 으로 들어간다. 실제로 기계는 q 개의 1 들의 일련체 ('등짚고 넘기 그룹') 를 테이프의 오른쪽으로 q 자리만큼 옮겨간다. 보기를 들어보면, p = 2 이고 q = 3 일 때 테이프는 처음에

처럼 된다. 그러면 기계는 셈표지 그룹에 1 이 하나만 남았다는 것을 알아차리고 그 1 을 지우고 오른쪽으로 사각형 두 개만큼 가서 1 을 만날 때까지 B 를 모두 1 로 바꾼 후 가장 왼쪽에 있는 1 로 가서 멈춘다. 다음이 등짚고 넘기 과정이 진행되는 방식이다.

일반적으로 등짚고 넘기 그룹은 0 개 또는 1 개 또는 ... 또는 q 개의 1 들과, 그 다음에 한 개의 빈 칸, 그리고 그 다음에 q 개의 1 들 중의 나머지로 이루어져 있다. 거기에 있는 빈 칸은 기계에게 등짚고 넘기 게임이 언제 끝나는지를 말해 준다. 그것을 말해 주지 않으면 q 개의 1 들의 그룹은 테이프 오른쪽으로 끝없이 움직임을 계속할 것이다. (등짚고 넘기를 할 때 등짚고 넘기 그룹에서 빈 칸 왼쪽에 있는 q 개의 1 들 부분은 셈표지로 기능을 한다. 그것은 빈 칸 오른쪽에 있는 등짚고 넘기 그룹 부분에 1 들을 더하는 과정을 통제한다. 그렇기 때문에 흐름 도식에 큰 고리가 두 개가 있는 것이다. 그 고리들은 각각 셈표지에 의해 통제되는 하위 과정들에 해당한다.)

5. 목표는 가장 왼쪽에 있는 1 을 지우고, 1 들의 두 일련체들 사이에 있는 틈을 메우고, 테이프에 남아 있는 연속된 일련의 1 들 중 가장 왼쪽에 있는 1 을 읽으면서 멈추는 것이다. 그것을 하는 한 가지 방식은 사중체 표기로 다음과 같다 :

6. 연습문제 2.3 에 따르면 양의 정수에서 양의 정수로 가는 모든 함수들의 집합은 열거가능하지 않다. 반면에 모든 튜링 기계들의 집합은 열거가능한데, 왜냐하면 어떠한 튜링 기계도

과 같은 무한한 알파벳의 유한한 나열로써 기술할 수 있고, 연습문제 2.4(d) 에 따르면 ( 라고 할 때) 그런 모든 나열들의 집합은 열거가능하기 때문이다. (우리는 출발 상태를 정할 규약이 필요하다. 이를 테면 출발 상태에는 가장 낮은 q-번호를 부여한다는 식으로 말이다.) 그러면 우리의 목록에서 각 튜링 기계가 계산하는 함수가 (만약 있다면) 무엇인지를 결정하기 위해 우리가 어떠한 규약을 채택하더라도, 우리의 튜링 기계 목록은 우리 규약에 따라 튜링 기계가 계산하는 양의 정수에서 양의 정수로 가는 모든 함수들의 (아마도 빈 틈이 있는) 목록이 될 것이다. 한 가지 가능한 규약은 연습문제 4 에서 규정한 것인데, 우리는 거기서 기호들 S₂, S₃, ... 중 어느 하나라도 사중체 속에 포함하는 튜링 기계는 양의 정수에서 양의 정수로 가는 어떠한 함수도 계산할 수 없다고 했다. 만약 f₁, f₂, f₃, ... 을 우리의 규약에 따라 튜링 기계가 계산하는 모든 함수들의 빈틈이 없는 목록이라고 한다면, 연습문제 2.3 의 반대각 함수 u 가 어떠한 튜링 기계도 우리 방식대로 계산하지 못하는 양의 정수에서 양의 정수로 가는 함수의 한 보기가 된다는 것에 주목하라. 또 다른 보기는 우리가 다음과 같이 정의하는 부분함수 t 이다.

10(a). 만약 자기 멈춤 문제가 해결가능하다면, 처치 입론에 의해서 s 를 어떤 방식으로, 이를테면 연습문제 9 의 방식으로 계산하는 어떤 튜링 기계가 S 가 있을 것이다. 그러면 연습문제 6 의 함수 t 는 다음과 같은 방식으로 계산가능할 것이다. t(n) 을 결정하기 위해서 기계 S 와 을 연속된 일련의 n 개의 1 들을 제외하고는 모두 빈 칸인 테이프의 가장 왼쪽에 있는 1 을 읽으면서 최초 상태에서 출발하게 하라.

경우 1 : 이 결코 멈추지 않는다. 그러면 S 는 결국 하나의 1 을 제외하고는 모두 빈 칸인 테이프에서 그 1 을 읽으면서 멈출 것이다. 우리는 그 때 이 결코 멈추지 않으리라는 것을 알게 될 것이고, 따라서 상응하는 함수 이 투입값 n 에 대해서 정의되지 않으리라는 것을 알게 될 것인데, 그러면 t(n) = 1 이다.

경우 2 : 이 결국 멈춘다. 그럴 때 우리는 테이프를 살펴봄으로써 이 정의되었는가 안되었는가를 결정할 수 있고, 따라서 t(n) 이 정의 안 되었는지 또는 1 과 같은지를 알 수 있을 것이다. 그러면 만약 자기 멈춤 문제가 해결가능하다면, t 는 일상적이지 않은 형태로 계산가능하고, 따라서 처치 입론에 의해서 어떤 튜링 기계가 t 를 계산하는데, 이는 우리가 연습문제 6 에서 증명한 것과 모순이 된다.

10(b). 만약 멈춤 문제가 해결까능하다면, 즉 h 가 계산가능하다면, 자기 멈춤 문제는 해결가능할 것이다. 즉 모든 양의 정수 n 에 대해서 s(n) = h(n, n) 이기 때문에 s 는 계산가능할 것이다.

0000000	0000100	0000100	0001100	0001100	0011100
¹	¹	²	²	³	³

0111,	00111,	10111,	010111,	110111
²	³	³	⁴	⁴

110111,	110111,	110111,	110111,	110111,	1101110.
⁵	⁵	⁶	⁶	⁶	⁶

110111,	110110.
⁷	⁷

111101,	111101,	111101,	111101,	111101,	111101,	0111101,
⁸	⁹	¹⁰	¹⁰	¹⁰	¹⁰	¹⁰

	111101,	0111101,	1111101,	01111101,	11111101.
	²	³	³	⁴	⁴

11111101,	11111101,	...,	11111101,	11111101,	11111101,
⁵	⁵		⁵	⁵	⁶

	111111010,	11111101,	11111100,	1111110,	111111,
	⁶	⁷	⁷	⁸	¹¹