제12장. Algorithmic Computation의 한계 학습목표 계산기계의 한계를 undecidability로 살펴보고, TM 이외의 다른 계산 모델을 소개한 후, 실제 문제해결에 필요한 계산복잡도에 대하여 알아본다.  이제까지 배운 오토메타/형식언어를 넘어선 advanced topic으로의 연결고리

개요 이제까지 공부한 오토메타/형식언어 이외의 것들을 한번 정리해 봅니다. Algorithmic computation의 한계 - TM으로 풀 수 없는 문제? - Post correspondence problem 다른 계산모델들 - Recursive functions - Post systems - Rewriting systems Computational complexity - TM과 complexity - Language family와 complexity class : P & NP  undecidability  halting problem  변환  좀더 실용적인 CFL를 위한 도구 기본 개념만 이해하고 넘어갑시다.

no limit on the length of computation TM으로 풀 수 없는 문제들 주어진 특정한 문제는 언제나 decidable! decidable : ∃ a TM giving correct answer for all domains TM halting problem : for (M, w), q0w ├ qf halting ? no limit on the length of computation  간단해 보이지만 복잡한 문제의 불가해성을 입증하는 핵심문제!

Undecidability 그러나… Thm : TM halting problem is undecidable pf) decidable 하다고 assume Copy w M q0 qy qn H qa qb  이거 모순이잖아! cf) 모든 (wM, w)에 대한 correct decision algorithm 없음

Reduction에 의한 Undecidability 증명 Decidability를 보일 때마다 복잡하게 할 것이 아니라, 기존에 undecidable한 대표문제인 halting problem으로 변환하여 undecidable함을 보이는 꽁수! Reduction에 의한 Undecidability 증명  state-entry problem이 decidable하다면 halting problem이 decidable  모순 Halting P Generate Mw B-T halting A Halts No halts

Homework : Exercises 12.1 개념적인 이해가 더 중요하기는 한데… - 3 - 7 - 정도는 뒤에 해답도 있고 하니 연습해 보도록.

Undecidable Problems for R.E. Languages Recursively enumerable 언어에서는 기본적인 특성도 undecidable! Undecidable Problems for R.E. Languages general ∃ a way of reducing halting p. to the question Thm G: unrestricted grammar L(G) = Ø : undecidable Construct Gw Emptiness A Thm L(M) = finite : undecidable cf) Rice’s theorem : any nontrivial property of r.e.l is undecidable  주어진 문제가 decidable하면 halting problem이 decidable함을 보인다!

Post Correspondence Problem : undecidable CFL를 위한 Undecidability 증명용 도구 Post Correspondence Problem : undecidable 모든 circumstances Thm MPCP : undecidable p316 Fig. 12.12 Thm PCP : undecidable Fig. 12.13 주어진 문제로부터 MPCP로 유도 Undecidable함을 증명

Undecidable Problems for CFL 증명과정 보다도 결과에 대한 이해필요! Undecidable Problems for CFL Thm ∃ no alg. deciding whether any given CFG is ambiguous Thm ∃ no alg. deciding whether L(G1) ∩ L(G2) = Ø for arbitrary CFG G1 & G2 ※ ∃ no completely general algorithm but only for some situations 자, 이제 TM의 한계도 명백해졌으니 다른 계산모델의 가능성을 알아볼까요?

< Other Models of Computation > 그러기에는 시간도 부족하고, 대학원의 고등논제를 기약합시다. 다만, 정의라도 < Other Models of Computation > math ↑ Newton Leibniz Complete Math? Consistent system must be incomplete G del’s Incomplete Theorem Computation Models Recursive functions Post systems equivalent ∴ Church-Turing Thesis no more powerful models can be found. Church’s thesis Rewriting systems : Matrix grammars, Markov algorithms, L-systems  용어나 기본 흐름 정도를 이해합시다.

< Computational Complexity > in real computers 단순히 풀 수 있는지/없는지가 아니라 얼마나 효율적으로 풀 수 있는지에 대한 검증필요  not only solvable but tractable (algorithm) < Computational Complexity > in real computers efficiency ◎ time space complexity sorting : nlogn satisfiablility problem : - unknown of nonexponential deterministic algorithm

Complexity Classes P & NP ◎ or P = NP  Unsolved question! conjecture P NP-complete NP 아직까지 P가 아닌 NP에 대한 명확한 증명은 없지만, 아마 P != NP라고 생각 계산기계로서의 오토메타와 형식언어를 넘어선 계산이론에 대한 고찰은 알고리즘 분석이나 대학원에서의 교과목에서 다루게 되며, 문제해결자의 입장에서는 주어진 문제가 과연 풀리는지, 얼마나 쉽게 풀 수 있는지를 분석적으로 이해하는 능력이 중요함.