설명번호

Description number

기술번호는 튜링머신 이론에서 발생하는 숫자다.괴델 숫자와 매우 유사하며, 문헌상으로는 때때로 괴델 숫자라고도 불린다.어떤 범용 튜링 기계에 주어진다면, 모든 튜링 기계는 그 기계에 인코딩된 번호를 부여받을 수 있다.이것은 기계의 설명 번호다.이 숫자들은 중단 문제의 불분명함에 대한 앨런 튜링의 입증에 핵심적인 역할을 하며, 튜링 기계에 대한 추론에도 매우 유용하다.

설명 번호의 예

상태1 q, ... qR, 기호가1 있는 테이프 알파벳, ... sm, s0, 그리고 현재 상태, 전류 기호 및 동작을 수행하는 전환(현재 테이프 기호를 덮어쓰고 테이프 헤드를 왼쪽 또는 오른쪽으로 이동하거나 전혀 이동하지 않는 것일 수 있음)과 다음 상태가 포함된 튜링 기계 M을 사용했다고 가정해 보십시오.앨런 튜링에 의해 기술된 원래의 범용 기계 아래에서 이 기계는 다음과 같이 입력으로 암호화될 것이다.

  1. 상태 q는i 문자 'D'에 이어 문자 'A'를 반복하여 인코딩된다(단일 인코딩).
  2. 테이프 기호 s는j 문자 'D'에 이어 문자 'C'가 반복 j번으로 인코딩된다.
  3. 전환은 상태, 입력 기호, 테이프에 쓸 기호, 이동할 방향(좌, 우, 무이동 시 'L', 'R' 또는 'N'이라는 문자로 표시됨)을 주고, 진입할 다음 상태를 주어 암호화되며, 위와 같이 상태와 기호가 인코딩된다.

따라서 UTM의 입력은 세미콜론으로 구분된 전환으로 구성되므로 입력 알파벳은 'D', 'A', 'C', 'L', 'R', 'N', ';'의 7개 기호로 구성된다.예를 들어 테이프에 0과 1을 영구적으로 인쇄하는 매우 간단한 튜링 기계의 경우:

  1. 상태: q1, 입력 기호: 공백, 동작: 인쇄 1, 오른쪽 이동, 다음 상태: q2
  2. 상태: q2, 입력 기호: 공백, 동작: 인쇄 0, 오른쪽 이동, 다음 상태: q1

빈칸을 s0, '0'은 s1, '1'은 s로2 하고, 기계는 UTM에 의해 다음과 같이 인코딩된다.

DADDCCRDAA;DADDCRDA;

그러나 7개의 기호 'A'를 1로, 'C'를 2로, 'D'를 3으로, 'L'을 4로, 'R'을 5로, 'N'을 6으로, '; 7'을 각각 교체하면 튜링 머신의 인코딩을 자연적인 숫자로 할 수 있을 것이다: 튜링 아래의 튜링 머신의 설명 번호다.따라서 위에서 설명한 간단한 튜링 기계는 설명 번호 313322531173113325317을 갖게 된다.모든 다른 유형의 범용 튜링 기계에는 유사한 과정이 있다.일반적으로 이러한 방법으로 설명 번호를 실제로 계산할 필요는 없다. 요점은 많은 자연 숫자가 튜링 기계에 대한 코드가 아닐 수도 있지만(또는 다른 방법으로 말하면 상태가 없는 튜링 기계를 나타냄) 대부분의 튜링 기계에 대한 코드로 해석될 수 있다는 것이다.튜링 기계에는 항상 그러한 숫자가 존재한다는 사실이 일반적으로 중요하다.

확인 불가능한 증명에 대한 적용

설명번호는 많은 불분명한 증거에서 중요한 역할을 한다. 예를 들어, 중단되는 문제가 불분명한 것이라는 증거와 같이 말이다.애당초 자연수와 튜링 기계 사이에 이 직접적인 대응의 존재는 모든 튜링 기계들의 집합은 폄하할 수 없으며, 모든 부분 기능의 집합은 헤아릴 수 없이 무한하므로 튜링 기계에 의해 계산될 수 없는 많은 기능이 분명히 있어야 한다.

칸토어의 대각선 주장과 유사한 기법을 사용함으로써, 예를 들어, 특히 정지 문제가 불가해하다는 것과 같은, 그러한 논박할 수 없는 함수를 나타낼 수 있다.첫째, U(e, x)에 의해 설명 번호 e와 입력 x가 주어진 범용 튜링 기계의 동작을 나타내고, e가 유효한 튜링 기계의 설명 번호가 아닌 경우 0을 반환한다.이제 정지 문제를 해결할 수 있는 알고리즘이 있다고 가정하면, 예를 들어 튜링 기계가 모든 입력에서 정지하면 1이 반환되는 튜링 머신 TEST(e)가 있고, 튜링 머신이 영구적으로 실행되도록 하는 일부 입력이 있을 경우 0이 반환되는 튜링 머신 TEST(e)가 있다.이들 기계의 출력을 조합하면 TEST(k)가 1이면 U(k, k) + 1을 반환하는 또 다른 기계 Δ(k)를, TEST(k)가 0이면 0을 반환하는 기계 Δ(k)를 구축할 수 있어야 한다.이 정의로부터 Δ는 모든 입력에 대해 정의되며 자연적으로 총 재귀적이어야 한다.우리가 추측한 튜링 기계 역시 Δ라고 하기 때문에 그것 역시 설명 번호를 가지고 있어야 한다, e라고 부른다.따라서 우리는 기술 번호 e를 다시 UTM에 공급할 수 있고, 정의상 Δ(k) = U(e, k), 즉 Δ(e) = U(e, e)를 공급할 수 있다.그러나 TEST(e)는 1이므로, 우리의 다른 정의에 따르면 Δ(e) = U(e) + 1로, 모순을 초래한다.따라서, TEST(e)는 존재할 수 없으며, 이러한 방식으로 우리는 중지 문제를 불문하고 해결할 수 없는 것으로 해결했다.

참고 항목

참조

  • John Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-44124-1. (신데렐라 책)
  • Turing, A. M. "Entscheidungsproroblem에 대한 응용 프로그램과 함께 계산 가능한 숫자로" Proc.Roy. Soc. London, 2(42), 1936, 페이지 230–265.