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.