Problema di arresto della macchina di Turing
Input - Una macchina di Turing e una stringa di input w.
Problem - La macchina di Turing finisce di calcolare la stringa win un numero finito di passaggi? La risposta deve essere sì o no.
Proof- In un primo momento, supporremo che una macchina di Turing del genere esista per risolvere questo problema e poi mostreremo che si contraddice. Chiameremo questa macchina di Turing come aHalting machineche produce un "sì" o un "no" in un periodo di tempo finito. Se la macchina di arresto termina in un periodo di tempo finito, l'output è "sì", altrimenti "no". Quello che segue è lo schema a blocchi di una macchina di arresto:
Ora progetteremo un file inverted halting machine (HM)’ come -
Se H restituisce YES, quindi esegue il ciclo per sempre.
Se H restituisce NO, quindi interrompe.
Quello che segue è lo schema a blocchi di una 'macchina di arresto invertita' -
Inoltre, una macchina (HM)2 quale input stesso è costruito come segue:
- Se (HM) 2 si interrompe durante l'input, loop all'infinito.
- Altrimenti, fermati.
Qui abbiamo una contraddizione. Quindi, il problema dell'arresto èundecidable.