จะพิสูจน์ความแน่ได้อย่างไร?

2024 ผู้เขียน: Fiona Howard | [email protected]. แก้ไขล่าสุด: 2024-01-10 06:43

เพื่อแสดงว่าภาษานั้นสามารถตัดสินใจได้ เราต้องการ เพื่อสร้างเครื่องทัวริงที่จะหยุดสตริงการป้อนข้อมูลจากตัวอักษรของภาษา เนื่องจาก 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 เป็นจำนวนรวมนั้นไม่สามารถตัดสินใจได้