컴퓨터과학이 여는 세계_2.4 튜링기계의 급소: 튜링기계 하나는 자연수 하나_이광근
Enumeration of computable sequence
튜링기계 하나를 한개의 자연수로 표현이 가능하다.
일단, 튜링기계는 테이프와 그 위에 써질 심볼, 규칙표 그리고 기계의 상태가 필요하다.
이것들을 각각 1열로 나열하면 어떤 진수로 표현할 수 있다.
이것이 무슨 말이냐 하면 만약 심볼이 1, 2, 3, 4, ... , 9, 0 이 써져있다고 하자. 그렇다면 이것을 1열로 나열하였을 경우 1234567890이 된다. 이것은 10진수로 나타내어진 자연수로 볼 수 있다.
또, 만약 심볼이 1, 2, 3, 4, ... , 9, 0, *, # 이라고 하자. 그렇다면 1234567890*# 이 된다. 이것은 12진수로 생각해서 *은 11로 #은 12로 나타낸채로 계산을 하면 된다. 이것을 N(1)이라 하자
비슷한 맥락으로 규칙표, 기계의 상태를 동일하게 만들어 각각 N(2), N(3)라고 나타내자.
이제 이것들을 2 ^ N(1) × 3 ^ N(2) × 5 ^ N(3) 로 계산하여 하나의 자연수로 만들 수 있다.
따라서 튜링기계는 하나의 자연수와 대응한다.
자, 그럼 튜링기계의 갯수가 자연수 갯수를 넘을 수 있을까? 자연수가 무한개인데 어떻게 자연수 갯수를 넘는다는 말이 나오는 거지 라는 의문을 가질 수 있는데, 무한이라고 다같은 무한이 아니다. 예를들어, 실수는 자연수의 무한보다 무한히 많다. 왜냐하면 실수는 자연수를 포함하고도 더 많은 무한개의 수를 가지고 있기 때문이다.
이것을 대각선 논법이라고 한다.
다시 본론으로 들어가자면 튜링기계의 갯수는 절대 자연수 갯수를 넘지 못한다. 튜링기계가 아무리 무한개로 많아도 모두 자연수와 대응하기에 튜링기계의 갯수는 절대 자연수의 갯수를 넘어서지 못한다.
소프트웨어는 튜링 기계의 아이디어로부터 출발했다. 따라서 소프트웨어의 갯수도 절대 자연수의 갯수를 넘어서지 못한다.
튜링은 이 튜링기계의 급소를 이용해 '기계적인 방식으론 절대 모든 참인 수리명제를 이끌어 낼 수 없음'을 증명했다.