[계산이론](20)[TM과 알고리즘]

알고리즘
여태까지 TM을 배웠는데 이제 실생활과 관련지어 생각해보겠다.
(TM) -> (high-level TM) -> (algorithm) -> (program) = (computer)

 

힐베르트의 10번째 문제

임의의 다항식에 대해 정수근을 가지는지 판정하는 알고리즘은 무엇인가?
    (단, 유한번의 연산으로 판정할 수 있어야 됨)

즉, 이 문제는 다항식 정수근 판별 문제가 decidable한지 묻고 있다...

• recognizer
  일단 decider보다 더 간단한 recognizer를 만들어보자...
  1. 임의의 input에 대해 다항식의 문법을 지키는지 검수
  2. 만약 문법이 옳다면 0, 1, -1, 2, -2, ... 를 순서대로 넣어보며 정수근 찾기
  -> 만약 정수근이 있다면? 언젠가 멈추고 accept
  -> 만약 정수근이 없다면? 안 멈추고 계속 loop
  
  
• decider
  아까 recognizer를 만들었을 때,
  만약 어디까지 넣으면 된다는 범위가 있다면
  정수근이 없을 떄 범위까지 넣고 reject할 것이다
      변수가 1개인 다항식은 $\pm k \frac{c_{max}}{c1}$로 경계가 있다!
      k = 항의 개수, cmax = 절댓값이 가장 큰 계수, c1 = 최고차항의 계수
  그러나, Matijasevic’s theorem는 다변수 다항식에선 그런 범위가 없다는 걸 보여준다
  -> 따라서 다변수 다항식에선 decider를 만들 수 없음
  --> 힐베르트의 문제를 풀 수 없다... (알고리즘이 존재하지 않기 때문)

 

알고리즘

어떤 작업을 수행하기 위한 간단한 명령어의 모음

알고리즘 -> TM의 단계

• high-level discription: 글로 알고리즘 묘사
• implementation description: 다 완전히 나타내진 않고, head, tape 움직임 등 TM의 중요사항만 묘사
• formal description: TM의 모든 세부사항 기술

이떄, 알고리즘은 string 말고도 다양한 것을 input으로 받을 수 있다 (object)
따라서 TM으로 나타내기 위해선 적절한 encoding이 필요하다
    이때 인코딩된 object를 <A> 이렇게 표시하겠다.

• 예) A가 connected & undirected graph로 이루어진 language라 하자.
  A를 recognize하는 TM을 만들 수 있는가?? (자료구조 25 참고)
  • 알고리즘 수준
    1. 임의의 노드를 선택해 .을 찍는다
    2. 이미 mark(.)된 노드와 붙어있는 노드도 .을 찍는다
    3. 새로운 노드가 mark(.)되지 않을 때까지 2를 반복한다
    4. 모든 노드를 스캔해 .이 찍히지 않은 노드가 1개라도 있다면 reject, 모두 .이라면 accept
       

       

       
       
       
  • 응용 수준
    1. 그래프G를 TM이 계산할 수 있게 string으로 인코딩<G>이 적절히 되었나 체크
       <G> = (1,2,3,4)((1,2),(2,3),(3,1),(1,4))
       (1,2,3,4)는 전부 다른 10진수인가? (이걸 노드 집합 V로 둔다)
       (1,2)는 V^2에 있는 원소인가?
    2. stage 1: TM은 1번째 노드에 .을 찍는다
    3. stage 2: 노드 목록 V에서 점이 찍히지 않은 노드를 찾아 _를 긋고, 점이 찍힌 노드에도 _을 긋는다.
    4. stage 3: (1,2),(2,3),(3,1),(1,4)에서 _이 그어진 노드 사이에 간선이 있는지 찾고
       만약 있다면, _에 모두 .을 찍고 해당 간선은 X표하고 _을 모두 제거 후 stage 2로 돌아감
       만약 없다면 다음 노드에 _이동
    5. 만약 더 이상 간선이 없는데 모든 V의 원소에 .이 찍히지 않았다면,
       unconnected graph이다.
  • TM 수준
    개복잡해서 생략함...