알고리즘여태까지 TM을 배웠는데 이제 실생활과 관련지어 생각해보겠다.(TM) -> (high-level TM) -> (algorithm) -> (program) = (computer) 힐베르트의 10번째 문제임의의 다항식에 대해 정수근을 가지는지 판정하는 알고리즘은 무엇인가? (단, 유한번의 연산으로 판정할 수 있어야 됨)즉, 이 문제는 다항식 정수근 판별 문제가 decidable한지 묻고 있다...recognizer일단 decider보다 더 간단한 recognizer를 만들어보자...임의의 input에 대해 다항식의 문법을 지키는지 검수만약 문법이 옳다면 0, 1, -1, 2, -2, ... 를 순서대로 넣어보며 정수근 찾기-> 만약 정수근이 있다면? 언젠가 멈추고 accept-> 만약 정수근이 ..

여러가지 TM앞에서 본 TM(Deterministic Turing Machine)말고도 여러 TM이 있다.그리고 이 TM들의 power는 전부 같다! stay TMLeft, Right 말고도 제자리에 멈춰있는 Stay가 포함된 TM즉, $\delta : \ Q \times \Gamma \rightarrow Q \times \Gamma \times {L, \ R, \ S}$stay TM = TM 증명TM -> stay TM일반 TM은 stay 기능을 사용하지 않는 stay TM과 같으므로,TM을 stay TM으로 나타낼 수 있다.stay TM -> TMstay 기능을 left, right만 있는 TM에서 구현하는 법은tape과 state에 아무 변화도 주지 않고left, right 1번씩 하는 것이다.즉,..

Turing machinetape: PDA의 input과 stack 역할control: state diagram특징무제한 메모리 용량PDA의 stack마냥 메모리가 무한하다무제약 메모리 접근PDA는 stack이라 맨 윗부분만 접근 가능했지만,TM은 어느 곳이든 head를 옮겨 데이터를 읽고 쓸 수 있다.accept, reject, loopaccept, reject state에 도달만 하면 바로 accept, reject그리고 accept, reject에 도달하지 못하고 반복하는 loop가 존재할 수 잇다. 수학적 정의정의 ($Q$, $\sum$, $\Gamma$ $\delta$, $q_0$, $q_{accept}$, $q_{reject}$)$Q$: 상태의 유한 집합$\sum$: input alphabet..