Định lý Rice
Định lý Rice tuyên bố rằng bất kỳ thuộc tính ngữ nghĩa không tầm thường nào của một ngôn ngữ được máy Turing nhận ra là không thể quyết định được. Thuộc tính, P, là ngôn ngữ của tất cả các máy Turing thỏa mãn thuộc tính đó.
Định nghĩa chính thức
Nếu P là một thuộc tính không tầm thường và ngôn ngữ chứa thuộc tính, L p , được máy Turing M nhận dạng, thì L p = {<M> | L (M) ∈ P} không xác định được.
Mô tả và Thuộc tính
Thuộc tính của ngôn ngữ, P, chỉ đơn giản là một tập hợp các ngôn ngữ. Nếu ngôn ngữ nào thuộc P (L ∈ P) thì nói rằng L thỏa mãn tính chất P.
Một thuộc tính được gọi là tầm thường nếu nó không được đáp ứng bởi bất kỳ ngôn ngữ liệt kê đệ quy nào, hoặc nếu nó được đáp ứng bởi tất cả các ngôn ngữ liệt kê đệ quy.
Một thuộc tính không tầm thường được thỏa mãn bởi một số ngôn ngữ liệt kê đệ quy và không được thỏa mãn bởi những ngôn ngữ khác. Nói một cách chính thức, trong một thuộc tính không tầm thường, trong đó L ∈ P, cả hai thuộc tính sau đều giữ:
Property 1 - Có các Máy Turing, M1 và M2 nhận dạng cùng một ngôn ngữ, tức là (<M1>, <M2> ∈ L) hoặc (<M1>, <M2> ∉ L)
Property 2 - Có các Máy Turing M1 và M2, trong đó M1 nhận ra ngôn ngữ trong khi M2 thì không, tức là <M1> ∈ L và <M2> ∉ L
Bằng chứng
Giả sử, một thuộc tính P là không tầm thường và φ ∈ P.
Vì P không tầm thường, nên có ít nhất một ngôn ngữ thỏa mãn P, tức là, L (M 0 ) ∈ P, ∋ Máy Turing M 0 .
Giả sử, w là một đầu vào trong một thời điểm cụ thể và N là một Máy Turing theo sau:
Trên đầu vào x
- Chạy M trên w
- Nếu M không chấp nhận (hoặc không dừng lại), thì không chấp nhận x (hoặc không dừng lại)
- Nếu M chấp nhận w thì chạy M 0 trên x. Nếu M 0 chấp nhận x thì chấp nhận x.
Một hàm ánh xạ một phiên bản ATM = {<M, w> | M chấp nhận đầu vào w} thành N sao cho
- Nếu M chấp nhận w và N chấp nhận cùng một ngôn ngữ với M 0 thì L (M) = L (M 0 ) ∈ p
- Nếu M không chấp nhận w và N chấp nhận φ thì L (N) = φ ∉ p
Vì A TM là không thể quyết định và nó có thể được giảm xuống Lp, nên Lp cũng không thể quyết định.