Equivalenza tra un TM e un TM che cambia

Question

Lascia che un mutevole TM sia un TM che non è in grado di scrivere lo stesso simbolo che viene letto. Formale: $ m ^ *= (q, \ sigma, \ gamma, \ delta, q_ {accetta}, q_ {rifiutazione}) $ , $ \ delta (q, a)= (q ^ *, a ^ *, c), a \ neq a ^ * $ con $ Q, q ^ * \ in q, a, a ^ * \ in \ gamma, c \ in \ {r, l \} $ . Ora ho bisogno di provare che un TM che cambia è equivalente a un normale TM.

La mia ipotesi era quella di creare un TM multi-nastro che è in grado di simulare la modifica del mutevole TM (e quindi un TM è equivalgono a un mutevole TM, poiché ogni multi nastro TM ha un tape singolo equivalente TM), ma sono inutilizzabileFinitura (scrivilo formale e non formazionale).

Answer 1

Questo è un altro modo semplice per dimostrare che un TM che cambia può simulare un TM. Il vantaggio di questa soluzione rispetto a quello precedente è che funziona senza ulteriori lavori noiosi indipendentemente dal fatto che il movimento "soggiorno" sia consentito.

Let $ T $ essere un TM con alfabeto nastro $ \ gamma $ . Creare un mutevole TM $ T '$ con lo stesso spazio di stato e un alfabeto nastro $ \ gamma' $ con $ 2 | \ gamma | $ simboli: per ogni simbolo $ a \ in \ gamma $ Aggiungi entrambi < Span Class="Math-Container"> $ A $ e un nuovo simbolo $ a '$ a $ \ Gamma '$ .

per ogni transizione $ (q, a) \ a (q ', b, m) $ di $ t $ Aggiungi le seguenti transizioni a $ T '$ (Si noti che è possibile avere $ A= B $ < / SPAN>):

.
• $ (q, a) \ a (q ', b', m) $
• $ (q, a ') \ to (q', b, m) $

in altre parole stai trattando due simboli $ a $ e $ a '$ come se loro erano identici. Ogni volta che leggi un simbolo "regolare" (I.e., uno da $ \ gamma $ ) scriverai un simbolo "Prime". Ogni volta che leggi un simbolo "Prime" (I.e., uno di $ \ gamma '\ setminus \ gamma $ ) scriverai un simbolo "regolare".

Answer 2

È chiaro che un TM può simulare un mutevole TM, quindi è necessario mostrare solo il Concorso. Lasciatemi consentire di utilizzare il movimento "soggiorno" nella macchina che cambia la macchina. È facile (ma noioso) per rimuovere questa ipotesi e mantenendolo rende il seguente argomento più intuitivo.

È possibile effettuare le seguenti operazioni: Inizia da una classe TM $ T $ con set di stati $ Q $ e alfabeto nastro $ \ gamma $ . Quindi, creare un mutevole TM $ T '$ con stati $ q'= q \ tazza (q \ volte \ gamma \ tempi \ {l, r \}) $ e alfabeto del nastro $ \ gamma '=gamma \ cup \ {\ gamma \} $ .

intuitivamente, stato $ Q \ in q $ di $ t '$ rappresenta lo stato $ q $ di $ t $ , mentre stato $ (q, a , m) \ in q \ time \ gamma \ time \ {l, r \} $ di $ T '$ rappresenta il fatto che abbiamo intenzione di pianificare scrivi $ A $ Nella cella di nastro corrente, quindi transizione in stato $ q $ e muoversi nel Direzione specificata da $ M $ (Si noti che questo stato, non una transizione, stiamo solo tenendo traccia dei nostri piani futuri). < / P >.

Sostituisci ogni transizione $ (q, a) \ to (q ', b, m) $ di $ t $ con le seguenti transizioni in $ T '$ :

.
• $ (q, a) \ a ((q ', b, m), \ gamma, s) $ e
• $ ((q ', b, m), \ gamma) \ a (q', b, m) $

Intuitivamente, questo sostituisce la scrittura di un simbolo $ B $ sul nastro con due operazioni: 1) scriviamo $ \ gamma $ senza spostare la testa e 2) sovrascrivere $ \ gamma $ con $ B $ , spostare la testa nella direzione prevista $ m $ e transizione verso lo stato corrispondente $ Q '$ di $ T $ .

---

.

Questo è un tedio simulaton di un TM con un TM che cambia se il "movimento del soggiorno" non è permesso. Definisci $ \ gamma '=gamma \ cup \ {\ gamma_1, \ gamma_2 \} $ e $ q'= q \ Cup (q \ volte \ gamma \ time \ {l, r \} \ volte \ gamma ') $ . Sostituisci ogni transizione $ (q, a) \ to (q ', b, m) $ di $ T $ Con le seguenti transizioni in $ T '$ :

.
• $ (q, a) \ a ((q ', b, m, \ gamma_1), \ gamma_1, r) $ ,
• $ ((q ', b, m, \ gamma_1), x) \ a ((q', b, m, x), \ gamma_2, l) $ < / span> $ \ quad \ forlt x \ in \ gamma $ ,
• $ ((q ', b, m, x), \ gamma_1) \ a ((q', b, m, x), \ gamma_2, r) $ < / span> $ \ quad \ forlt x \ in \ gamma $ ,
• $ ((q ', b, m, x), \ gamma_2) \ a ((q', b, m, \ gamma_1), x, l) $ < / span> $ \ quad \ forlt x \ in \ gamma $ ,
• $ ((q ', b, m, \ gamma_1), \ gamma_2) \ a (q', b, m) $

Cosa stiamo facendo è quanto segue: 1) Scriviamo $ \ gamma_1 $ e spostare a destra, 2) memorizziamo il simbolo del nastro corrente $ x $ , sostituirlo con $ \ gamma_2 $ e spostamento a sinistra, 3) Sostituiamo il simbolo del nastro $ \ gamma_1 $ con $-contenitore "> $ \ gamma_2 $ e sposta a destra, 4) scriviamo il simbolo del tipo memorizzato $ x $ al posto di $ \ gamma_2 $ e muoversi a sinistra, 5) Abbiamo finalmente scritto $ B $ , Spostarsi secondo $ M $ e Transition to State $ q ' .