임의의
TuringMachine과 그에 대한 어떤 입력에 대해 그 결과로 다음의 두 가지만이 예측됨을 쉽게 이해할 수 있다.
- 언젠가 계산을 멈춘다.
- 안 멈추고 영원히 계산한다.
이런 두 가지 상황에 대해서, 정지문제란 '이렇게 어떤 특정한 기계 M과 입력 I의 쌍 (M, I)가 주어졌을 때에 이 계산이 유한한 시간 내에 정지되겠는가?'를 말한다.
이 문제를 푸는 기계를 함수 H(M, I)라고 표시해보자. 이 기계는 입력으로 M과 I를 받아서 M에 I를 넣었을 때, 즉, M에 input I를 넣었을 때, M이 유한한 시간 내에 정지할지 정지하지 않을지를 유한한 시간 안에 결정해 준다. 그러나 결론적으로 이러한 기계 H는 존재하지 않는다:
만일 그러한 H가 존재한다고 하자. 즉, M이 I를 인풋으로 해서 무한루프를 돌면 YES, 무한루프를 돌지 않으면 NO를 출력으로 한다. 즉,
procedure H(procedure M, input I){
if( M(I) loops infinite) return YES;
else NO
}
이제 청개구리 함수 K(P)를 만들어보자. 이게 모순을 이끌어내는 핵심이다. 즉, 자신을 입력으로 받는 함수 P를 입력으로 삼는 함수이며, H(P,P)의 반대로 작동한다. 즉, H(P,P)가 YES면 K(P)는 유한한 시간 내에 끝나고, H(P,P)가 NO면, 무한루프를 돈다. 이러한 K(P)는 H가 존재한다는 가정하게 간단히 다음과 같이 짤 수 있을 것이다.
procedure K(procedure P){
if(H(P,P) is YES) return;
else while(1);
}
이번에는 H(K,K)에 대해서 생각해보자.
1. 답이 YES 라고 해보자. H의 정의에 의해 K(K)는 무한루프를 돌아야 한다. 그러나 K의 정의에 의해 H(K,K)가 YES이므로 K(K)는 유한한 시간 내에 끝나야 한다. --> 모순
2. 답이 NO라고 해보자. H의 정의에 의해 K(K)는 유한한 시간 내에 끝나야 한다. 그러나 K의 정의에 의해 H(K,K)가 NO이므로 K(K)는 무한루프를 돌아야 한다. --> 모순
따라서, 이와같은 H가 존재한다는 가정이 잘못되었음을 알 수 있으며, 이 문제는 undecidable problem으로 분류된다. --
naya
TuringMachine.html TuringTest
