Teorema del riso

Il teorema di Rice afferma che qualsiasi proprietà semantica non banale di una lingua riconosciuta da una macchina di Turing è indecidibile. Una proprietà, P, è il linguaggio di tutte le macchine di Turing che soddisfano quella proprietà.

Definizione formale

Se P è una proprietà non banale e il linguaggio che ne contiene la proprietà, L _p , è riconosciuto dalla macchina di Turing M, allora L _p = {<M> | L (M) ∈ P} è indecidibile.

Descrizione e proprietà

• La proprietà delle lingue, P, è semplicemente un insieme di lingue. Se una qualsiasi lingua appartiene a P (L ∈ P), si dice che L soddisfa la proprietà P.

• Una proprietà viene chiamata banale se non è soddisfatta da alcun linguaggio enumerabile ricorsivamente o se è soddisfatta da tutti i linguaggi enumerabili ricorsivamente.

• Una proprietà non banale è soddisfatta da alcuni linguaggi enumerabili ricorsivamente e non è soddisfatta da altri. Formalmente parlando, in una proprietà non banale, dove L ∈ P, valgono entrambe le seguenti proprietà:

  • Property 1 - Esistono macchine di Turing, M1 e M2 che riconoscono la stessa lingua, ovvero (<M1>, <M2> ∈ L) o (<M1>, <M2> ∉ L)

  • Property 2 - Esistono Turing Machines M1 e M2, dove M1 riconosce la lingua mentre M2 no, cioè <M1> ∈ L e <M2> ∉ L

Prova

Supponiamo che una proprietà P non sia banale e che φ ∈ P.

Poiché P non è banale, almeno un linguaggio soddisfa P, cioè L (M ₀ ) ∈ P, ∋ Macchina di Turing M ₀ .

Sia w un input in un particolare istante e N è una macchina di Turing che segue:

All'ingresso x

• Esegui M su w
• Se M non accetta (o non si ferma), allora non accetta x (o non si ferma)
• Se M accetta w, esegui M ₀ su x. Se M ₀ accetta x, allora accetta x.

Una funzione che mappa un'istanza ATM = {<M, w> | M accetta l'input w} a un N tale che

• Se M accetta w e N accetta la stessa lingua di M ₀ , allora L (M) = L (M ₀ ) ∈ p
• Se M non accetta w e N accetta φ, Allora L (N) = φ ∉ p

Poiché A _TM è indecidibile e può essere ridotto a Lp, anche Lp è indecidibile.