ปัญหาการหยุดเครื่องทัวริง

Input - เครื่องทัวริงและสตริงอินพุต w.

Problem - เครื่องทัวริงทำการคำนวณสตริงเสร็จหรือไม่ wในจำนวนขั้นตอนที่ จำกัด ? คำตอบต้องเป็นใช่หรือไม่ใช่

Proof- ในตอนแรกเราจะคิดว่าเครื่องทัวริงนั้นมีอยู่เพื่อแก้ปัญหานี้และจากนั้นเราจะแสดงให้เห็นว่ามันขัดแย้งในตัวเอง เราจะเรียกเครื่องทัวริงนี้ว่าHalting machineที่สร้าง 'ใช่' หรือ 'ไม่ใช่' ในระยะเวลาที่ จำกัด หากเครื่องหยุดทำงานเสร็จสิ้นในระยะเวลาที่กำหนดเอาต์พุตจะเป็น "ใช่" หรือเป็น "ไม่" ต่อไปนี้เป็นแผนภาพบล็อกของเครื่อง Halting -

ตอนนี้เราจะออกแบบไฟล์ inverted halting machine (HM)’ เป็น -

• ถ้า H ส่งกลับใช่แล้ววนซ้ำตลอดไป

• ถ้า H ส่งคืน NO แล้วหยุด

ต่อไปนี้เป็นแผนภาพบล็อกของ 'Inverted halting machine' -

นอกจากนี้เครื่อง (HM)₂ ซึ่งอินพุตนั้นสร้างขึ้นเองดังนี้ -

• หาก (HM) ₂หยุดการป้อนข้อมูลให้วนซ้ำตลอดไป
• อื่นหยุด

ที่นี่เรามีความขัดแย้ง ดังนั้นปัญหาการหยุดชะงักคือundecidable.