Masalah Menghentikan Mesin Turing

Input - Mesin Turing dan string input w.

Problem - Apakah mesin Turing menyelesaikan penghitungan string wdalam jumlah langkah yang terbatas? Jawabannya harus ya atau tidak.

Proof- Pada awalnya, kami akan berasumsi bahwa mesin Turing semacam itu ada untuk menyelesaikan masalah ini dan kemudian kami akan menunjukkan bahwa mesin itu bertentangan dengan dirinya sendiri. Kami akan menyebut mesin Turing ini sebagaiHalting machineyang menghasilkan 'ya' atau 'tidak' dalam waktu yang terbatas. Jika mesin berhenti berhenti dalam waktu yang terbatas, hasilnya akan muncul sebagai 'ya', sebaliknya sebagai 'tidak'. Berikut ini adalah diagram blok dari mesin Halting -

Sekarang kita akan mendesain file inverted halting machine (HM)’ sebagai -

• Jika H mengembalikan YA, kemudian mengulang selamanya.

• Jika H mengembalikan NO, lalu berhenti.

Berikut ini adalah diagram blok dari 'Mesin penghenti terbalik' -

Selanjutnya, mesin (HM)₂ yang masukan itu sendiri dibangun sebagai berikut -

• Jika (HM) ₂ berhenti pada input, lakukan loop selamanya.
• Lain, berhenti.

Di sini, kami mendapat kontradiksi. Oleh karena itu, masalah berhenti adalahundecidable.