Uncomputability via diagonalization : George Boolos. Richard Jeffrey

대각화를 통한 계산불가능성

(Uncomputability via diagonalization)

계산가능성과 논리 : George S. Boolos Richard C. Jeffrey 저, 김영정.최훈.강진호 옮김, 문예출판사 (393-5681), 1996 (원서 : Computability and Logic, 3rd ed, Cambridge Univ. Press, 1989), page 54~64

이 장에서 우리는 연습문제 3.8, 3.9, 3.10 에서와 같이 다양한 계산불가능한 함수들을 보일 것이다. 이러한 함수들을 '튜링 기계들에 의해 계산불가능한' 이라고 부르는 대신 단순히 '계산불가능한' 이라고 부르는 것은 우리가 6-8 장에 걸쳐 그 증거를 제시할 처치의 입론을 참이라고 전제하고 있기 때문이다. 이 장 전체를 통해, '함수' 는 양의 정수들에서 양의 정수들로 가는 함수를 의미하고 있다.

계산불가능한 함수들의 존재는 개략적인 방식으로 쉽게 증명될 수 있다. 왜냐하면 우리는 (연습문제 2.3 을 통해) 모든 함수들의 집합은 열거불가능하나, (연습문제 2.4(d) 를 통해) (사중체들의 유한 배열들에 의해 표시된) 모든 튜링 기계들의 집합은 열거가능함을 알고 있기 때문이다. 만약 튜링 계산가능한 함수들의 집합이 모든 함수들의 집합과 동일하다면, 그 집합은 열거가능하면서 동시에 열거불가능할 것이다. 그러므로, 이 두 집합은 서로 다르다. 즉, 뒤의 집합은 앞의 집합의 진부분 집합이다.

위의 증명이 개략적이라는 것은 우리가 양의 정수들에서 양의 정수들로 가는 함수들의 튜링 계산가능성의 개념을 아직 정확히 정의하지 않았다는 점에서이다. 튜링 기계들은 수들에 대해 작동하는 것이 아니라, 기호들에 대해 작동한다. 우리는 튜링 기계들이 수로 된 함수들을 계산하는 것이라고 말할 수 있기 전에, 연습문제 3.4 와 3.5 의 곱셈 기계와 덧셈 기계에서와 같이, 수로 된 투입값들과 산출값들이 기계의 테이프 위에 표시될 수 있는 표기법을 명시하여야만 한다. 일진 표기법의 선택이 간결성에 도움이 되나, 필수적인 것은 아니다. 십진 표기법이나 여타 다른 표기법들도 역시 사용될 수 있다. 필수적인 것은 표기법과 같은 구체적인 것들이 어떠한 방식으로 명시되어야만 한다는 것이다. 우리의 구체적 명시 사항들은 다음과 같다.

(a) 함수의 투입값들은 하나의 빈 칸에 의해 분리된 1 들의 연속된 일련체들에 의해 일진 표기법으로 빈 테이프 위에 표시된다. 예를 들어 3 + 2 의 계산을 시작할 때, 테이프는 다음과 같을 것이다 : 111B11.

(b) 최초에 기계는 테이프 위에 있는 1 중에서 가장 왼쪽의 것을 읽고 있다. 만약 기계의 최초 상태가 1 이면, 3 + 2 를 계산할 때 최초의 형태는 다음과 같다 :

(c) 만약 계산가능한 함수가 테이프 위에 맨 처음 표시된 투입값들에 대해 산출값을 부여한다면, 그 기계는 궁극적으로 표준적 형태로 멈출 것이다. 즉, 연속된 일련의 1 들을 제외하고는 모두 빈 칸인 테이프의 맨 왼쪽 1 을 읽으면서 멈출 것이다. 그 연속된 1 들의 개수가 주어진 투입값들에 부여된 그 함수의 산출값이다. 따라서 연습문제 3.5 에 나온 덧셈 기계에 의해 행해진 3 + 2 계산의 최종 형태는 가 될 것이다.

(d) 다른 한편으로, 만약 함수가 주어진 투입값들에 대해 어떠한 값도 부여하지 않는다면, 그 기계는 궁극적으로 표준적 형태로 멈추지 않을 것이다. 즉, 그 기계는 영원히 작동을 계속하거나, 이나 이나 등과 같은 비표준적 형태로 멈출 것이다.

위의 (a) 와 (b) 에서 묘사된 최초의 형태를 '표준적' 최초 형태로, (c) 에서 묘사된 최종의 형태를 '표준적' 최종 형태로 부를 수 있을 것이다.

위와 같이 명시함으로써, 어떠한 튜링 기게도 투입값의 개수가 하나인 함수, 둘인 함수, 그리고 일반적으로 각 양의 정수 n 에 대해, 투입값의 개수가 n 개인 함수를 계산한다고 볼 수 있다. 가령 최초의 상태가 이고, 단일의 사중체 '' 에 의해 명시되는 기계를 고려하여 보자. 그 기계는 표준적 최초 형태로 시작하여, 테이프를 변화시키지 않은 채 곧바로 멈춘다. 만약 처음에 테이프 위에 단 하나의 1 들의 일련체만이 있었다면, 그것의 최종 형태는 표준적일 것이다. 따라서 이 기계는 하나의 투입값을 갖는 항등 함수 i 를 계산한다. 항등 함수 i 는 모든 각 양의 정수 n 에 대해 i(n) = n 이다. 결국 이 기계는 투입값을 하나 갖는 어떤 전체 함수를 계산한다. 그러나 만약 처음에 테이프 위에 둘 또는 그 이상의 1 들의 연속된 일련체들이 있다면, 그것의 최종 형태는 표준적이 아닐 것이다. 따라서 그 기계는 모든 쌍의 투입값들에 대해 정의되지 않는 투입값 순서쌍들의 극단적인 부분 함수를 계산한다. 그리고 일반적으로 함수가 n 개의 투입값들을 가질 때, 이 기계는 어떠한 n 중체의 투입값들에 대해서도 산출값을 부여하지 않는 극단적인 부분 함수를 계산한다.

다른 한편으로, 그림ㄱ 1 의 기계는 모든 n 중체의 투입값들에 대해 똑같이 산출값 1 을 부여하는 전체 함수를 계산한다. 상태 1 과 표준적 최초 형태에서 출발하여, 이 기계는 (상태 1 과 상태 2 를 왔다갔다 하면서) 1 들의 최초의 일련체를 지우고, 상태 3 으로 가서 최초의 일련체에서 오른쪽으로 두번째에 위치한 사각형을 읽는다. 만약 그 기계가 거기서 빈 칸을 보면, 그 기계는 테이프 전체를 이미 지웠다는 것을 알고 하나의 1 을 쓰고 상태 4 에서 표준적 최종 형태로 멈춘다. 그러나 만약 그 기계가 거기서 1 을 보면, 그 기계는 다시 상태 1 과 상태 2 를 왕복하면서 두번째 1 들의 일련체를 지우고, 상태 3 에서 다시금 테이프 전체가 빈 칸인가 아니면 더 지워야 할 하나 또는 그 이상의 일련체들이 남아 있는가를 묻는다.

그림 1 f(X₁, .., X_n) = 1

이 장에서 우리는 투입값을 하나 갖는 함수들만을 다룰 것이다. 우리는 튜링 기계들에 의해 계산되는 단일한 투입값의 함수들의 집합은 열거가능함에 반해, 모든 단일한 투입값의 함수들의 집합은 열거가능하지 않음을 보일 것이다. 그리고 그러한 열거의 세세한 부분에 주의를 기울임으로써, 우리는 어떠한 튜링 기계에 의해서도 계산되지 않는 단일한 투입값의 특정한 함수 t 를 정의할 것이다. 우리의 구체적인 명시 사항들에 따르면, 각 n = 1, 2, 3, ... 중에서 오로지 f(n) 이 정의된 n 에 대해서만 기계 M 이 테이프 위에 n 개의 1 들을 가지고 표준적 형태로 출발해서 궁극적으로 테이프 위에 f(n) 개의 1 들을 쓴 후 표준적 형태로 멈출 경우 그리고 오직 그 경우에만 M 은 일항 함수 f 를 계산한다. 이러한 명시 사항들에 따라 함수 f 가 어떤 기계 M 에 의해 계산될 경우 그리고 오직 그 경우에만 함수 f 는 튜링 계산가능하다고 불린다.

우리는 튜링 기계들을 열거함으로써 일항의 튜링 계산가능한 함수들을 열거한다. 이러한 목록을 만들기 위해, 우리는 자신의 첫 기호가 기계의 최초 상태인 사중체로 시작하여, 인접한 사중체들을 갈라놓는 어떠한 빈 공간도 없는 하나의 연속된 일련체로 기계의 사중체들을 씀으로써 각 기계를 명시한다. 예를 들어 최초의 상태가 인 그림 1 의 기계는 일련체에 의해 표시된다 :

분명히, 각 튜링 기계는 다음과 같이 열거가능하게 무한한 알파벳들의 어떤 유한한 일련체에 의해 위와 같은 방식으로 명시된다 :

(1)

이 알파벳들로 구성된 모든 낱말이 튜링 기계를 명시하는 것은 아니다. 다음과 같은 조건들을 만족할 경우 그리고 오직 그 경우에만 낱말은 튜링 기계를 명시한다.

(a) 낱말의 길이는 정확히 4 로 나누어져야 한다.

(b) 오로지 기호들 등만이 1, 4, 5, 8, 9, 12, ..., 4n, 4n +1, ... 의 위치에 나타난다.

(c) 오로지 기호들 등만이 2, 6, 10, ..., 4n + 2, ... 의 위치에 나타난다.

(d) 오로지 기호들 R, L, 만이 3, 7, 11, ..., 4n + 3, ... 의 위치에 나타난다.

(e) 어떠한 의 형태도 낱말 속에 한 번 이상 나타나지 않는다.

(2)

조건 (e) 는 다소 임의적이다. 조건 (e) 는 모순적인 지시 사항들을 배제하는 역할을 잘 해낸다. 그러나 동일한 사중체들의 반복을 허용하는 다음과 같은 명시 사항도 그런 역할을 잘 수행해 낼 수 있다. 그 명시 사항은, 만약 낱말 속에 의 형태가 한 번 이상 나타나면, 다음에 나오는 한 쌍의 기호들은 나타날 때마다 동일하여야만 한다는 내용이다.

이제 연습문제 2.4(d) 에 의해 우리는 열거가능하게 무한한 알파벳 (1) 에 의해 구성된 모든 낱말들의 집합이 열거가능하다는 것을 알고 있다. 더 생생하게 말하자면, 그러한 모든 낱말들의 집합을 단일한 (아마도, 빈 칸이 있는) 목록, 으로 배열하는 것이 가능하다. 만약 이 목록에서 튜링 기계들을 표시하지 못하는 낱말들을 지운다면, 우리는 각 튜링 기계들이 적어도 한 번은 이름 불려지고, 그리고 튜링 기계 이외의 어떠한 것도 이름 불려지지 않는 빈 칸이 있는 목록을 갖게 된다. 이제 (계속 생생하게 얘기하여) 모든 튜링 기계들의 빈 칸이 없는 목록 을 얻기 위해 그 빈 칸들을 제거하자. 모든 튜링 기계들이 양의 정수들에서 양의 정수들로 가는 특정한 함수 하나를 결정하므로, 각 n 에 대해 을 기계 이 계산하는 일항의 전체 또는 부분 함수라 할 때, 이 기계들의 목록은 다음과 같이 일항의 모든 튜링 계산가능한 함수의 목록을 결정한다 :

(3)

그러므로 우리가 알파벳 (1) 로 구성된 낱말들의 특정한 열거 을 명시하자마자, 우리는 일항의 튜링 계산가능한 함수들의 특정한 열거 (3) 을 명시하는 셈이 된다. w 들을 연습문제 2.4(d) 의 풀이 끝부분에서 기술한 방법으로 열거하자. 이렇게 해서 생긴 목록은 빈 틈이 있는 목록으로, 그 첫번째 항목은 , 즉 R 이다. 일반적으로, 이 목록에 있는 낱말의 위치는 그 낱말 속에 있는 R 을 12 로 L 을 122 로 을 1222 로 등등과 같이 치환함으로써 얻어진 일련체에 의해 십진법으로 주어진다. 다시 말해서, 알파벳 (1) 의 n 번째 글자는 1 다음에 n 개의 2 들을 쓴 숫자에 의해 치환된다.

w 들의 순서를 결정하면 이제 M 들의 순서를 결정하는 것은 사소한 (그러나 고된) 작업이 된다. 튜링 기계를 결정하는 (즉, (2) 의 조건들을 만족하는) w 들 중에서 첫번째 것은 '' 이다. 이것은 n = 1 222 212 221 212 222 (1 천조보다 큰 수) 인 이다. 그러면 은 그림 2 (a) 와 같은 흐름 도식을 갖는다. 어떠한 표준적 최초 형태에서도 이 기계는 1 을 읽으므로 최초의 위치에서 곧바로 멈춘다. 그러므로 은 항등 함수 i 이다. 즉 각 n 에 대해 이다. 더 나아가 는 과 동일한 함수이다. 왜냐하면 튜링 기계들을 표시하는 w 들 중에서 두번째 것은 '' 이며, 이것은 n = 12 222 122 212 212 222 인 이기 때문이다. 따라서 의 흐름 도식은 그림 2(b) 와 같이 된다. 이 기계 역시 테이프 위에 1 들의 단일한 일련체만이 있는 표준적 형태로 시작하였을 때, 표준적 최종 형태로 곧바로 멈춘다.

그림 2

우리는 이제 일항의 튜링 계산가능한 함수들을 계산하는 기계들을 열거함으로써 그 함수들을 열거하였다. 그러한 열거가 가능하다는 사실은 일항의 계산불가능한 함수들이 틀림없이 존재한다는 것을 보여준다. 실제로 그러한 열거를 하나 명시한 까닭은 아래와 같이 정의된 함수 u 와 같은 특정한 계산불가능한 함수를 제시하려고 했기 때문이다. (연습문제 2.3 과 3.6 참조.)

(4)

이제 u 는 진정으로 완벽한 일항의 전체 함수이다. 그러나 u 는 튜링 계산가능하지는 않다. 즉, u 는 도 도 도 ... 아니다. 증명. u 가 튜링 계산가능한 함수들 중의 하나라고, 예를 들어 m 번째 함수라고 하자. 그러면 각 양의 정수 n 에 대해, u(n) 과 둘 다 정의되고 그 값이 같거나, 또는 둘 다 모두 정의되지 않거나 할 것이다. 그러나 n = m 인 경우를 생각해 보자 :

(5)

그러면 이 투입값 m 에 대해 정의되었든 안 되었든 간에 모순을 유발한다. 즉, 이 정의되지 않았을 경우 (5) 는 의 산출값이 1 이라고 말해 준다. (따라서 정의되고 또한 동시에 정의되지 않았다.) 또 이 정의되었을 경우, (5) 는 이 과 같다는 것을 알려준다. (이로부터 우리는 0 = 1 을 연역해 낼 수 있다.) u 가 목록 의 어디엔가 나타난다는 가정으로부터 모순을 도출해냈으므로, 우리는 그 가정이 틀렸다고 결론내릴 수 있다. 따라서 우리는 함수 u 가 튜링 계산가능하지 않다고 결론지을 수 있다.

비록 어떠한 튜링 기계도 함수 u 를 계산하지 못하지만, 우리는 그 함수의 산출값들 중 첫 몇 개는 결정할 수 있다. 가령 는 항등 함수이므로, 이며 따라서 (4) 에 의해 u(1) = 2, u(2) = 3 임을 알 수 있다. 위와 같은 산출 값 결정 과정이나 또는 u 의 정의인 (4) 에는 어떠한 모순도 없음을 주목하라. 등식 (5) 는 모순된다. 왜냐하면 이것은 u 가 튜링 계산가능하다는, 즉 m 이 어떤 양의 정수인 기계 에 의해 계산된다는 가정을 끌어들였기 때문이다. (5) 에서 생기는 모순은 이 가정을 논박하나 정의 (4) 는 침해하지 않는다.

이제 시간만 충분히 있다면, 우리가 어떠한 양의 정수 n 에 대해서도 u(n) 을 실제로 계산할 수 있는 것처럼 보인다. 틀림없이 우리는 투입값들 1 과 2 에 대해 u 가 부여하는 산출값들을 발견하였다. 그리고 시간이 허용하는 한에서 그 다음 투입값들에 대해서도 그 산출값을 찾아내는 것은 완전히 틀에 박힌 작업임에 틀림없는 것처럼 보인다. 여기서 u 가 투입값에 부여하는 산출값을 발견하는 데 진정으로 매번 행운이나 기발한 발상을 필요로 하느냐가 정말로 문제거리이다. 그러한 행운이나 기발한 발상이 필요한 것 같지는 않다. 왜냐하면 n = 1, 2, 3, ... 인 을 결정하는 사중체들이 어떤 것인지를 발견하는 것은 기계적이기 때문이다. (이것은 기계적이지만 궁극적으로 인간으로서는 불가능하다. 왜냐하면 큰 수 n 에 대한 사소한 계산들에 소요되는 시간이 인간의 수명보다 더 길며, 인류 전체의 수명보다 더 길 수 있음이 충분히 가능하기 때문이다. 그러나 우리의 계산가능성 개념과 관련해서는 인간의 수명이 유한하다는 사실은 무시한다.) 가장 중요한 문제는 일련의 n 개의 1 들을 제외하고는 모두 빈 칸인 테이프의 맨 왼쪽 1 을 읽으면서 출발한 기계 이 일련의 1 들을 제외하고는 모두 빈 칸인 테이프의 맨 왼쪽 1 을 읽으면서 궁극적으로 멈추느냐, 멈추지 않느냐의 여부를 결정하는 일에 관한 것이다. 그 일이 완전히 틀에 박힌 작업인가? 만약 그렇다면, 함수 u 는 비록 어떠한 튜링 기계에 의해서도 계산가능하지 않지만, 결국 계산가능하다.

그러나 이 위와 같이 표준적 위치에서 궁극적으로 멈추는지의 여부를 발견하는 일이 완전히 틀에 박힌 일인가? 틀림없이 일단 최초의 형태가 명시되면 의 조작들을 따라가는 것은 완전히 틀에 박힌 일이다. 그리고 만약 이 궁극적으로 멈춘다면, 우리는 그 기계의 조작들을 따라감으로써 그 정보를 궁극적으로 얻게 될 것이다. 그러나 최초의 형태가 주어졌음에도 불구하고 만약 이 멈추지 않도록 운명지워져 있다면 어떨 것인가? 이 기계의 조작들을 따르는 틀에 박힌 과정 중에 이 기계가 결코 멈추지 않으리라는 것이 분명해질 어떤 한 시점이 있음이 틀림없는가? 간단한 경우들에서는 틀림없이 그러하다. 예를 들어 사중체 이 만약 1 을 읽으면서 출발하였다면 결코 멈추지 않는 기계를 표시함이 분명하다. 또 일련체 에 의해 기술된 기계가 결코 멈추지 않으리라는 것도 분명하다. 그러나 우리가 더 복잡한 경우들을 생각해 본다면 주어진 형태에서 출발한 특정한 기계가 궁극적으로 멈출 것인지의 여부를 발견하는 획일적이고 기계적인 절차가 있는지는 결코 분명하지 않다. 가령 연습문제 3.4 의 곱셈 기계를 고려하여 보자. 곱셈 기계는 알파벳 (1) 의 124 개의 기호들로 구성된 다양한 사중체들에 의해 묘사된다. 목록 에서 그러한 일련체를 하나 만났다고 상상해 보자. 그러한 일련체가 튜링 기계를 기술하고 있는지를 검증하는 것은 틀에 박힌 기계적 과정이다. 그리고 주석이나 등짚고 넘기 (leapfrog) 과정 및 그 밖의 과정들의 요점과 구실들에 대한 보조적 설명을 곁들이지 않고 그러한 일련체를 기반으로 3 장에서와 같은 흐름 도식을 그리는 일은 쉬운 일이다. 이러한 경우 그리고 더 복잡한 경우들에서, 일단 최초의 테이프 형태가 명시되면 기계가 표준적 최종 형태로 궁극적으로 멈추는지의 여부를 우리가 결정할 수 있게 해주는 획일적 방법이 존재하는가? 만약 존재한다면, 비록 어떠한 튜링 기계에 의해서도 계산가능하지 않지만, 함수 u 는 계산가능하다. 그러나 만약 존재하지 않는다면, u 를 튜링 방식으로는 계산불가능하나 다른 어떤 방식으로는 계산가능한 함수로 보려는 우리의 시도는 실패로 돌아가고 만다.

핵심적인 문제는 임의의 기계 사중체들 및 최초의 테이프 형태의 기술이 주어졌을 때, 주어진 최초의 형태로 출발한 기계가 어떤 유한 수의 과정을 거친 후에 표준적 형태로 궁극적으로 멈추는지의 여부를 결정하는 획일적인 절차를 명시하는 것이다. 만약 그러한 획일적인 절차가 존재하면, 계산가능성에 대한 튜링의 개념은 너무 좁다. 그러면 튜링 계산가능하지는 않지만 계산가능한 함수들이 존재하며, 특별히 u 가 그러한 함수이다. 그러나 만약 튜링의 계산가능성 개념이 어떠한 직관적인 의미에서든 계산가능한 모든 함수들을 다 포용할 수 있을 만큼 넓은 것이라면, 이 문제는 해결불가능하다.

위 문제와 밀접히 관련되었으며, 또 만약 튜링의 계산가능성 개념이 보편적이라면 마찬가지로 해결불가능한 문제가 연습문제 3.10 의 멈춤 문제이다. 곧, 튜링 기계가 연속된 일련의 1 들을 제외하고 모두 빈 칸인 테이프에서 맨 왼쪽의 1 을 읽으면서 최초 상태에서 출발하였을 때, 그 기계가 궁극적으로 멈추는지 (표준적 최종 형태든 아니면 다른 어떤 형태이든 간에) 의 여부를 발견하기 위한 획일적이고 효율적인 절차를 명시하는 문제이다. 처치의 입론이 받아들여지는지의 여부에 관계없이, 만약 멈춤 문제가 해결가능할 경우 그리고 오직 그 경우에만 (직관적 의미에서) 계산가능한 다음과 같은 함수 h 가 튜링 계산불가능하다는 것을 증명할 수 있다는 것은 주목할 만하다 : 번호가 m 인 기계가 연속된 일련의 n 개의 1 들을 제외하고는 모두 빈 칸인 테이프에서 가장 왼쪽 1 을 읽으면서 최초 상태에서 출발한 후 궁극적으로 멈추느냐 멈추지 않느냐에 따라서 h(m, n) = 2 또는 1 이다. 그러므로 처치의 입론이 옳다면, 멈춤 문제는 해결불가능하다.

우리가 지금 하려고 하는 h 가 튜링 계산불가능한 함수라는 증명은 연습문제 3.10 에 주어진 증명에 대한 더 직접적인 대안이다. 우리는 지금 u 의 계산불가능성으로부터 h 의 계산불가능성을 연역하지 않고, 직접 대각선 논변을 이용하여 증명한다. 이 목적을 위해서, 연습문제 3.10 에서는 h 가 값 1 을 갖는 조건들만을 명시했음에 반해, 여기서는 h 가 전체 함수가 되도록 완전히 정의하였다. 논변은 귀류법을 이용하고 있다. 즉 우리는 만약 h 가 어떤 튜링 기계 H 에 의해 계산된다면, 모든 양의 정수들 n 에 대해, 만약 이 n 개 1 들의 일련체에서 가장 왼쪽의 것을 읽으면서 최초 상태에서 출발한 후 멈추지 않을 경우 그리고 오직 그 경우에만 이 똑같은 상태에서 출발한 후 멈추는 그러한 다른 튜링 기계 이 존재한다는 것을 보여준다. 그러나 물론 과 같은 기계는 있을 수 없다. 왜냐하면 만약 있다면, 그 기계는 연속된 일련의 m 개의 1 들을 제외하고는 모두 빈 칸인 테이프에서 맨 왼쪽 1 을 읽으면서 최초 상태에서 출발한 후, 만약 멈추지 않을 경우 그리고 오직 그 경우에만 멈추기 때문이다.

만약 h 가 어떤 튜링 기계 H 에 의해 계산된다면, 위에서 기술된 것과 같은 종류의 튜링 기계 이 존재한다는 주장이 참이라는 것은 그림 3 을 고려함으로써 보여질 수 있다. 그림 3 속에 있는 'H' 상자는 H 의 도식을 표시한다. H 상자의 왼쪽 둥근 마디는 기계 H 의 최초 상태를 표시한다. h 가 전체 함수이므로, H 의 도식 속에는 콜론 앞에 1 이 쓰여진 것을 지시 사항으로 갖는 화살표가 없는 마디가 적어도 하나 있을 것이다. H 가 멈추는 모든 상태들이 모두 그러한 마디에 의해 표시된다. (아마도 h 의 값을 계산하는 과정에서, H 가 결코 1 을 읽지 않는 상태가 있을 수 있으므로, 거기서 H 가 멈추지 않는 약간의 상태들도 콜론 앞에 1 이 적힌 화살표가 없는 마디들로 표시될 수 있다.) 우리는 명료성을 위해 그러한 상태들이 단지 두 개만 있다고 상정했으며, 그것은 H 상자의 오른쪽 두 마디에 의해 표시되고 있다. H 의 다른 상태들과 화살표들은 상자 안에 숨겨져 있다.

그림 3 의 도식

따라서 그림 3 은 기계 H 를 부분으로 포함하고 있는 기계 의 도식을 표시하며, 은 연속된 일련의 n 개의 1 들을 제외하고는 모두 빈 칸인 테이프에서 가장 왼쪽 1 을 읽으면서 최초 상태에서 출발하였을 때, 우선 빈 칸 하나를 사이에 두고 오른쪽에 n 개 1 들의 일련체를 복사하고, 그 후 H 로 하여금 이 한 쌍의 일련체들을 투입값으로 하여 계산하도록 한다. H 의 계산 과정이 끝났을 때, 그 전체 기계 은 만약 H 가 테이프 위에 오로지 한 개의 1 만을 남겼을 경우 그리고 오직 그 경우에만 멈춘다. (H 는 항상 빈 테이프 위에 쓰여진 1 또는 11 의 왼쪽 1 을 읽으면서 끝난다.)

따라서 연속된 일련의 n 개의 1 들을 제외하고는 모두 빈 칸인 테이프에서 맨 왼쪽 1 을 읽으면서 최초 상태에서 출발하였을 때, 은 만약 이 멈추지 않을 경우 (즉, h(n, n) = 1 일 경우) 그리고 오직 그 경우에만 멈춘다. m = n 으로 놓으면, 우리는 이 존재할 수 없음을, 따라서 H 가 존재할 수 없음을 알 수 있다. 그러므로 함수 h 는 처치 입론의 옳고 그름에 관계없이 튜링 계산불가능하다. 달리 말해, 멈춤 문제는 어떠한 튜링 기계에 의해서도 해결가능하지 않다. 만약 처치의 입론이 참이면, 멈춤 문제는 절대적으로 해결 불가능하다.