괴델에서 컴퓨터까지 철학의 중요성 1

발생

괴델 불완전성의 정리 해당 영상에 영향을 받아 작성하게된 괴델에서 컴퓨터까지 철학이 우리에게 어떤 영향을 주었는지에 대한 글

난 복잡하게 글을 쓰지 않고 아주 단순화하여 작성 할 것이다. 그게 더 뇌리에 깊숙이 박힐거라는 생각이 있기 때문이다.

괴델 - 불완전성의 정리

괴델이 펼쳐낸 불완전성의 정리란 한마디로 정리하면 아래와 같다.

모든 논리 체계는 완전하지 않다.

괴델이 실제로 이를 증명해낸 방법은 직접 찾아보는 것이 더 확실 할 것이다. 하지만 나는 아주 단순하게 비유해보겠다.

특정 논리 체계를 만든다.
해당 논리 체계 내의 논리로 “이 명제는 증명되지 않는다” 라는 명제를 만든다.
이 명제를 증명 하게되면 증명되지 않는 명제를 증명하게 됨으로 그 논리 체계는 모순이 존재하게 된다.
명제를 증명하지 않는다면 그 논리 체계에서는 증명하지 못하는 명제가 존재하게 된다.
이는 곧 다른 논리 체계에도 적용이 된다. 곧 모든 모순이 존재해선 않되는 논리 체계에서는 증명하지 못하는 명제가 반드시 존재한다.

괴델이 이러한 정리를 펼쳐낸 이유는 괴델 이전의 수학자들 중 대다수는 완전무결한 논리 체계의 형성이 가능하다고 믿고있었다. 괴델은 이러한 학자들에게 인간이 만든 논리 체계에는 항상 허점이 있으며 항상 새로운 방향성이 존재한다는걸 일깨워쳐준 것이다.

괴델의 정리는 기존의 논리 체계 틀에서 사람들을 자유롭게 해준것이다.

앨런 튜링 - 튜링 머신

괴델의 정리는 당대 여러 인물들에게 큰 영향을 끼쳤으며 컴퓨터의 아버지라고 불리는 앨런 튜링 또한 영향을 받았다.

앨런 튜링은 괴델의 정리를 자신만의 방법으로 풀어내었고 자신만의 논리 체계를 만들어 이를 증명하였다.

튜링이 고안해낸 논리 체계는 튜링 머신을 이용한 논리 체계였다. 튜링이 증명해낸 방법을 간략화 하자면 아래와 같다.

여러 프로그램들을 실행 시킬 수 있는 튜링 머신들을 정의한다.
튜링 머신의 동작은 프로그램 화 시킬 수 있다. (튜링 머신의 동작 = 프로그램)
프로그램을 입력으로 받아 내부적으로 동작시켜 결과를 확인 할 수 있는 만능 튜링 머신 $U$ 를 정의한다.
$U$ 를 이용해 모든 프로그램의 정지 여부를 알 수 있는 튜링 머신 $H$ 가 존재한다고 가정한다.
$H$ 를 이용해 튜링 머신 $H^+$ 를 정의한다.
$H^+$ 는 내부적으로 $H$ 를 호출하여 프로그램을 실행한다.
1. $H$ 가 프로그램이 정지 한다고 결과를 반환하면 $H+$ 는 무한 루프에 진입한다.
2. $H$ 가 프로그램이 정지하지 않는다고 결과를 반환하면 $H+$ 는 즉시 정지한다.
$H^+$ 에 $H^+$ 프로그램을 입력으로 넣으면 모순이 발생한다.
1. 입력으로 받은 $H^+$ 가 정지한다고 $H$ 가 판단할 경우 $H^+$ 는 무한 루프에 진입
2. 반대로 입력으로 받은 $H^+$ 가 무한 루프에 진입한다고 $H$ 가 판단 할 경우 $H^+$ 는 정지
3. 결국 항상 $H$ 의 판단과는 모순되게 $H^+$ 의 정지 여부는 정해진다.
따라서 모든 프로그램의 정지 여부를 알 수 있는 튜링 머신 $H$ 는 존재 할 수 없다.

나는 이 방법에서 개인적으로 가장 헷갈린 부분은 $H^+$ 에 $H^+$ 를 넣었을 때 왜 모순이 발생하는지였다.
$H^+$ 를 프로그래밍적으로 사고하면 항상 새로운 Call Stack 에 쌓이는 함수를 생각하게 되어 이해에 방해가 됐었는데 수학적 정의로 사고하면 $H^+ = Stop$ 과 $H^+ = Loop \space Forever$ 라는 정의가 동시에 공존 할 수 없다는게 바로 인식되서 이해가 쉬웠다.

결론

작성 시간이 길어져서 오늘은 이정도만 작성 후 마저 작성하겠다.

튜링은 괴델의 증명을 아름다운 방법으로 풀어내었고 이런 과정에서 현대 컴퓨터의 기초 이론이 되는 튜링 머신을 만들었음에 엄청난 업적을 이뤘음에 그 누구도 반박하지 못할 것이다.

튜링이 이러한 증명을 하게된 이유는 힐베르트의 질문에 의한 것이라는 점을 알아두면 좋다. 나중에 힐베르트가 수학계에 던진 질문에 대해서 정리해보아도 재밌을 것 같다.

Day-58

philosophy