Problema di arresto per le macchine di tentazione con un input

Question

La mia domanda è:

.

Esiste una costruzione semplice simile al programma "bugiardo" di Turing che mostra che le macchine di Turing più un oracolo di arresto non può decidere se una determinata macchina di Turing si ferma su tutti gli ingressi.

Quando parlo del programma bugiardo, mi riferisco alla prova standard che una macchina di Turing non può determinare l'arresto di tutte le altre macchine Turing, poiché l'analisi del caso sui seguenti lead alle contraddizioni

def Liar(T):
   if Halts('T(T)'):
      loop()
   else:
      return

.

Posso vedere che avere un'elenco di oracle mi permetterà di determinare se una macchina di Turing si ferma su qualsiasi set finito di ingressi (andavamo semplicemente tutto in ordine).

Se chiamiamo le macchine regolari di Turing Level 0, possiamo chiamare macchine di Turing più il livello di oracle di arresto 1. Ho visto che la prova utilizzando il programma bugiardo funziona lo stesso per mostrare che le macchine di livello 1 hanno il proprio problema di fermezzaè indecidabile per loro.

Answer 1

Cosa si chiama un programma "bugiardo" è in genere chiamato argomento diagonalizzazione , poiché in qualche modo assomiglia all'argomento di diagonalizzazione del cantore.

Di solito ciò che intendiamo con questo è che se cerchiamo di enumerare tutti gli elementi con una certa proprietà, allora possiamo sottolineare, per costruzione, un elemento che è necessariamente "errato", e lo facciamo dimostrando che lo fa Non soddisfare la proprietà per se stessa (questa è completamente ondulata a mano, ma se hai visto l'argomento, speriamo di capire cosa intendo).

Ora, quello che stai chiedendo è se possiamo fare lo stesso per dimostrare che ALL_TM (Universalità TM) non è decidabile da un TM con Oracle a HALT_TM.

Beh, non proprio. Almeno non in modo naturale: l'argomento avrebbe dovuto iniziare assumendo che esiste una macchina Oracle M che decide all_tm, e poi costruendo da m qualche altro macchina n (cosa chiami una macchina "bugiarda"), che avrebbe dato a contraddizione quando corriamo n on n. Tuttavia, la macchina N dovrebbe essere una macchina Oracle, non un TM standard (o perderà essenzialmente la potenza dell'oracolo in m). Ma poiché l'Oracle in N prende come ingresso TMS standard, quindi il lavoro interno di N avrebbe in qualche modo necessario creare un TM standard per nutrire l'Oracle. Questo non sembra una costruzione naturale, e non sarebbe certamente semplice.

Ora, forse c'è un modo contorto per dare un argomento diretto di diagonalizzazione per questa affermazione, ma non è ben motivato, dato che dimostrando direttamente il reclamo (vale a dire che ALL_TM non è decidabile da un TM con Oracle a Halt) non lo è difficile utilizzando strumenti standard, come riduzioni.