Macchina che può ricordare

Question

Special Turing Machine è definito come una macchina di Turing standard, solo che ogni passaggio viene effettuato in base al contenuto del nastro a partire dal bordo sinistro alla posizione della testa in nastro. (La funzione di transizione in questo caso appartiene a q x γ * -> q x γ x {l, r})

Quale dei seguenti è True:

a. Ogni lingua l ha una macchina di Turing che decide se e solo se c'è una macchina speciale che decide l.

b. Ogni lingua l ha una macchina di Turing che decide l in un momento polinomiale se e solo se c'è una macchina di tentazione speciale che decide l in un polinomio (polinomiale di ingresso).

c. A, le risposte B sono corrette.

d. A, B Answers non sono corrette.

E la mia domanda è: La risposta corretta è D e non riesco a capire perché.

La risposta è: Ogni lingua può essere decisa da una speciale macchina di tentazione nel tempo di lunghezza dell'ingresso lineare (o (n) quando n è la lunghezza di ingresso). Una funzione di transizione va a destra finché non viene visto nessuno spazio vuoto e non appena vedi uno spazio vuoto interruttore per ricevere o rifiutare in base alla parola scritta sul nastro.

La mia domanda è: Come posso decidere se rifiutare o accettare una parola? In altri modelli computazionali, come PDA, DFA, abbiamo definito la funzione di transizione allo stesso modo e nessuna potenza è stata aggiunta al modello. Perché sembra che il potere sia aggiunto al modello computazionale come risultato del cambiamento della funzione di transizione quando si tratta di macchine Turing?

Grazie.

Answer 1

Dato qualsiasi lingua $ l $ C'è una macchina speciale di Turing $ T $ che decide $ L $ in tempo polinomiale.

La macchina Turing ha 3 stati: gli stati iniziali $ q_0 $ , l'accettazione stato $ Q_A $ e lo stato di rifiuto $ Q_R $ . Let $ \ Gamma $ Sii l'alfabeto del nastro (incluso il simbolo vuoto $ \ varepsilon $ ), e lascia $ \ alfa x $ Denota il contenuto del nastro a partire dal bordo sinistro alla posizione della testa in nastro, dove $ \ alfa \ in \ gamma ^ * $ e $ x \ in \ gamma $ . Come al solito, suppongo che l'input sia scritto a partire dall'inizio del nastro e che la testa è inizialmente posizionata all'inizio del nastro. La funzione di transizione $ \ delta $ è definito come segue:

.
• $ \ delta (q_0, \ alpha x)= (q_0, x, r) $ se $ x \ neq \ varepsilon $
• $ \ delta (q_0, \ alpha x)= (q_a, x, r) $ se $ x=Varepsilon $ e $ \ alfa \ in l $
• $ \ delta (q_0, \ alpha x)= (q_a, x, r) $ se $ x=Varepsilon $ e $ \ alfa \ non \ in l $

Poiché ci sono lingue indecidentali per le macchine di Turing regolari, questo implica immediatamente che A e B sono falsi.

Le risposte D e C non sono chiare. Parlano di "entrambe le risposte" ma ti viene data $ 4 $ possibili risposte.