정보수학
수학의 무한에 대한 탐구란 기계에서는 어떤 의미일까? 본문
칸토어의 무한은 일반적인 수학에서는 다루기가 까다롭고 의미도 모호하다. 가장 대표적인 것이 바로 홀수의 전체 집합과 짝수의 전체 집합이 자연수의 전체 집합과 같다는 점이다. 자기 참조적인 성격이 있으므로, 우리가 흔히 이해하는 수학과는 다른 형태로 나타난다.
앨런 튜링은 계산을 하는 Universal Machine을 상정하고, 해당 Machine이 모든 주어진 프로그램에 대해 유한한 시간안에 답을 얻을 수 있는지 없는지 판정하는 일반적인 알고리즘이 없다는 것을 증명했다. (Alan Turing, " On computable numbers, with an application to the Entscheidungsproblem", 1936)
그러면 과연 프로그래밍에서 무한에 대한 정리는 무엇을 의미하는가? 결론부터 이야기해보면 프로그래밍의 본질은 지정한 상태의 변화의 연속이며, 무한은 그 과정에서 발생할 수 밖에 없는 유한한 시간에 끝나지 않는 변화의 반복과정이다.
(칸토어의 집합에서의 무한은 사실 이 특정 조건 상태들의 집합간 크기 비교라고도 볼 수 있다)
의미를 구체화하고자, 가장 흔히 상상해볼 수 있는 무한의 계산과정 들은 다음과 같다. (아래 외에도 사실 "실수의 집합의 전체 크기를 구하는 것"처럼, 칸토어의 집합을 응용해서 그 계산 과정을 만들 수도 있다. 만족하는 값을 계속 조사하도록 하면 된다.)
1) 0의 값에 0을 계속 더하되 1이 되면 멈추고 더한 횟수를 출력한다.(무한히 걸린다. 1 나누기 0의 값을 구하는 계산이다)
2) 0에서 2씩 더한 값을 차례로 조사하되, 각 값이 두 개의 소수로 된 합을 찾을 수 없는 경우 멈춘다(무한이라고 믿지만, 아직 무한인지 모르는 계산이다, 골드바흐의 추측)
3) 0의 값에 2를 계속 더하되, 그 값이 존재할 수 없는 수가 아니면 계속 더한다.(가장 큰 자연수 짝수를 구하는 계산이다)
4) 1의 값에 2를 계속 더하되, 그 값이 존재할 수 없는 수가 아니면 계속 더한다.(가장 큰 자연수 홀수를 구하는 계산이다)
이 계산들은 사실은 끝이 나지 않을 것이라고 예측되는 것들인데, 이 중에 어떤 것은 분명히 무한이지만, 어떤 것은 그렇지 않다. 그러면 이렇게 질문할 수 있다.
이 중에 과연 어떤 계산들이 비슷한 속성을 지니는가? 즉 사실상 같나?
칸토어는 집합의 관점에서 수의 크기를 정리했다. 그러나 더 본질적인 것은 위 계산 과정들을 그룹핑하는 일이다. 어찌보면 앨런 튜링은 유한시간에 끝나는가 아닌가라는 단순한 질문에 대해 탐구한 것이고, 칸토어는 1:1 대응이라는 방법과 집합론을 통해 더 일부를 정리해놓은 것이다.
원래 수학이나 프로그래밍은 그 연산 결과에만 관심이 있었던 셈이다. 그런데 이제 그 연산 결과가 끝나지 않는 연산들을 만나게 되었다. 이를테면 1나누기 0같은 것들이다. 과연 이것들을 어떻게 다뤄야 하는가?
왜 그것이 중요하느냐면, 무한의 문제의 결론을 내어야 다음으로 넘어갈 수 있는 문제들이 존재하기 때문이다. 이를 테면 미적분도 이러한 무한대와 무한소의 문제를 일부 겪는다. 신기하게도 위의 예에서 보듯이 골드바흐의 추측도 무한의 문제로 바꿀 수 있다(사실은 모든 증명 문제가 그러할 수 있다. 무한을 포함해 전체 경우의 수를 조사하면 그만이다). 우리가 계산은 할 수 없을지라도 무한히 소요되는 계산의 특성을 이해하면, 그 이해에 바탕해서 또다른 문제를 풀 수가 있는 것이다. 앞서 이야기한 미적분의 문제나 원의 면적 문제도 마찬가지다. 우리가 무한 계산의 특성만 알아도 무언가 가정을 통해 실제 값을 구할 수 있는 경우들이 생긴다.
따라서 이 무한의 문제를 이해하는 것은 더 여러가지 계산으로 가는 지름길이 된다. 우주의 시간은 무한하지만 그 끝에 무엇이 있을지 우리는 이러한 무한에 대한 이해를 통해 계산의 결과를 훔쳐볼 수 있다. 그리고 칸토어가 집합론을 통해서 수의 집합을 유형화하고 등급화한 것처럼 더 나아가 어떤 계산의 절차들을 그렇게 할 수 있다면 더 많은 문제들의 해답을 내놓을 수 있는 것은 아닐까?
이렇게 튜링이 처음 고민했던 계산상의 무한해보이는 과정들에 대한 이해가 수학의 무한에 대해 더 많은 이해를 제공해 줄 수는 있지 않을까?