Sự cố dừng máy Turing

Input - Một máy Turing và một chuỗi đầu vào w.

Problem - Máy Turing có hoàn thành tính toán chuỗi không wtrong một số bước hữu hạn? Câu trả lời phải là có hoặc không.

Proof- Lúc đầu, chúng tôi sẽ cho rằng tồn tại một cỗ máy Turing như vậy để giải quyết vấn đề này và sau đó chúng tôi sẽ cho thấy nó đang tự mâu thuẫn với chính nó. Chúng tôi sẽ gọi máy Turing này làHalting machinetạo ra 'có' hoặc 'không' trong một khoảng thời gian hữu hạn. Nếu máy tạm dừng kết thúc trong một khoảng thời gian hữu hạn, kết quả đầu ra là "có", ngược lại là "không". Sau đây là sơ đồ khối của máy tạm dừng -

Bây giờ chúng tôi sẽ thiết kế một inverted halting machine (HM)’ như -

• Nếu H trả về CÓ, sau đó lặp lại mãi mãi.

• Nếu H trả về KHÔNG, sau đó dừng lại.

Sau đây là sơ đồ khối của 'Máy dừng ngược' -

Hơn nữa, một cỗ máy (HM)₂ đầu vào nào chính nó được xây dựng như sau:

• Nếu (HM) ₂ dừng trên đầu vào, lặp lại mãi mãi.
• Khác, dừng lại.

Ở đây, chúng tôi đã có một mâu thuẫn. Do đó, vấn đề tạm dừng làundecidable.