컴퓨터과학이 여는 세계_9.1 튜링증명 리뷰, 시간복잡도의 개념_이광근

강좌 동영상

 예전에 스위치만 켜면 참인 명제만 만드는 기계가 존재한다 --A 라면

어떤 명제가 현실적으로 가능한 시간만에 끝난다--H 인 명제가 사실임을 증명했다. 그 증명을 짧게 요야하자면

 어떤 명제M이 있을 때, A에서 말한 기계가 M에 대하여

'M이 끝난다'

'M이 끝나지 않는다'

를 밝힐 것이다. 그런데 그것을 밝히는 역할은 H에서 말한 기계가 하는 일이므로 A가 참이면 H도 참이다.

 또, H가 거짓이라 A가 거짓임을 밝혔다.

 그런데 강좌에서 한 학생이 질문을 한다.

만약 참인 명제만을 만드는 기계가

"어떤 명제 M이 끝나는지 아닌지 알 수 없다."

라는 명제를 증명하면 어떡하죠?

 이것을 답하기 전에 명제의 종류를 알아야한다.

먼저 기본적인 명제 'p이면 q이다' 같은 것들은 "1st order"명제라고 한다.

반면 명제에 대한 명제, 위에 질문과 같은 상위의 명제들은 "high order"명제라고 한다.

질문에 답변을 하자면 A에서 말하는 기계는 "1st order"만 증명하는 것이기에 상관없다. 한정된 세계에서 참인 명제만 만들어내는 기계여도 H를 만들 수 있다.