어떤 목록을 아무리 길게 만들어도 빠지는 계산이 있을까?

모든 목록의 밖에 있는 똑같은 열을 만든다는 뜻일까요?

5. 모든 목록의 밖에 있는 똑같은 열을 만든다는 뜻일까요?

주의해야 할 대목이 있습니다. d는 목록 L에 따라 만들어집니다. L을 바꾸면 대각선 자리의 값도 바뀌며 새 열 d도 달라집니다. 따라서 모든 목록에 대해 단 하나의 고정된 이진열이 항상 빠져 있다는 주장과는 다릅니다.

또한 새 열을 만드는 규칙이 간단해 보인다고 해서 언제나 컴퓨터가 계산할 수 있다는 뜻도 아닙니다. L(n)(n) 값을 얻으려면 해당 목록의 n번째 행과 n번째 자리 값을 계산할 방법이 필요합니다. L이 전혀 계산 가능한 방식으로 제공되지 않았다면 d를 계산할 수 있다는 보장은 없습니다. 이 구별은 뒤에서 컴퓨터 프로그램의 한계를 다룰 때 결정적입니다.

대각선 논법은 주어진 목록의 모든 행과 적어도 한 자리에서 다른 열을 만든다는 집합론적 증명입니다. 이 결과를 바로 '어떤 특정 프로그램으로도 모든 계산을 할 수 없다'는 주장으로 바꾸려면, 프로그램을 어떤 방식으로 나열하고 어떤 값을 실제 계산할 수 있는지를 새롭게 정의해야 합니다.

6. 컴퓨터 프로그램에도 자연수 번호를 붙일 수 있나요?

프로그램은 유한한 길이의 기호열로 기록됩니다. 0과 1로 된 코드로 모든 프로그램을 표현할 수도 있습니다. 유한한 이진 문자열은 길이가 0인 것부터 1인 것, 2인 것 순으로 나열할 수 있습니다. 각 길이의 문자열은 유한 개이므로 모든 유한 문자열에 자연수 번호를 붙일 수 있습니다.

정확한 코딩 방법과 문법의 차이는 있지만, 이 사실로부터 프로그램 전체가 많아야 가산 무한임을 알 수 있습니다. 모든 프로그램이 서로 다른 계산을 하지는 않습니다. 한 프로그램이 여러 입력에서 같은 결과를 내거나 어떤 입력에서는 끝나지 않을 수도 있습니다. 그럼에도 서로 다른 프로그램의 총수는 가산이라는 사실은 유지됩니다.

여기서 앞의 B와 프로그램의 집합을 비교할 수 있습니다. B에는 모든 무한 이진열이 있고 그 수는 비가산입니다. 반면 프로그램 코드는 유한 문자열이므로 가산입니다. 따라서 계산 가능한 이진열은 전체 B보다 훨씬 적습니다. 계산할 수 없는 무한 이진열이 존재한다는 결론을 얻습니다. 이것은 집합 크기의 비교로 얻은 존재 정리입니다.

7. '가산'인데도 모든 것을 계산하지 못한다는 사실

이 결론이 의아할 수 있습니다. 프로그램에도 0번부터 번호를 붙이고, 자연수에도 0번부터 번호를 붙이는데 왜 프로그램으로 모든 이진열을 만들 수 없을까요? 핵심은 프로그램 한 개가 나타내는 것이 무한 이진열 하나라는 점입니다. 자연수로 셀 수 있는 개수만큼의 프로그램으로 표현할 수 있는 이진열은 가산 개뿐입니다. 그런데 모든 이진열의 집합은 비가산입니다.

이 논증에는 중요한 한계도 있습니다. 비가산성을 이용하면 계산할 수 없는 이진열의 존재를 보일 수 있지만, 그 자체로 특정한 유명한 문제 하나가 계산 불가능하다고 증명하지는 않습니다. '어떤 수는 계산 불가능하다'와 '정지 문제는 결정할 수 없다'는 다른 강도의 질문입니다. 실제 문제의 판정 불가능성을 얻으려면 문제의 구조를 구체적으로 사용해야 합니다.

이제 표의 값 0과 1을 프로그램이 멈추는지 여부로 바꿔 봅시다.

정지 문제의 두 입력을 구분합니다

8. 정지 문제의 두 입력을 구분합니다

프로그램 P와 입력 x를 주었을 때 P가 x를 받아 유한한 단계 뒤에 멈출지 알아내는 문제를 생각합니다. 여기서 '멈춘다'는 뜻은 프로그램의 실행이 종료된다는 뜻입니다. 프로그램이 1을 출력하거나 0을 출력하는 것과 구별해야 합니다. 어떤 프로그램은 계산을 끝내고 0을 출력할 수 있고, 어떤 프로그램은 1을 출력할 수도 있으며, 어떤 프로그램은 끝없이 반복할 수도 있습니다.

정지 판정기 H(P,x)를 가정해 봅시다. 이 프로그램은 어떤 유효한 프로그램 코드 P와 입력 x를 넣어도 반드시 멈춰서 정확한 답을 내놓는다고 가정합니다. 멈춘다고 판단하면 1, 끝나지 않는다고 판단하면 0을 돌려줍니다.

H(P,x)=1 ⇔ P(x)가 언젠가 멈춘다

H(P,x)=0 ⇔ P(x)가 끝없이 실행된다

실제로 이러한 H가 있다는 뜻은 아닙니다. 지금은 그 가능성을 가정하고, 그 가정과 충돌하는 프로그램을 만들어 보려는 것입니다. 판정기가 반드시 종료해야 한다는 조건을 빼면 정지 문제를 정확히 규정한 것이 아닙니다.

9. 한 프로그램을 자기 자신의 입력으로 넣습니다

모든 프로그램은 유한한 코드로 표현되므로 그 코드를 입력 데이터로도 취급할 수 있습니다. P의 코드를 다시 P 자신에게 주는 실행을 P(P)라고 간단히 적겠습니다. 실제 프로그램 언어에서는 코드를 입력 가능한 문자열 형태로 부호화해야 합니다. 여기서 P(P)는 그 부호화 절차를 생략한 교육용 표기입니다.

이제 H(P,P)를 계산하면 판정기 H는 프로그램 P가 자기 코드를 입력받았을 때 멈추는지 답해야 합니다. H가 정말 모든 P와 x에 대해 정확하게 작동한다면 이런 자기 입력 사례도 예외일 수 없습니다.

집합론의 대각선 규칙에서는 n번째 행과 n번째 자리를 비교했습니다. 계산 문제에서는 n번째 프로그램의 자기 입력을 조사합니다. 둘 다 같은 번호를 두 위치에 사용하는 것이 핵심이지만, 새 결과가 놓이는 수학적 맥락은 다릅니다.

10. 판정기의 대답을 뒤집는 프로그램 D

다음과 같은 새 프로그램 D를 생각합시다. 입력으로 프로그램 코드 P를 받습니다. 먼저 H(P,P)를 실행합니다. H가 1이라고 답하면 D는 무한 반복에 들어가고, H가 0이라고 답하면 D는 즉시 멈춥니다.

D(P): H(P,P)=1이면 계속 반복, H(P,P)=0이면 즉시 종료

이것은 H를 호출한 다음 결과에 따라 두 동작 중 하나를 택하는 유한한 코드입니다. H가 언제나 끝나고 정확한 답을 준다는 가정이 있으므로 D도 유효한 프로그램으로 작성할 수 있습니다. 이 단계에서 아직 모순은 생기지 않았습니다.

이제 D 자신의 코드를 입력으로 넣어 D(D)를 실행합니다. H가 자기 입력 사례인 H(D,D)에 대해 답을 해야 하므로, 가능한 답 1과 0을 모두 검토하겠습니다.

첫째 경우: H(D,D)=1이라고 답한다면

11. 첫째 경우: H(D,D)=1이라고 답한다면

H가 1이라고 답한다는 것은 D(D)가 언젠가 멈춘다는 예측입니다. 그러나 D의 규칙은 H의 답이 1이면 무한 반복에 들어가도록 정의되어 있습니다. 따라서 D(D)는 끝나지 않습니다. H의 예측과 D의 실제 동작이 서로 충돌합니다.

이 모순은 실행 시간이 길다는 뜻이 아닙니다. 1초, 100년, 무한히 긴 시간 중 어느 시점에 끝날지 추측하는 문제가 아니라, '멈춘다'고 한 답과 '멈추지 않는다'는 정의된 동작이 양립할 수 없다는 뜻입니다.

12. 둘째 경우: H(D,D)=0이라고 답한다면

이번에는 H가 D(D)가 끝나지 않는다고 예측합니다. 그런데 D의 규칙은 H가 0을 내놓으면 즉시 종료하도록 되어 있습니다. 그러므로 D(D)는 멈춥니다. 이번에도 판정기의 예측과 실제 동작이 충돌합니다.

H는 항상 0 또는 1을 내놓도록 가정했으므로 가능한 답을 모두 검토했습니다. 두 경우 모두 모순입니다. 따라서 처음에 세운 가정, 즉 모든 프로그램과 입력에 대해 항상 종료하며 정지 여부를 정확하게 판정하는 알고리즘 H의 존재가 부정됩니다.

¬∃H ∀P ∀x [H(P,x)가 항상 종료하고 정확하게 정지 여부를 판정한다]

이 결론은 모든 프로그램이 실행되지 않는다거나 어떤 특정 프로그램의 정지 여부도 결코 알 수 없다는 주장이 아닙니다. 개별 프로그램이 멈춘다는 사실은 직접 실행해 확인할 수 있습니다. 다만 모든 프로그램과 입력을 처리하는 범용적인 완전 판정기는 존재하지 않습니다.

13. 정지 여부를 부분적으로 알아내는 방법도 있나요?

P(x)를 직접 실행하다가 끝나면 '멈춘다'라고 답할 수 있습니다. 이 절차는 P(x)가 실제로 멈추는 경우에는 언젠가 답을 내놓습니다. P(x)가 끝없이 반복되면 그 절차 또한 계속 기다리게 됩니다. 이런 성질을 '멈춤 사례를 반결정할 수 있다' 또는 '정지 집합이 재귀적으로 열거 가능하다'고 설명합니다.

반결정과 완전 결정을 분리하면 정지 문제에 대한 과장된 설명을 피할 수 있습니다. 어떤 프로그램의 종료를 증명하거나 테스트하는 일은 실제로 가능합니다. 컴퓨터가 모든 프로그램에 대해 '멈춤/무한 반복'을 반드시 답하는 일반 알고리즘을 가질 수 없다는 것이 정리의 정확한 내용입니다.

실제 소프트웨어 검증 시스템이 많은 프로그램의 성질을 검사한다고 해서 정지 문제의 정리와 충돌하지 않습니다. 그 시스템은 검사 대상 언어·규칙·시간·자원 또는 답변 가능한 사례의 범위를 제한할 수 있습니다.

칸토어의 대각선과 튜링의 대각선은 같은 정리일까요?

14. 칸토어의 대각선과 튜링의 대각선은 같은 정리일까요?

두 논증은 모두 목록의 n번째 항목과 같은 번호의 자리를 사용한 뒤 그 값을 뒤집는 구조를 공유합니다. 칸토어에서는 무한 이진열의 목록 L에서 d(n)=1−L(n)(n)이라고 정했습니다. 튜링의 현대적 교육용 정지 논증에서는 H(P,P)의 답과 반대로 움직이는 D(P)를 정의했습니다.

하지만 칸토어의 결론은 모든 무한 이진열이 가산 목록에 들어갈 수 없다는 집합의 크기에 관한 결과입니다. 정지 문제의 결론은 특정 성질을 모든 프로그램에 대해 정확히 판정하는 계산 절차가 존재하지 않는다는 결과입니다. 튜링의 논증에서 계산 가능한 H를 가정했기 때문에 D도 계산 가능한 프로그램으로 정의할 수 있고, 그 D가 바로 H의 가정에 모순을 일으킵니다.

그래서 '같은 대각선 발상'이라는 말은 맞지만, 두 결과의 증명 조건과 대상까지 동일하다는 뜻으로 쓰지 않습니다.

15. 왜 계산 가능한 전체 함수만 나열하면 조심해야 하나요?

'모든 계산 가능한 함수 f₀,f₁,f₂,…를 나열한 다음 g(n)=1−fₙ(n)을 계산하자'는 생각은 매우 그럴듯합니다. 그러나 결정적인 질문이 있습니다. n을 입력하면 fₙ(n)을 항상 계산할 수 있는 통일된 절차가 주어졌나요?

각각의 fₙ이 개별적으로 계산 가능한 함수라는 사실만으로 n에서 fₙ을 찾아 그 값을 계산하는 통일된 알고리즘이 존재한다는 결론은 나오지 않습니다. 특히 0과 1을 반환하는 모든 전역 계산 가능 함수의 목록을 항목과 입력에 따라 일관되게 계산 가능한 표로 만드는 일은 불가능합니다. 그런 표가 있다고 가정하면 대각선 뒤집기를 한 결과 g 역시 계산 가능하면서 목록의 어느 행에도 없게 되어 모순이 생기기 때문입니다.

이 대목을 생략하고 '대각선으로 만든 함수는 언제나 계산 가능하다'고 설명하면 증명이 틀립니다. 목록이 단순히 존재하는지와 그 목록을 프로그램이 실제로 계산할 수 있는지에 대한 조건을 구별해야 합니다.

16. 괴델의 대각화에서는 무엇을 뒤집을까요?

제11회에서 살핀 괴델의 불완전성 정리는 산술 명제와 형식적 증명에 번호를 붙이는 데서 시작합니다. 특정 산술 명제 안에 그 명제 자신의 번호를 집어넣는 고정점 구성으로, 자신이 주어진 이론에서 증명되지 않는다는 성질과 연결되는 명제를 얻습니다.

전문적으로는 대각화 보조정리에 따라 적절한 공식 A(x)에 대해 F ⊢ G ↔ A(⌜G⌝)인 문장 G를 구성합니다. ⌜G⌝는 G의 기호열에 배정된 수, 즉 괴델 번호입니다. A가 '그 번호의 문장이 F에서 증명되지 않는다'는 성질을 나타내도록 택하면 불완전성의 핵심 구성이 됩니다. 실제 정리에는 이론 F의 공리화 가능성, 산술 표현 능력, 무모순성 등 조건이 따릅니다.

이 구성은 칸토어가 무한 이진열의 대각선 자리를 뒤집는 방법이나 정지 판정 프로그램을 역행시키는 방법과 닮았지만, 단순한 자기 부정 문구만으로 성립하는 것은 아닙니다. 부호화가 정확하고 증명 가능성을 산술 안에서 표현할 수 있어야 논리학의 정리가 됩니다.

자기 언급이 나오면 언제나 역설일까요?

17. 자기 언급이 나오면 언제나 역설일까요?

'이 문장은 한국어로 적혀 있다'는 자기 언급은 모순을 일으키지 않습니다. 어떤 프로그램이 자기 코드의 길이를 계산한다고 해도 그 자체가 논리적 모순은 아닙니다. 자기 언급이 등장한다는 사실만으로 역설이 발생하지 않는다는 점을 기억해야 합니다.

대각선 논증은 자기 번호의 자리에 접근해 기존 목록 또는 가정된 판정과 강제로 어긋나도록 구성하는 규칙이 핵심입니다. 칸토어에서는 0과 1을 뒤집었고, 튜링에서는 멈춘다는 답을 받으면 무한 반복을, 멈추지 않는다는 답을 받으면 종료를 실행하도록 만들었습니다. 괴델에서는 형식적 증명 가능성에 관한 표현과 자기 번호의 대입을 정교하게 결합했습니다.

모순이 실제로 발생하는 위치는 각 증명에서 명확하게 보여야 합니다. 단지 '스스로를 가리키기 때문에 불가능하다'고 요약하면 논증을 이해할 수 없습니다.