컴퓨터과학이 여는 세계_4.1 질의응답 및 멈춤문제를 자동으로 풀 수 있다면 가능해지는 일들_이광근

강좌 동영상

 만약, 아주 만약에 멈춤문제를 증명하는 튜링기계를 만들 수 있다면 어떻게 될까?

그렇게 된다면, 여러가지 수학난제들이 바로 해결된다.

예를 들어보자

골드바흐의 추측: 2이상의 짝수는 소수 두개의 합으로 이루어져 있다. (ex. 8 = 3+5, 12 = 5+7)

페르마의 마지막 정리: 자연수 n > 2에 대해서 a^n + b^n = c^n인 자연수a, b, c는 없다.

 다음 명제들을 튜링기계로 짠다고 했을 때, 하나씩 다 해보면서, 반례가 존재하는지 확인하는 튜링기계를 만들면 된다. 만들고 난 후, 멈춤문제를 증명하는 튜링기계에게 입력으로 준다. 그렇다면 멈춤문제를 증명하는 튜링기계는 딱 보고 유한시간만에 '이건 반례를 찾아서 끝나겠다.' 아니면 '반례가 없기 때문에 끝나지 않는다.'라고 나오는 것이다. 반례의 유/무로 위 명제들을 자동으로 증명하는 셈이다.