Macchina che può ricordare
-
29-09-2020 - |
Domanda
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.
Soluzione
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.