Decider(튜어링 머신)

Decider (Turing machine)

계산 가능성 이론에서, 결정자는 모든 [1]입력에 대해 멈추는 튜링 기계이다.결정자는 전체 함수를 나타내기 때문에 전체 튜링[2] 기계라고도 불립니다.

항상 정지하기 때문에 이러한 기계는 주어진 문자열이 정식 언어의 구성원인지 여부를 판단할 수 있습니다.이러한 기계에 의해 결정될 수 있는 언어의 클래스는 재귀 언어의 집합입니다.

임의의 튜링 기계가 주어졌을 때, 그것이 결정자인지 아닌지를 결정하는 것은 결정할 수 없는 문제이다.이것은 튜링 기계가 특정 입력에 정지하는지 여부를 묻는 정지 문제의 변형입니다.

전체 튜링 기계로 계산 가능한 함수

실제로, 많은 관심 함수는 항상 정지하는 기계로 계산할 수 있습니다.특정 입력에 유한 메모리만 사용하는 머신은 플로우 제어 기능을 제한하여 입력마다 강제로 정지시킬 수 있으며, 이로 인해 어떤 입력도 머신을 무한 루프 상태로 만들 수 없습니다.간단한 예로, 최종적인 의사결정 트리를 구현하는 기계는 항상 정지합니다.

단, 기계에 루프 기능이 완전히 없는 것은 아닙니다.루프를 예측 가능한 유한 크기(BASIC의 FOR 루프 등)로 제한하면 모든 원시 재귀 함수를 표현할 수 있습니다(Meyer 및 Ritchie, 1967).이러한 기계의 예는 Brainerd 및 Landweber(1974)의 완구 프로그래밍 언어 PL-{GOTO}에 의해 제공된다.

한층 더 고도의 기능을 항상 정지시킬 수 있는 프로그래밍 언어를 정의할 수 있습니다.예를 들어, 원시 재귀가 아닌 Ackermann 함수는 그럼에도 불구하고 그 인수에 대한 축소 순서를 가진 용어 개서 시스템에 의해 계산 가능한 총 계산 가능 함수이다(Ohlebusch, 2002, 페이지 67).

프로그램의 종료를 보장하는 위의 프로그래밍 언어의 예에도 불구하고, 정확히 전체 재귀 함수, 즉 항상 정지하는 튜링 기계에 의해 계산될 수 있는 함수를 포착하는 프로그래밍 언어는 존재하지 않는다.왜냐하면 그러한 프로그래밍 언어의 존재는 튜링 기계가 모든 입력에 정지하는지의 문제의 반감소성과는 모순될 것이기 때문이다.

부분 튜링 기계와의 관계

일반적인 튜링 기계는 부분 함수를 계산할 것이다.부분 튜링 기계와 전체 튜링 기계 사이의 관계에 대해 두 가지 질문을 할 수 있습니다.

  1. 부분 튜링 기계에 의해 계산될 수 있는 모든 부분 함수는 확장될 수 있는가? (즉, 그것의 영역이 확대되는) 완전한 계산 가능한 함수가 될 수 있는가?
  2. 튜링 기계의 정의를 변경하여 전체 튜링 기계의 특정 클래스, 모든 계산 가능한 함수를 계산하는 것이 가능한가?

이 질문들에 대한 답변은 모두 "아니오"입니다.

다음 정리는 항상 정지하는 기계에 의해 계산 가능한 함수가 모든 부분 계산 가능 함수의 확장을 포함하지 않는다는 것을 보여주며, 이는 위의 첫 번째 질문이 부정적인 답을 가지고 있음을 의미한다.이 사실은 정지 문제의 알고리즘적 해결 불가능성과 밀접하게 관련되어 있습니다.

정리 - 전체 튜링 계산 가능 함수로 확장되지 않은 튜링 계산 가능 부분 함수가 있습니다.특히, 부분 함수 f는 지수 n을 가진 튜링 기계가 출력 m을 가진 입력 0에 정지하는 경우에만 f(n) = m이 되도록 정의되었다.

실제로, 만약 g가 f를 확장하는 전체 계산 가능 함수라면, g는 몇몇 튜링 기계에 의해 계산될 것이다; 그러한 기계의 색인으로서 e를 고정하라.Kleene의 재귀 정리를 사용하여 튜링 기계 M을 구축합니다. 이 정리는 입력 0에서 M의 인덱스M n에서 실행되는 인덱스 e로 기계를 시뮬레이션합니다(따라서 머신 M은 스스로 인덱스를 생성할 수 있습니다. 이것이 재귀 정리의 역할입니다).가정에 따르면, 이 시뮬레이션은 결국 답을 반환합니다.g(nM) = m이면 M반환값m + m)이 M을 정의합니다[clarify].따라서 입력 0에서 M의 진정한 반환값인 f(nM)는 g(nM)와 같지 않습니다.따라서 g는 f를 확장하지 않는다.

두 번째 질문은 본질적으로 전체 함수만 계산하고 전체 계산 가능한 함수를 계산하는 또 다른 합리적인 계산 모델이 있는지 여부를 묻습니다.비공식적으로, 만약 그러한 모델이 존재한다면, 각각의 컴퓨터는 튜링 기계에 의해 시뮬레이션 될 수 있었다.따라서 이 새로운 계산 모델이 기계의 ,, {{ 구성되어 있는 경우, 모든 튜링 기계와 총계 함수를 계산하는 시퀀스 \ \ 재귀적으로 열거됩니다.함수는 기계i T 중 하나로 계산할 수 있습니다.입력 i에서 기계 T가 (i) + ( \ ( i ) + 1 ,하도록 기계 T 가 구성될 수 있기 때문에 이것은 불가능합니다.이 기계는 목록의 어떤 기계 T 와도 동등할 수 없습니다.인덱스 j 의 리스트에 있다고 가정해 주세요. j ( ) j () + { )= 정수 결과를 반환하지 않습니다.따라서 전체일 수는 없지만 구성별 함수는 전체여야 한다(전체 함수가 재귀적으로 열거될 수 있는 경우 이 함수는 구성될 수 있다). 이는 모순입니다.이것은 두 번째 질문의 답이 부정적이라는 것을 보여준다.

전체 튜링 기계의 색인 집합

지수 e를 가진 튜링 기계가 모든 입력에서 정지할 것인지의 결정 문제는 결정되지 않는다.실제로 이 문제는 산술 계층의 레벨 0 _ 있습니다.따라서 이 문제는 인덱스가 e인 머신이 입력0으로 정지할지를 묻는 Susping 문제보다 엄밀하게 더 어렵습니다.직관적으로 이러한 해결 불가능성의 차이는 "전체 머신" 문제의 각 인스턴스가 중단 문제의 인스턴스를 무한히 많이 나타내기 때문입니다.

프로바이더하기

튜링 기계가 전체인지 여부뿐만 아니라 1차 페아노 산술과 같은 특정 논리 시스템에서 이것이 증명될 수 있는지에 대해서도 관심을 가질 수 있다.

방음 시스템에서, 모든 가능한 전체 튜링 기계는 실제로 전체이지만, 그 반대가 사실이 아니다: 비공식적으로, 충분히 강한 모든 1차 증명 시스템에 대해, 시스템이 일관되지 않는 한 전체라고 가정되지만 그렇게 증명될 수 없는 튜링 기계가 있다.증명하다)이들의 전체성에 대한 증거는 몇 가지 가정에 기초하거나 다른 증명 시스템을 필요로 한다.

따라서, 증명 시스템의 모든 증거를 열거할 수 있으므로, 처음 n개의 증명을 거쳐 모순을 찾는 입력 n에 튜링 기계를 구축할 수 있다.1개가 발견되면 무한 루프 상태가 되어 정지하지 않습니다.그렇지 않으면 정지합니다.만약 시스템이 일관된다면, 튜링 기계는 모든 입력에서 정지할 것이지만, 괴델의 불완전성 이론으로 인해 충분히 강력한 증명 체계에서는 이것을 증명할 수 없다.

또한 증명 시스템이 일관성이 없는 경우에만 정지하는 튜링 기계를 만들 수 있으며, 따라서 일관성 있는 시스템에 대해서는 전체적이지 않지만 그러한 것을 증명할 수 없다.이것은 입력에 관계없이 모든 증거를 열거하고 모순에 멈추는 튜링 기계입니다.

굿스타인 시퀀스를 거쳐 0으로 정지하는 튜링 기계는 총합이지만 페아노 산술에서는 그렇게 증명될 수 없다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Sipser, 1996[page needed]
  2. ^ 코젠, 1997년[page needed]