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.