쌀 정리
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도 결정할 수 없습니다.