Come sostenere che se potessimo risolvere il problema dell'arresto, allora potremmo risolvere il castoro indaffarato?

Question

Questo è uno dei compiti del mio incarico.Ho una simulazione della macchina di Turing che può simulare a funzione castoro occupato.Ho fatto alcune ricerche per dimostrare questo problema, ma ancora non ho capito, quindi immagino che forse puoi aiutarmi qui.Una buona fonte a cui rivolgermi o un esempio di come sostenerlo sarebbe utile.

Answer 1

La funzione BB è definita come il numero massimo di passi che una macchina di Turing di una particolare dimensione può eseguire e comunque fermarsi.(Un altro modo di dirlo è che tutte le macchine di Turing di dimensione x si fermeranno in passi inferiori a BB(x) o funzioneranno per sempre).

Supponendo di avere una macchina di Turing di complessità x, potresti determinare se si fermerebbe o meno lasciandola funzionare per passi temporali BB (x): se non si fosse fermata entro allora, per definizione non lo farà mai.

Allo stesso modo, se potessi risolvere il problema dell'arresto, potresti valutare tutte le possibili macchine di Turing di dimensione x, eliminare quelle che non si fermano e considerare BB(x) come il massimo dei tempi di esecuzione dei resti.

Naturalmente, BB(x) non è calcolabile - e in effetti cresce più velocemente di qualsiasi possibile funzione calcolabile che potresti nominare - quindi non può nemmeno essere approssimato.

Answer 2

È possibile trovare la prova che cercate qui , sotto la prova che il problema Busy Beaver è uncomputable.