[Lec.Halting] Undecidability, Halting Problem - 11주차 2강

11월 13일 - 11주차 2강

정지 문제를 대학 전공 수업에서 한 번도 다루지 않았다는 사실에 충격을 받은 교수님...

급기야 추가 렉쳐를 기획하게 되는데....

* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.

 

• 예, 아니오로 대답할 수 있는 문제
  • 유한 오토마타가 문자열을 인식하는가? CFG가 ambiguous 한가?
  • 결정 가능 문제: 모든 입력에 대한 올바른 답(예/아니오)를 유한 시간 내에 출력 가능한 알고리즘 존재
  • 결정 불가능 문제: 모든 입력에 대해 항상 올바른 답을 출력할 수 있는 알고리즘을 만드는 것이 불가능한 문제
• TSP 외판원 문제 -  다른 문제로부터 결정 문제로 변가능
  • 최적화 문제: 모든 도시를 정확히 한 번씩 방문하고 시작 지점으로 돌아오는 최단경로 찾기
  • 결정 문제: 주어진 거리 d 이하의 경로가 존재하는지 확인하는 문제

결정 가능 문제(Decidable Problems)의 예시:

1. 정규식 매칭: 문자열 sss가 정규식 rrr에 매칭되는가?
2. FA를 이용한 문자열 인식: 문자열 sss가 유한 오토마타(FA)에서 인식되는가?
3. 외판원 문제의 결정 버전: 모든 가능한 경로를 탐색하면 "예" 또는 "아니오"로 답할 수 있음.
4. 집합 멤버십 확인: 주어진 요소 yyy가 유한 집합 XXX의 원소인가?

---

결정 불가능 문제(Undecidable Problems)의 예시:

1. 정지 문제(Halting Problem): 프로그램 ppp와 입력 iii가 주어졌을 때, p(i)가 종료되는가, 아니면 무한 루프에 빠지는가?
2. CFG 모호성: 문법 GGG가 모호한지 여부.
3. CFG 동등성: 두 문법 G1​과 G2의 언어가 동일한지 L(G1)=L(G2) 확인.
4. 프로그램의 안전성/정확성 증명: 프로그램이 항상 속성 ϕ를 만족하는가?

• halt(p,i)는 프로그램 p와 입력 i가 주어졌을 때, p(i)가 종료하면 true, 아니면 false
• inverse는 half의 결과를 반대로 작동하도록 설계되었음
• half(inverse,inverse)=true라고 가정
  • half의 정의에 따르면 inverse(inverse)는 종료해야 함
  • 그러나 inverse의 line 4~5에 의하면 inverse(inverse)는 loop forever에 빠짐 -> 모순
• half(inverse, inverse)=false라고 가정
  • halt의 정의에 따르면 inverse(inverse)는 종료하지 않아야 함
  • 그러나 inverse의 2~3줄에 따르면 inverse(inverse)는 종료해야 함 -> 모순

• claim: 이상적인 분석기는 항상 어떤 program이나 specification에 대해 safe or unsafe 결과를 출력할 수 있음
• proof by contradiction: 모순논법, 이상적인 분석기가 존재한다고 가정
  
  • 프로그램 P에 대해 assert(false)를 추가한 새로운 프로그램 P' assert(false)를 만듦
    • P가 종료하면 P'은 unsafe로 판정
    • P가 종료하지 않으면 P'은 safe로 판정
  • 이상적인 분석기가 있다면 정지 문제를 해결할 수 있어야 하지만, 정지문제는 결정불가능하기 때문에 모순