[오토마타] 15. 결정 가능한 문제(Decidable Problem)

":)" 문제가 있다고 생각해보자. ":)" 문제는 어떤 프로그램이 :)를 출력하는지 아닌지를 확인하는 문제다. 결론부터 말하자면, 컴퓨터는 이 단순한 문제를 항상 해결하지 못한다.

 

만약 이런 프로그램이 입력으로 들어온다면 문제의 정답을 "yes"라는걸 쉽게 알 수 있다.

int main() {
 printf(":)");
}

하지만, 이런 문제라면 어떨까? 코드의 내용을 간단히 요약하자면, n을 입력받고, 가능한 모든 정수쌍 (x,y,z)를 순회하면서 $x^n+y^n=z^n$가 성립하면 ":)"를 출력하는 코드다. 가령 $n=2$라면, $3^2+4^2=5^2$에서 ":)"가 출력될 가능성이 있다.

int main() {
  int n, tot, x, y;
  scanf("%d", &n);

  while(1) {
    for(x=1; x<tot-2; x++) {
      for(y=1; y<tot-x-1; y++) {
        z = tot-x-y;
        if(pow(x,n)+pow(y,n) == pow(z,n) printf(":)");
      }
    }
  }
}

 참고로 위 코드에 사용된 $x^n+y^n=z^n$은 페르마의 마지막 정리에 등장하는 식이며, $n \ge 3$인 경우, 만족하는 x,y,z 정수해가 존재하지 않는다는 것이 증명되었다. 즉, 우리는 수학적인 증명을 통해 :)를 출력하지 않는다는 것을 알고 있다. 하지만 컴퓨터는 위 코드가 :)를 출력할지 않을지 알 수 없다. 코드는 무한히 실행되고, 컴퓨터는 기다리면 :)가 나올지를 목빠져라 기다릴 뿐이다.

 

결정 가능한 문제(Decidable Problem)

":)" 문제와 같은 문제를 결정 불가능한 문제(Undecidable Problem)라고 부른다. 모든 입력에 대해 유한시간 내에 "yes"나 "no"로 답할 수 없는 문제기 때문이다. 반대로 유한시간 내에 모든 입력에 대해서 "yes"나 "no"를 결정할 수 있으면 결정 가능한 문제(Decidable Problem)라고 한다. 이런 예시를 들 수 있다.

 

결정 가능한 문제

- 이 사람은 성인인가?

- 주어진 정수가 소수인가?

- 주어진 문자열의 길이가 5 이상인가?

 

결정 불가능한 문제

- 앞서 우리가 예로 든 ":)" 문제

- 정지문제(Halting Problem): 주어진 프로그램이 종료하는가?

- 문법 모호성: 주어진 문법이 모호한가?

- 프로그램 등가성: 두 프로그램이 같은 결과를 내는가?

 

":)" 문제의 결정 불가능함에 대한 증명

":)" 문제는 정말 결정 불가능할까? 어떤 프로그램 P와 어떤 입력 I가 주어졌을 때 ":)"를 출력하는지 하지 않는지를 판단하는 ":) 테스터"가 존재한다면, :) 문제는 결정 가능할것이다. 하지만, 우리는 :) 테스터가 존재한다고 가정하면 모순이 발생함을 보여서(귀류법), :) 테스터는 존재할 수 없고, :) 문제는 결정 불가능하다는 것을 증명할 수 있다.

 

프로그램 $H$의 스펙은 아래와 같다.

프로그램 $H$
입력: 프로그램 $P$와 입력 $I$
출력: $P(I)$를 시뮬레이션하고, ":)"가 출력되면 "yes" 출력, 출력되지 않으면 "no" 출력
출력 종류: "yes" or "no"

 

프로그램 $H$를 이용하여 구현한 프로그램 $H_1$의 스펙은 다음과 같다.

프로그램 $H_1$
입력: 프로그램 $P$와 입력 $I$
출력: $H(P,I)$를 시뮬레이션하고, "yes"가 출력되면 똑같이 "yes" 출력, "no"가 출력되면 ":)"를 출력
출력 종류: "yes" or ":)"

 

이번엔 프로그램 $H_2$를 정의한다.

프로그램 $H_2$
입력: 프로그램 $P$ (입력 I를 받지 않음)
출력: $H_1(P,P)$를 시뮬레이션해서, 결과를 그대로 출력
출력 종류: "yes" or ":)"

 

그러면 우리는 $H_2(H_2)$를 실행할 때 모순을 발견할 수 있고, 그래서 프로그램 $H_2$는 존재하지 않고, 그로 인해 프로그램 $H_1$도 존재하지 않고, 그로 인해 프로그램 $H$도 존재하지 않는다는 결론이다. 그래서 ":) 문제"는 결정 불가능하다. 왜 $H_2(H_2)$가 모순인지는 아래와 같다.

 

프로그램 $H_2$은 "yes" 아니면 ":)"를 출력한다.
프로그램 $H_2$는 $P$가 자신을 입력을 받았을 때($P(P)$) ":)"가 출력되면 "yes", 출력되지 않으면 ":)"를 출력하는 프로그램이다.
$H_2(H_2)$는 $H_2$가 자신을 입력을 받았을 때($P(P)$) ":)"가 출력되면 "yes", 출력되지 않으면 ":)"를 출력하는 프로그램이다.

- 만약 $H_2(H_2)$가 "yes"를 출력한다면, $H_2$가 자신을 입력받아 ":)"를 출력했다는 것을 의미한다. 모순이다.
- 만약 $H_2(H_2)$가 ":)"를 출력한다면, $H_2$가 자신을 입력받아 ":)"를 출력하지 못했다는 뜻이다. 모순이다.

 

여기까지가 ":)" 문제가 결정불가능함을 보이는 증명이다. 앞서 예로 등장한 정지 문제(Halting Problem)도 이런식으로 증명할 수 있는데, 좋은 영상과 설명이 있어 공유한다. 여기

 

환원(reduction)

":)"문제가 결정 불가능하다는 것은 알았다. 다른 결정불가능한 문제들도 위 방법대로 직접 증명을 할 수도 있다. 하지만 이미 ":)" 문제가 결정 불가능하다는 것을 우리는 알고 있으니, 이 점을 이용하면 더 간단하게 증명할 수 있다. 환원(Reduction)을 이용한다.

 

1. 새로운 문제 P에 대해 유한시간 내에 yes/no를 답하는 프로그램 Q이 있다고 가정
2. 프로그램 Q를 이용하면 ":)"문제도 유한시간 내에 yes/no를 답할 수 있다고 증명
3. 그런데 ":)"문제는 결정 불가능하다는 것을 알고 있으므로 모순 발생
4. 따라서, 새로운 문제 P를 해결하는 프로그램 Q는 존재하지 않음. 즉, P도 결정 불가능함.

 

위 과정을 'P를 ":)"문제로 환원'했다고 한다.

 

"Smile 호출" 문제를 정의해보자. "Smile 호출" 문제는 "어떤 프로그램이 'Smile'이라는 함수를 호출하는가?" 에 답하는 문제다.

1. 만약 이 문제를 해결하는 테스터가 있다고 가정해보자.
2. ":)" 문제 테스터가 판단하기 어려워하고 있는 프로그램 X가 있다고 생각하자. Smile 호출 문제 테스터에게 이런 프로그램을 만들어서 떠넘긴다: "X가 :)를 출력하면 Smile을 호출하고, 아니면 호출하지 않는 프로그램"
3. 그런데 ":)" 문제는 결정 불가능하므로, 2. 의 프로그램을 해결할 수 있는 Smile 호출 문제 테스터는 존재하지 않는다.

 

쉽게 말하면, ":)" 문제 테스터가 Smile 호출 문제 테스터를 걸고 넘어지면 되는거다. :) 문제 테스터는 Smile 테스터에게 이렇게 말하고 있다. "내가 못 풀고 있는 이 문제를 너가 풀 수 있었다면, 너도 결정 가능한거고 나도 결정 가능하다고 했을거야! 그런데 너가 못풀었으니까 나도 어쩔수 없이 결정 불가능한거야!"