계산할 수 있는 것과
판정할 수 없는 것은 어디서 갈릴까요?

논문은 소수 전개를 유한한 수단으로 써 내려갈 수 있는 실수를 계산 가능하다고 부릅니다. 함수나 술어도 같은 문제를 품지만, 수의 0과 1을 차례로 적는 장면이 절차를 가장 간결하게 드러낸다고 보았습니다.

계산 가능성은 이미 알고 있는 답의 저장보다, 어떤 자리의 기호를 다음에 쓸지 유한한 규칙이 매 순간 정해 주는 데 달려 있습니다. 이 기준은 ‘정의할 수 있음’보다 좁습니다. 원문은 정의 가능하지만 계산할 수 없는 수가 있음을 예고합니다.

사람이 계산할 때도 한 순간에 무한히 많은 기호를 살피지 못합니다. 튜링은 종이를 칸으로 나누고, 현재 읽는 한 칸과 유한한 내부 상태가 다음 동작을 정한다고 추상화했습니다. 동작은 기호 쓰기·지우기, 왼쪽 또는 오른쪽 한 칸 이동, 상태 변경으로 나뉩니다.

테이프는 실제 기계 설계도가 아니라 계산 절차의 필요한 구별만 남긴 모형입니다. 종이의 2차원 배치는 1차원 띠로 부호화할 수 있다고 보며, 한 번에 제한된 양만 식별한다는 조건을 중심에 둡니다.

표의 왼쪽에는 현재 m-configuration과 주사 기호가 놓입니다. 오른쪽에는 수행할 동작과 다음 m-configuration이 적힙니다. 예를 들어 q₀, 빈칸 → 0을 쓰고 오른쪽으로 이동, q₁은 한 번의 국소 규칙입니다.

표 전체는 유한하지만 같은 줄을 여러 번 적용할 수 있습니다. 그래서 짧은 설명이 긴 출력과 무한한 실행을 만들 수 있습니다. 프로그램과 실행 기록을 구분하는 관점이 여기서 이미 드러납니다.

아래 실험은 원문의 첫 예를 단순화했습니다. 각 단계에서 테두리가 굵은 칸이 현재 읽는 자리입니다. 출력 0과 1 사이에 작업용 빈칸을 두던 원문의 세부 표기는 생략하고, 상태 변화와 반복 구조만 보입니다.

원문 §8의 직접 질문은 주어진 기계가 circle-free인지 판정하는 일반 과정입니다. circle-free 기계는 0·1 같은 첫째 종류 기호를 계속 새로 출력합니다. circular 기계는 실제로 멈추거나, 작업을 이어 가도 더는 그런 기호를 출력하지 못합니다.

오늘날 널리 쓰는 ‘임의의 프로그램이 멈추는가’와 가까운 계보를 이루지만 문장 그대로 같지는 않습니다. 이 글은 원문의 판정 문제를 먼저 설명하고, 현대적 정지 문제라는 이름은 후속 정식화와의 관계를 밝힐 때만 씁니다.

튜링은 표의 각 줄을 정해진 문자들로 바꿔 ‘표준 설명’으로 만들고, 다시 문자마다 숫자를 대응시켜 description number를 얻습니다. 기계마다 유한한 설명이 있으므로 이 번호들을 차례로 나열할 수 있습니다.

모든 자연수가 올바른 기계를 나타내는 것은 아닙니다. 특히 circle-free 기계의 번호를 satisfactory number라고 부릅니다. 바로 그 번호인지 판정하는 일반 절차가 존재하는지가 다음 질문입니다.

보편 기계 U는 입력 테이프에 다른 기계 M의 표준 설명을 받으면 M이 만드는 수열을 모사합니다. ‘가장 많은 고유 기능을 가진 특별 장치’라기보다, 설명을 읽어 그 설명대로 동작하는 해석기입니다.

하드웨어 하나와 프로그램 데이터의 분리라는 현대적 비유가 도움은 됩니다. 다만 이 논문이 현대 컴퓨터의 공학 구조를 그대로 제안했다고 확대하면 안 됩니다. 원문이 확립한 것은 유한 설명을 입력으로 받아 임의의 계산 기계를 모사하는 수학적 가능성입니다.

설명번호는 자연수이므로 어떤 기계의 설명도 다른 기계의 입력이 될 수 있고, 특별히 자기 자신의 번호도 입력으로 줄 수 있습니다. 이 자기 적용이 역설을 자동으로 만드는 것은 아닙니다. 판정기처럼 기계의 행동 전체를 정확히 분류한다고 가정한 장치와 결합될 때 대각선 구성이 가능해집니다.

자기 참조라는 말만으로 결론을 건너뛰지 않고, 무엇이 부호화되고 어떤 출력을 다시 요구하는지 단계별로 보아야 합니다.

D가 기계의 설명을 받아, 숫자를 끝없이 출력하면 s, 유한 개만 출력하면 u라고 항상 정확히 답한다고 가정합시다. H는 설명번호를 차례로 검사하고 s를 받은 기계만 셉니다. 번호 N까지 통과한 기계 수를 R(N)이라고 씁니다.

N번 기계가 통과하면 H는 그 기계의 R(N)번째 숫자를 계산해 그대로 옮겨 적습니다. 이렇게 만든 수열이 β′입니다. 예를 들어 설명번호 2·5·9가 차례로 통과했다면, 각 기계에서 첫째·둘째·셋째 숫자를 가져옵니다. 설명번호와 통과 순번은 서로 다릅니다.

각 검사는 D의 가정에 따라 끝납니다. 통과한 기계는 숫자를 계속 출력하므로 필요한 자릿수도 얻을 수 있어야 합니다. 이 가정에서 H 역시 숫자를 끝없이 출력한다고 결론 내린 뒤, H 자신의 설명번호를 만나는 경우를 검사합니다.

H의 설명번호를 K, 그때까지 통과한 순번을 r=R(K)라고 합시다. D가 u라고 답하면 앞서 H가 숫자를 끝없이 출력한다는 결론과 충돌합니다. 그러면 s라고 답할 수 있을까요?

s라고 답하면 H는 K번 기계, 곧 H 자신의 r번째 숫자를 구해야 합니다. 그런데 지금 만들고 있는 숫자가 바로 그 r번째 숫자입니다. “H의 r번째 숫자를 계산한 다음 그 숫자를 쓰라”는 요청이 같은 계산을 다시 요구하므로, 이 단계가 끝나지 않습니다. 이는 s라는 판정과 충돌합니다.

원문은 대각선 숫자를 뒤집는 β 논증도 소개합니다. 여기서 따라온 H와 β′는 숫자를 그대로 취해 계산의 진행이 막히는 경로입니다. 두 경로를 구분하면 무엇이 가정이고 어디서 모순이 생기는지 확인할 수 있습니다.

§11은 각 기계 M에 대응하는 논리식 Un(M)을 구성합니다. 그 식은 어떤 완전 구성에서 M이 특정 기호 0을 테이프에 쓴다는 상황을 형식 언어로 표현합니다. 만약 해당 논리 체계의 공식이 증명 가능한지 항상 판정하는 절차가 있다면, M이 0을 쓰는지도 일반적으로 판정할 수 있습니다.

앞선 절의 비결정 가능성과 충돌하므로 그러한 Entscheidungsproblem의 일반 해법은 없습니다. 계산 모형에서 얻은 한계를 논리식으로 번역하는 환원이 논문의 마지막 다리입니다.

아닙니다. 특정 실행이 이미 멈췄다면 그 유한 기록을 검사할 수 있고, 명백한 반복 구조를 증명할 수도 있습니다. 부정되는 것은 모든 올바른 기계 설명에 대해 항상 끝나며 정확한 답을 주는 하나의 일반 과정입니다.

사례 해결, 제한된 부류의 판정, 경험적 시간 제한과 보편적 결정 절차를 구분해야 합니다. 버튼으로 세 범위를 비교해 보세요.

논문은 오늘날 계산가능성 이론의 기준점이지만, 모든 세부가 처음부터 완전했던 것은 아닙니다. 1937년 정오표는 §11의 형식화에서 P. Bernays가 지적한 오류를 고치고 일부 문장을 수정합니다. 핵심 비결정 가능성 논증과 원문의 모든 수식을 같은 수준으로 무비판적으로 묶어서는 안 됩니다.

또한 튜링의 사람-계산자 분석은 계산 가능한 절차에 대한 강력한 정당화지만, ‘모든 물리적 과정이 튜링 기계다’ 같은 별도 철학 명제를 논문이 직접 증명한 것으로 확대할 수 없습니다.

계산할 수 있는 것은 유한한 상태와 기호, 국소 동작으로 각 단계를 정해 계속 산출할 수 있는 대상입니다. 한편 그런 기계의 설명을 모두 입력으로 받아 앞으로의 행동을 늘 정확히 가르는 보편 판정 절차는 만들 수 없습니다.

경계는 기계의 성능 부족에서 생기지 않습니다. 설명을 데이터로 다루는 보편성 자체가 자기 적용과 대각선 구성을 가능하게 하며, 전면적인 판정 가정을 무너뜨립니다. 그래서 계산 모델의 정의와 계산 한계의 증명이 한 논문 안에서 맞물립니다.