[알고리즘] Halting problem

(2021.12.08)

알고리즘 수업 들으면서 정리하기 25탄

 

w15-1 실강 정리

halting problem 을 배웠다. NP 정의도 배웠다.

교수님이 이 부분을 굉장히 자세하게 천천히 많이 설명해주셔서 오늘도 진도를 많이 안나갔다

 

교수님 추천 영상

https://www.youtube.com/watch?v=92WHN-pAFCs&feature=youtu.be 

---

 

Halting Problem (unsolvable problem)

프로그램 P와 input i 가 있고, 프로그램 P에 input i 를 넣는다. 그러면 두가지의 상황이 발생한다.

> P halts on i

> P runs forever on i

 

프로그램 P와 input i 가 있을 때, P가 i에 halt인지 아닌지를 알아낼 수 있는 프로그램 H가 존재할까?

--> Halting problem은 undecidable하다.

 

 

 

알고리즘 Halt(P,i)가 P가 i에서 halt인지 아닌지를 판단한다고 가정한다.

만약, P가 i에서 halt이면, Halt(P,i)는 true를 반환한다.

만약, 그렇지 않다면, Halt(P,i)는 false를 반환한다.

 

 

 

이 알고리즘 Halt(P,i)를 Test(P)안에 넣어주고, True는 False, False는 True로 바꾸어 출력해준다.

Halt(Test,Test)가 Test halts on input Test(True)를 의미한다고 가정하면, 이는 Test(Test) runs foever on input Test를 뜻하게 된다. 

Halt(Test,Test)가 Test runs forever on input Test(False)를 의미한다고 가정하면, 이는 Test(Test) halts on input Test를 뜻하게 된다.

 

두가지는 모두 모순된다. 즉, Halt(P,i)는 존재하지 않는다.

(사실 뭐가 모순이라는 건지.... 잘 모르겠음)

 

 

 

교수님이 또다른 예시 문제를 들어 설명해주셨는데 이 문제는 이해가 갔다