쌀 정리

Rice 정리는 Turing 기계가 인식하는 언어의 중요하지 않은 의미 론적 속성은 결정할 수 없다고 말합니다. 속성 P는 해당 속성을 충족하는 모든 튜링 머신의 언어입니다.

공식적인 정의

P가 중요하지 않은 속성이고 속성을 포함하는 언어 L p 가 Turing 기계 M에서 인식되면 L p = {<M> | L (M) ∈ P}는 결정할 수 없습니다.

설명 및 속성

  • 언어의 속성 P는 단순히 언어의 집합입니다. 어떤 언어가 P (L ∈ P)에 속하면 L은 속성 P를 만족한다고합니다.

  • 재귀 적으로 열거 가능한 언어에 의해 충족되지 않거나 모든 재귀 적으로 열거 가능한 언어에 의해 충족되는 경우 속성은 사소한 것으로 호출됩니다.

  • 사소하지 않은 속성은 일부 재귀 적으로 열거 가능한 언어에 의해 충족되고 다른 언어에서는 충족되지 않습니다. 공식적으로 말하면, L ∈ P 인 사소하지 않은 속성에서 다음 두 속성이 모두 유지됩니다.

    • Property 1 − (<M1>, <M2> ∈ L) 또는 (<M1>, <M2> ∉ L) 같은 언어를 인식하는 Turing Machines, M1 및 M2가 있습니다.

    • Property 2 − Turing Machines M1 및 M2가 있습니다. 여기서 M1은 언어를 인식하고 M2는 인식하지 않습니다. 즉 <M1> ∈ L 및 <M2> ∉ L

증명

속성 P가 중요하지 않고 φ ∈ P라고 가정합니다.

P는 사소하지 않기 때문에 적어도 하나의 언어는 P, 즉 L (M 0 ) ∈ P, ∋ Turing Machine M 0을 충족 합니다.

w는 특정 순간의 입력이고 N은 다음과 같은 Turing Machine입니다.

입력 x

  • w에서 M 실행
  • M이 수락하지 않거나 중단하지 않으면 x를 수락하지 않거나 중단하지 않습니다.
  • M이 w를 받아들이면 x 에서 M 0 을 실행 합니다. M 0 이 x를 받아들이면 x를 받아들입니다.

인스턴스를 매핑하는 함수 ATM = {<M, w> | M은 입력 w}를 N으로 받아

  • M이 w를 받아들이고 N이 M 0 과 같은 언어를 받아들이면 L (M) = L (M 0 ) ∈ p
  • M이 w를 받아들이지 않고 N이 φ를 받아들이면 L (N) = φ ∉ p

A TM 은 결정할 수없고 Lp로 줄일 수 있기 때문에 Lp도 결정할 수 없습니다.