챔's coding 챔's coding

[Computational complexity] 알고리즘은 특정 알고리즘의 성능 특성에 대한 연구이다. [The turing machine] - 알고리즘과 계산 개념을 튜링 기계라는 추상 모델을 통해 형식화 - 튜링 머신보다 더 powerful한 디지털 computation 모델은 없다. (추상 기계 중 가장 상위) > Finite automaton : 가장 basic한 추상 기계, read만 가능 q0 : initial state(=start state) q3 : final state - input string이 있는 finite tape - tape는 왼쪽에서 오른쪽으로 read (no going back) - finite automaton은 추가적 메모리를 가지지 않음 > Turing Machine..