Twierdzenie o ryżu

Twierdzenie Rice'a stwierdza, że ​​każda nietrywialna semantyczna właściwość języka, który jest rozpoznawany przez maszynę Turinga, jest nierozstrzygalna. Właściwość P jest językiem wszystkich maszyn Turinga, które spełniają tę właściwość.

Definicja formalna

Jeśli P jest nietrywialną własnością, a język posiadający tę właściwość, L p , jest rozpoznawany przez maszynę Turinga M, to L p = {<M> | L (M) ∈ P} jest nierozstrzygalne.

Opis i właściwości

  • Własność języków P to po prostu zbiór języków. Jeśli jakikolwiek język należy do P (L ∈ P), mówi się, że L spełnia właściwość P.

  • Właściwość jest nazywana trywialną, jeśli nie spełnia jej żaden rekurencyjnie wyliczalny język lub jeśli spełnia ją wszystkie rekurencyjnie wyliczalne języki.

  • Nietrywialna własność jest spełniana przez niektóre rekurencyjnie wyliczalne języki, a nie przez inne. Formalnie rzecz biorąc, w nietrywialnej własności, gdzie L ∈ P, zachodzą obie następujące własności:

    • Property 1 - Istnieją maszyny Turinga, M1 i M2, które rozpoznają ten sam język, tj. (<M1>, <M2> ∈ L) lub (<M1>, <M2> ∉ L)

    • Property 2 - Istnieją maszyny Turinga M1 i M2, gdzie M1 rozpoznaje język, a M2 nie, czyli <M1> ∈ L i <M2> ∉ L

Dowód

Załóżmy, że właściwość P jest nietrywialna i φ ∈ P.

Ponieważ P jest nietrywialne, co najmniej jeden język spełnia P, tj. L (M 0 ) ∈ P, ∋ Maszyna Turinga M 0 .

Niech w będzie wartością wejściową w określonej chwili, a N to maszyna Turinga, która następuje po -

Na wejściu x

  • Uruchom M na w
  • Jeśli M nie akceptuje (lub nie zatrzymuje się), to nie akceptuje x (lub nie zatrzymuje się)
  • Jeśli M akceptuje w, uruchom M 0 na x. Jeśli M 0 akceptuje x, zaakceptuj x.

Funkcja odwzorowująca instancję ATM = {<M, w> | M akceptuje wejście w} do N takie, że

  • Jeśli M akceptuje w, a N akceptuje ten sam język co M 0 , to L (M) = L (M 0 ) ∈ p
  • Jeśli M nie akceptuje w, a N akceptuje φ, to L (N) = φ ∉ p

Ponieważ A TM jest nierozstrzygalna i można ją zredukować do Lp, Lp jest również nierozstrzygalna.