เพื่อแสดงว่าภาษานั้นสามารถตัดสินใจได้ เราต้องการ เพื่อสร้างเครื่องทัวริงที่จะหยุดสตริงการป้อนข้อมูลจากตัวอักษรของภาษา เนื่องจาก M เป็น dfa เราจึงมีทัวริงแมชชีนอยู่แล้ว และเพียงแค่ต้องแสดงให้เห็นว่า dfa หยุดในทุกอินพุต
คุณคำนวณความสามารถในการตัดสินใจอย่างไร
ภาษาคือ ตัดสินใจได้ก็ต่อเมื่อสามารถจดจำได้เท่านั้น การพิสูจน์. หากภาษานั้นตัดสินได้ ส่วนเสริมของมันก็ตัดสินได้ (โดยการปิดภายใต้การเติมเต็ม)
คุณพิสูจน์ความสามารถในการตัดสินใจของทัวริงได้อย่างไร
พิสูจน์ว่าภาษาที่รู้จักนั้นเท่ากับภาษาที่กำหนดและอัลกอริธึมหยุดการป้อนข้อมูลทั้งหมด เพื่อพิสูจน์ว่าภาษาใดภาษาหนึ่งนั้นทัวริงสามารถจดจำได้: สร้างอัลกอริทึมที่ยอมรับสตริงที่อยู่ในภาษานั้นทุกประการต้องปฏิเสธหรือวนซ้ำในสตริงใด ๆ ที่ไม่ได้อยู่ในภาษา
คุณจะรู้ได้อย่างไรว่าภาษานั้นจำได้ไหม
ภาษา L จะจำได้ก็ต่อเมื่อ มีตัวตรวจสอบสำหรับ L โดยที่ตัวตรวจสอบคือเครื่องทัวริงที่หยุดอินพุตทั้งหมดและสำหรับ w∈Σ∗ ทั้งหมด, w∈L↔∃c∈Σ∗. วี ยอมรับ ⟨w, c⟩.
แสดงว่าปัญหายังตัดสินใจไม่ได้
The Totality Problem is Undecidable
The h alting problems สามารถใช้เพื่อแสดงว่าปัญหาอื่นไม่สามารถตัดสินใจได้ ปัญหาทั้งหมด: ฟังก์ชัน (หรือโปรแกรม) F เรียกว่าผลรวม ถ้า F(x) ถูกกำหนดไว้สำหรับ x ทั้งหมด (หรือในทำนองเดียวกัน ถ้า F(x) หยุดสำหรับ x ทั้งหมด) การพิจารณาว่าฟังก์ชัน F เป็นจำนวนรวมนั้นไม่สามารถตัดสินใจได้