은하수를 여행하는 히치하이커를 위한 안내서를 보면, 깊은 생각이 인생, 우주와 모든 것들에 대한 궁극적인 해답을 내놓을 것을 요구받으면서 대략 750만년이 걸릴 것이라고 말한다. 결과적으로 750만년동안 철학자들의 실업 사태는 유예되었지만, 중요한 것은 철학자들의 실업사태 따위가 아니다. 사람들이 잘 주목하지 않는, 심지어는 컴퓨터 전공자까지도 잘 주목하지 않았던 중요한 사실은, 깊은 생각을 만들어낸 범차원적 초지성체들은 정지문제(halting problem)를 해결할 수 있었다는 점이다!!
정지문제는, 임의의 알고리듬이 어떤 (유한한 길이의) 입력에 대하여 종료될 것인가 아닌가를 실행해 보지 않고 판단할 수 있는 알고리듬이 존재할 수 있는가-의 문제인데, 결론적으로는 이런 알고리듬은 존재할 수 없다. 왜냐하면, 이런 알고리듬은 그 자체도 종료될 수 있는가 아닌가도 판단할 수 있어야 하는데, 이 알고리듬의 결과를 사용하는 쪽에서, 종료한다는 결과가 나왔을 때 무한루프를 돌아버리면 모순된 결과가 되기 때문이다. 따라서 모든 알고리듬에 대해 정지문제를 풀 수 있는 알고리듬은 존재할 수 없다.
그런데 우리의 깊은 생각은, 문제를 듣자마자 잠시 생각한 후 계산이 750만년 후에 종료된다고 답을 냈다. 깊은 생각이 그 문제를 풀기 위해 만들어진 컴퓨터이긴 하지만, 문제를 듣고난 후에야 풀기 시작했다는 것은, 깊은 생각은 임의의 알고리듬에 대해 정지문제를 풀 수 있었다는 뜻이 아닐까! 일부 알고리듬에 대해 정지문제를 결정할 수 있는 알고리듬은 존재할 수 있지만, 범차원적 초지성체의 세계에서는 모든 알고리듬에 대해 정지문제를 결정할 수 있는 방법이 있었을 지도 모르는 일.
정지문제는, 임의의 알고리듬이 어떤 (유한한 길이의) 입력에 대하여 종료될 것인가 아닌가를 실행해 보지 않고 판단할 수 있는 알고리듬이 존재할 수 있는가-의 문제인데, 결론적으로는 이런 알고리듬은 존재할 수 없다. 왜냐하면, 이런 알고리듬은 그 자체도 종료될 수 있는가 아닌가도 판단할 수 있어야 하는데, 이 알고리듬의 결과를 사용하는 쪽에서, 종료한다는 결과가 나왔을 때 무한루프를 돌아버리면 모순된 결과가 되기 때문이다. 따라서 모든 알고리듬에 대해 정지문제를 풀 수 있는 알고리듬은 존재할 수 없다.
그런데 우리의 깊은 생각은, 문제를 듣자마자 잠시 생각한 후 계산이 750만년 후에 종료된다고 답을 냈다. 깊은 생각이 그 문제를 풀기 위해 만들어진 컴퓨터이긴 하지만, 문제를 듣고난 후에야 풀기 시작했다는 것은, 깊은 생각은 임의의 알고리듬에 대해 정지문제를 풀 수 있었다는 뜻이 아닐까! 일부 알고리듬에 대해 정지문제를 결정할 수 있는 알고리듬은 존재할 수 있지만, 범차원적 초지성체의 세계에서는 모든 알고리듬에 대해 정지문제를 결정할 수 있는 방법이 있었을 지도 모르는 일.
