- Turing Machine의 기본개념 Turing Machine은 Tape을 이용한 오토마타이다. - tape에는 input이 들어가 있고, TM은 tape에서 read와 write 모두 가능하다. - input을 왼쪽에서 오른쪽으로만 읽는 기존의 machine들과 다르게 Left, Right, Stay방향으로 진행 가능하다. (stay의 경우 left right 두번이라고 생각하면 된다) - tape는 infinite한 성질을 가지는데, 맨 왼쪽에서 leftmove할경우 무시하고, rightmove할 경우 blank(오른쪽으로 무한한 blank를 가진다고 이해하면 쉽다)을 계속 읽을 수 있다. - TM이 accept나 reject되지 않고 loop를 가져서 무한히 동작할 수도 있다. 모든 input..