Pirinç Teoremi
Rice teoremi, bir Turing makinesi tarafından tanınan bir dilin önemsiz olmayan herhangi bir anlamsal özelliğinin karar verilemez olduğunu belirtir. Bir özellik, P, bu özelliği karşılayan tüm Turing makinelerinin dilidir.
Resmi tanımlama
P önemsiz olmayan bir özellikse ve özelliği tutan dil olan L p , Turing makinesi M tarafından tanınırsa, L p = {<M> | L (M) ∈ P} karar verilemez.
Tanım ve Özellikler
Dillerin özelliği, P, sadece bir diller kümesidir. Herhangi bir dil P (L ∈ P) 'ye aitse, L'nin P özelliğini karşıladığı söylenir.
Bir özellik, özyinelemeli olarak numaralandırılabilen herhangi bir dil tarafından tatmin edilmezse veya özyinelemeli olarak numaralandırılabilen tüm diller tarafından karşılanırsa, önemsiz olarak adlandırılır.
Önemsiz olmayan bir özellik, yinelemeli olarak numaralandırılabilen bazı diller tarafından karşılanır ve diğerleri tarafından tatmin edilmez. Resmi olarak konuşursak, önemsiz olmayan bir mülkte, burada L ∈ P, aşağıdaki özelliklerin her ikisi de geçerlidir:
Property 1 - Aynı dili tanıyan M1 ve M2 Turing Makineleri vardır, yani (<M1>, <M2> ∈ L) veya (<M1>, <M2> ∉ L)
Property 2 - M1'in dili tanıdığı, M2'nin tanımadığı Turing Makineleri M1 ve M2 vardır, yani <M1> ∈ L ve <M2> ∉ L
Kanıt
Diyelim ki, P özelliği önemsiz değil ve φ ∈ P.
P önemsiz olmadığından, en az bir dil P'yi karşılar, yani L (M 0 ) ∈ P, ∋ Turing Makinesi M 0 .
Belirli bir anda bir girdi olalım ve N aşağıdaki bir Turing Makinesidir -
X girişinde
- M'yi w üzerinde çalıştır
- M kabul etmezse (veya durmazsa), x kabul etmeyin (veya durmayın)
- M w'yi kabul ederse , x üzerinde M 0'ı çalıştırın . M 0 x'i kabul ederse, x'i kabul edin.
ATM = {<M, w> | örneğini eşleyen bir işlev M, w} girdisini bir N'ye kabul eder, öyle ki
- M w kabul ederse ve N, M 0 ile aynı dili kabul ederse, L (M) = L (M 0 ) ∈ p
- M w kabul etmezse ve N kabul eder φ, O zaman L (N) = φ ∉ p
Bir TM karar verilemez olduğundan ve Lp'ye indirgenebileceğinden, Lp de karar verilemez.