[계산이론](22)[undeciablity]

undeciablity

몇몇 문제들은 알고리즘적으로 풀지 못한다(algorithmically unsolvable)

undecidable

문제에 대응되는 decider가 존재하지 않는 language

 

A_TM

$A_{TM}$: 어떤 turning machine(TM)과 string(w)가 주어졌을 때, 이 TM이 w를 accept할 지 판정하는 문제
    $A_{TM}$ = {<M, w> | M is turning machine that accepts input string w}
인코딩된 문자열이 주어졌을 때

1. TM 내부에서 w가 주어졌을 때 M을 시뮬레이션 한다
   내부 state, 현재 input char 등을 tape에 가록해가며 하면 된다.
2. 만약 M이 accept하면 TM도 accept, reject하면 reject한다
   근데 M이 loop에 갇힌다면? 이걸 어떻게 reject할 수 있을까?

 

halting problem

다음과 같은 TM인 $TM_{HALT}$가 decider로 존재하는가?
$TM_{HALT}$ = {<M, w> | M is TM and M halts on input w}
    즉, TM_HALT는 M에 w를 넣었을 때 accept or reject에 간다면 accept를,
    아니라면 reject를 뱉는 TM이다

이떄 A_TM과 halting problem은 서로 필요충분조건이다.

• halt -> A_TM
  만약 TM_HALT H를 가지고 있다면,
  A_TM을 input <M, w>에 대해
      1. 먼저 H에서 멈추지 않는 경우를 모두 reject한다
      2. 그 다음 <M, w>를 시뮬레이션 해서 accept, reject를 판정한다 
  이와 같은 방식으로 만들 수 있으므로, H가 존재하면 A_TM도 존재한다.
• A_TM -> halt
  만약 A_TM S를 가지고 있다면,
  TM_HALT를 input <M, w>에 대해
      1. M이 accept or reject로 갈 때 억지로 accept로 가게 M'로 개조
      2. S에 M'을 넣어 accept하면 원본 M은 accept or reject로 멈추는 것이고, 만약 accept를 안하면 loop에 빠진 것이라 판단하면 된다.
  이와 같은 방식으로 TM_HALT를 만들 수 있으므로, S가 존재하면 TM_HALT도 존재한다.

따라서 halting problem을 증명하는 것은 A_TM을 증명하는 것이고,
A_TM을 증명하는 것은 halting problem을 증명하는 것이다.

 

halting problem의 증명

<M, w>가 주어질 때 정지하는지 판정하는 TM H가 존재한다고 가정하자.

• H(M, w)
  accept: M이 w를 받았을 때 정지 (accept, reject)
  reject: M이 w를 받았을 때 정지 안함 (loop)

그리고 내부에서 H를 호출하는 T를 하나 생각해보자
이건 string s를 입력으로 받아 H를 돌려보고 reject일 때만 멈춘다.

• T(s)
  accept: H(s, s) == reject
  loop: H(s, s) != reject

이제 T(T, T)를 돌려보고 결과를 가정하고 살펴보자.

• 가정 1: T가 halt한다
  T는 H(T, T) == reject일 때만 멈춘다.
  H(T, T)가 reject이려면 T가 loop여야 한다.
  그러나 맨 처음 T가 halt한다고 가정했으므로, 모순
  -> T는 halt하지 않는다.
• 가정 2: T가 halt하지 않는다
  T는 H(T, T) != reject일 때만 멈추지 않는다
      즉, H(T, T) == accept
  H(T, T)가 accept이려면 T가 halt여야 한다.
  그러나 맨 처음 T가 halt하지 않는다고 가정했으므로, 모순
  -> T는 halt해야 한다.

-> 즉, 모든 경우에서 모순이므로, T는 결정할 수 없다.
(decider로 H가 존재하지 않는다.)

참고) decider로의 H는 존재하지 않으나, recognizer로서의 H는 충분히 존재한다.

• H(M, w) (recognizer)
  accept: M이 w를 받았을 때 정지 (accept, reject)
  loop: M이 w를 받았을 때 정지 안함 (loop)