결정자

계산가능성 이론에서, 결정자(結定者, )는 모든 입력에 대해 정지하는 튜링 기계이다.Sipser, 1996 결정자는 완전 정의 함수에 대응하므로 완전 튜링 기계()라고도 한다.Kozen, 1997

결정자는 반드시 정지하므로, 어떤 문자열이 특정한 형식 언어에 속하는지 결정할 수 있다. 결정자로 결정할 수 있는 언어를 재귀 언어라고 한다.

주어진 튜링 기계가 결정자인가 하는 문제는 결정불가능하다. 이 문제는 주어진 튜링 기계가 특정 입력에 대해 정지하는지를 묻는 정지 문제의 한 변형이다.

 결정자로 계산 가능한 함수 

실생활에서 유용한 많은 함수는 반드시 정지하는 기계로 계산할 수 있다. 어떤 입력이 주어지든 유한한 메모리만 사용하는 기계의 경우, 제어 흐름을 제약하여 무한 루프에 빠질 수 없게 하면 모든 입력에 대해 정지하게 만들 수 있다. 자명한 예로, 유한한 결정 트리를 구현하는 기계는 반드시 정지한다.

그러나 기계가 반드시 정지함을 보장하기 위해서 루프(반복문)를 완전히 제거해야 하는 것은 아니다. (BASIC의 FOR 루프처럼) 루프를 유한 번만 반복할 수 있도록 제한하면 모든 원시 재귀 함수를 계산할 수 있다.Meyer and Ritchie, 1967 그러한 기계의 예로 Brainerd and Landweber (1974)의 모형 프로그래밍 언어 PL-{GOTO}가 있다.

이보다 더 복잡한 함수를 계산할 수 있으면서 반드시 정지하는 프로그래밍 언어도 만들 수 있다. 예를 들어 아커만 함수는 원시 재귀 함수는 아니지만, 정렬순서를 따르는 재작성 체계로 계산할 수 있는 완전 계산 가능 함수이다.Ohlebusch, 2002, pp. 67

위와 같이 프로그램이 반드시 정지함을 보장하는 프로그래밍 언어들을 만들 수 있기는 하지만, 모든 완전 재귀 함수의 집합, 즉 반드시 정지하는 모든 튜링 기계의 집합에 정확히 대응하는 프로그래밍 언어는 존재하지 않는다. 주어진 튜링 기계가 모든 입력에 대해 정지하는가 하는 문제는 준결정가능(semidecidable)하지 않기 때문이다. 즉, 주어진 튜링 기계가 결정자라고 해도 유한 시간 안에 그 기계가 결정자임을 알아내는 알고리즘은 존재하지 않는다.

 부분 튜링 기계와의 관계 
일반적인 튜링 기계는 부분 정의 함수를 계산한다. 부분 튜링 기계와 완전 튜링 기계의 관계에 관하여 두 가지 질문을 던질 수 있다.
 부분 튜링 기계로 계산되는 부분 정의 함수의 정의역을 확장하여 완전 계산 가능 함수로 만들 수 있음이 보장되는가?
 튜링 기계의 정의를 바꾸어, 모든 완전 계산 가능 함수를 계산할 수 있는 특정한 완전 튜링 기계의 부류를 찾을 수 있는가?
두 질문의 답은 모두 '아니오'이다.

다음 정리는 결정자로 계산되는 함수의 집합이 모든 부분 계산 가능 함수의 확장을 포함하지 않음을 보여준다. 이는 정지 문제의 결정불가능성과 밀접한 관련이 있다.

두 번째 질문은 오직 완전 정의 함수만을 계산하고 모든 완전 계산 가능 함수를 계산할 수 있는 계산 모형이 존재하는가 하는 질문이다. 만약 그런 모형이 존재한다면, 그에 속한 기계 각각은 튜링 기계로 모사할 수 있을 것이다. 따라서 이 새로운 계산 모형에 속한 기계들을 라 하면, 완전 튜링 기계의 재귀 열거 수열 이 존재하여, 임의의 완전 계산 가능 함수에 대해 어떤 가 그 함수를 계산할 수 있을 것이다. 그러나 대각선 논법에 의해 그러한 수열은 존재할 수 없다. 그러한 수열이 있다고 하면, 를 입력받아 을 출력하는 튜링 기계 를 만들 수 있다. 이 기계는 정의상 완전 튜링 기계이므로, 어떤 에 대하여 여야 한다. 그러면 이므로, 는 정수 값을 출력할 수 없어 는 완전 튜링 기계가 아니다. 이는 모순이다. 따라서 두 번째 질문에 대한 답은 부정적이다.

 완전 튜링 기계의 번호의 집합 

번호 인 튜링 기계가 모든 입력에 대해 정지하는가 하는 결정 문제는 결정불가능하다. 이 문제는 산술 위계에서 에 위치한다. 따라서 이 문제는 번호 인 튜링 기계가 입력 0에 대해 정지하는가 하는 정지 문제보다 더 어려운 문제이다. 직관적으로 말해, 이는 하나의 '완전 튜링 기계' 문제가 무한히 많은 정지 문제를 포함하기 때문이다.

 증명가능성 
어느 튜링 기계가 반드시 정지하는지의 문제를 넘어, 그 사실을 1차 페아노 공리계 등 특정한 논리 체계에서 증명할 수 있는가 하는 문제를 생각할 수 있다.

건전한 증명 체계에서, 반드시 정지함을 증명할 수 있는 튜링 기계는 반드시 정지하지만, 그 역은 성립하지 않는다. 페아노 산술을 포함할 만큼 충분히 강하며 무모순인 1차 증명 체계에서는, 반드시 정지하지만 그 사실을 증명할 수 없는 튜링 기계들이 존재한다. 그러한 기계가 반드시 정지한다는 증명은 추가적인 가정을 요하거나 다른 증명 체계를 필요로 한다.

주어진 증명 체계의 모든 증명에 번호를 붙여 열거할 수 있으므로, 을 입력받으면 첫 개의 증명을 살펴보고 그 안에 모순이 있는지 검토하는 튜링 기계를 만들 수 있다. 모순이 있으면 무한 루프에 빠져서 정지하지 않고, 모순이 없으면 정지하도록 하는 것이다. 주어진 체계가 무모순이라면, 그러한 튜링 기계는 모든 입력에 대해 정지하지만, 충분히 강한 체계라면 괴델의 불완전성 정리 때문에 그 사실을 증명할 수는 없다.

반대로 증명 체계의 모순을 발견하면 정지하는 튜링 기계도 만들 수 있다. 이 기계는 주어진 체계가 무모순이라면 부분 튜링 기계가 되지만, 그 사실을 증명할 수는 없다.

굿스타인 수열의 각 항을 계산하다가 0이 나오면 정지하는 튜링 기계는 완전 튜링 기계이지만 페아노 공리계 안에서는 이를 증명할 수 없다.

 각주 


 참고 문헌 
 Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
 Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.
 Sipser, M. (2006), Introduction to the Theory of Computation, PWS Publishing Co.
 Kozen, D.C. (1997), Automata and Computability, Springer.
 Ohlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer.

 같이 보기 
 완전 함수형 프로그래밍
 정지 분석

분류:튜링 기계