1
Contents
과제✔
- 자신의 실험 결과에 대한 write-up 을 쓰세요.
-
사람은 어떤 학문을 이해하든지 간에 그 학문이 정말로 맞는지 확인하기 위해 자신만의 실험을 하기 마련이다. 특히 컴퓨터 공학은 그러한 실험이 많이 일어나는데 어제의 내용과 오늘의 내용을 이해하기 위해서 자신이 했던 생각이나 의문이나 고민을 write-up 에 작성하고 그 생각과 의문과 고민을 해결하기 위해서 시도했던 실험과 실험 결과를 write-up 에 작성하시오.
-
튜링이 괴델의 불완전성 정리를 자신의 방법으로 증명했다는 이야기를 듣고, 이에 대해 알아보고 싶었다. 그래서 halting problem에 대해 알아보았는데 알아본 결과는 다음과 같다
Halting problem✔
- 어떤 프로그램과 입력을 받았을 때, 그 프로그램을 실행했을 때 유한한 단계 후에 끝날지 혹은 영원히 끝나지 않을지를 판별할 수 있는 문제
Q. 컴퓨터는 정지 문제를 해결 할 수 있을까?
귀류법으로 증명 (앨런 튜링이 증명)
귀류법 : 어떤 명제가 참임을 증명하려 할 때, 그 명제의 결론을 부정함으로써
가정 또는 공리등이 모순됨을 보며 간접적으로 그 결론이 성립한다는 것을 증명하는 방법
대전제 : 정지 문제를 판별하는 알고리즘이 존재한다.
정지 문제를 판별하는 알고리즘 : halting ( A, B)
A : 임의의 프로그램.
B : 임의의 입력 값.
프로그램이 정상적으로 종료가 된다 -> true반환
프로그램이 정상적으로 종료가 되지 않는다 -> false반환
c Function check (A) { If (halting(A, A) == false) Return true; eles Infinite loop; } Check (check); Function check
A라는 입력 값을 받고 있음(여기서 A는 check이기도함)
내부적으로 halting (A,A)를 호출하고 있음
(A는 프로그램이지만, 컴퓨터 내부적으로는 0과 1로구성이되었므로 입력 값이 될 수 있음)
A라는 프로그램에 자기 자신이 입력 값으로 들어가 무한 루프가 빠진다면
halting이 false를 반환하여 check 함수는 true를 반환 할 것이고, 만약 정상적으로 종료할 경우 check 함수는 무한루프에 빠질 것이다.
Check (check) 가정 1. Check (check)가 정상적으로 종료되었다.
halting(check, check)가 거짓이다. 즉 halting(check, check)은 무한루프를 돈다
하지만 Check (check)은 정상적으로 종료해야 함
-> 참일 수가 없음
가정 2. Check (check)가 무한 루프에 빠졌다.
halting(check, check)이 잘 종료 되었다. 즉, true를 반환한다.
하지만 Check (check)가 무한루프라고 가정 했기 때문에 모순이 발생
-> 거짓일 수가 없다.
결론
-
halting(check, check)는 참도 거짓도 될 수 없다는 모순이 발생
-
따라서 Halting은 존재할 수 없음