Théorème du riz
Le théorème de Rice déclare que toute propriété sémantique non triviale d'un langage qui est reconnue par une machine de Turing est indécidable. Une propriété, P, est le langage de toutes les machines de Turing qui satisfont cette propriété.
Définition formelle
Si P est une propriété non triviale et que le langage détenant la propriété, L p , est reconnu par la machine de Turing M, alors L p = {<M> | L (M) ∈ P} est indécidable.
Description et propriétés
Propriété des langues, P, est simplement un ensemble de langues. Si un langage appartient à P (L ∈ P), on dit que L satisfait la propriété P.
Une propriété est appelée à être triviale si elle n'est satisfaite par aucun langage récursivement énumérable, ou si elle est satisfaite par tous les langages récursivement énumérables.
Une propriété non triviale est satisfaite par certains langages énumérables récursivement et n'est pas satisfaite par d'autres. Formellement parlant, dans une propriété non triviale, où L ∈ P, les deux propriétés suivantes sont vérifiées:
Property 1 - Il existe des Machines de Turing, M1 et M2 qui reconnaissent le même langage, à savoir soit (<M1>, <M2> ∈ L) ou (<M1>, <M2> ∉ L)
Property 2 - Il existe des Machines de Turing M1 et M2, où M1 reconnaît le langage alors que M2 ne le fait pas, c'est-à-dire <M1> ∈ L et <M2> ∉ L
Preuve
Supposons qu'une propriété P soit non triviale et φ ∈ P.
Puisque P est non trivial, au moins un langage satisfait P, c'est-à-dire L (M 0 ) ∈ P, ∋ Turing Machine M 0 .
Soit w une entrée à un instant particulier et N est une machine de Turing qui suit -
Sur entrée x
- Exécuter M sur w
- Si M n'accepte pas (ou ne s'arrête pas), alors n'acceptez pas x (ou ne vous arrêtez pas)
- Si M accepte w alors exécutez M 0 sur x. Si M 0 accepte x, alors acceptez x.
Une fonction qui mappe une instance ATM = {<M, w> | M accepte l'entrée w} dans un N tel que
- Si M accepte w et N accepte le même langage que M 0 , alors L (M) = L (M 0 ) ∈ p
- Si M n'accepte pas w et N accepte φ, alors L (N) = φ ∉ p
Comme A TM est indécidable et peut être réduit à Lp, Lp est également indécidable.