ทฤษฎีบทข้าว

ทฤษฎีบทของข้าวระบุว่าคุณสมบัติทางความหมายที่ไม่สำคัญใด ๆ ของภาษาที่เครื่องทัวริงยอมรับนั้นไม่สามารถยืนยันได้ คุณสมบัติ P คือภาษาของเครื่องทัวริงทั้งหมดที่ตอบสนองคุณสมบัตินั้น

นิยามอย่างเป็นทางการ

ถ้า P เป็นคุณสมบัติที่ไม่สำคัญและภาษาที่ถือคุณสมบัติ L _pได้รับการยอมรับโดย Turing machine M ดังนั้น L _p = {<M> | L (M) ∈ P} ไม่สามารถตัดสินใจได้

คำอธิบายและคุณสมบัติ

• คุณสมบัติของภาษา P เป็นเพียงชุดของภาษา ถ้าภาษาใด ๆ เป็นของ P (L ∈ P) แสดงว่า L ตอบสนองคุณสมบัติ P

• คุณสมบัติถูกเรียกให้เป็นเรื่องเล็กน้อยหากไม่เป็นที่พอใจของภาษาที่แจกแจงซ้ำ ๆ หรือหากเป็นที่พอใจของภาษาที่นับซ้ำได้ทั้งหมด

• ทรัพย์สินที่ไม่สำคัญเป็นที่พึงพอใจของภาษาที่แจกแจงซ้ำ ๆ และไม่เป็นที่พอใจของผู้อื่น พูดอย่างเป็นทางการในคุณสมบัติที่ไม่สำคัญโดยที่ L ∈ P คุณสมบัติทั้งสองต่อไปนี้ถือ:

  • Property 1 - มีเครื่องทัวริง M1 และ M2 ที่รับรู้ภาษาเดียวกันเช่น (<M1>, <M2> ∈ L) หรือ (<M1>, <M2> ∉ L)

  • Property 2 - มี Turing Machines M1 และ M2 โดยที่ M1 รับรู้ภาษาในขณะที่ M2 ไม่รับเช่น <M1> ∈ L และ <M2> ∉ L

หลักฐาน

สมมติว่าคุณสมบัติ P ไม่ใช่เรื่องเล็กน้อยและφ∈ P.

เนื่องจาก P นั้นไม่น่ารำคาญอย่างน้อยหนึ่ง satisfies ภาษา P คือ L (M ₀ ) ∈ P, ∋ทัวริงเครื่องจักร M 0

ให้ w เป็นอินพุตในช่วงเวลาหนึ่งและ N คือ Turing Machine ซึ่งตามมา -

บนอินพุต x

• เรียกใช้ M บน w
• ถ้า M ไม่ยอมรับ (หรือไม่หยุด) ก็ไม่ยอมรับ x (หรือไม่หยุด)
• ถ้า M ยอมรับ w ให้รัน M ₀บน x ถ้า M ₀ยอมรับ x ก็ให้ยอมรับ x

ฟังก์ชันที่แมปอินสแตนซ์ ATM = {<M, w> | M ยอมรับอินพุต w} ถึง N เช่นนั้น

• ถ้า M ยอมรับ w และ N ยอมรับภาษาเดียวกันกับ M ₀ดังนั้น L (M) = L (M ₀ ) ∈ p
• ถ้า M ไม่ยอมรับ w และ N ยอมรับφดังนั้น L (N) = φ∉ p

เนื่องจาก A _TMไม่สามารถตัดสินใจได้และสามารถลดเป็น Lp ได้ Lp จึงไม่สามารถตัดสินใจได้