Equivalencia entre un TM y un TM cambiante.

Question

Deja que un cambio de TM sea un TM que no pueda escribir el mismo símbolo que se está lea. Formal: $ m ^ *= (q, \ sigma, \ gamma, \ delta, q_ {aceptan}, q_ {rechazar}) $ , $ \ Delta (Q, A)= (Q ^ *, A ^ *, C), A \ NEQ A ^ * $ con $ q, q ^ * \ en q, a, a ^ * \ in \ gamma, c \ in \ {r, l \ \ \ {r, l \} $ . Ahora necesito probar que un TM cambiante es equivalente a un TM normal.

Mi conjetura fue crear un TM de múltiples cintas que sea capaz de simular el cambio de TM (y, por lo tanto, un TM es equivalente a un TM cambiante, ya que cada TM de múltiples cintas tiene una sola cinta TM equivalente), pero no soy libre paraTerminar (escribirlo formal y no formal hacia abajo).

Answer 1

Esta es otra manera fácil de demostrar que un TM cambiante puede simular un TM. La ventaja de esta solución sobre la anterior es que funciona sin ningún trabajo tedioso adicional, independientemente de si se permite el movimiento de "estancia".

Permitir $ t $ ser un TM con alfabeto de cinta $ \ gamma $ . Cree un cambio de TM $ t '$ con el mismo espacio de estado y un alfabeto de cinta $ \ gamma' $ con $ 2 | \ gamma | $ símbolos: para cada símbolo $ a \ in \ gamma $ agregar < Span Class="Math-contenedor"> $ A $ y un nuevo símbolo $ a '$ a $ \ Gamma '$ .

para cada transición $ (q, a) \ a (q ', b, m) $ de $ t $ Agregue las siguientes transiciones a $ t '$ (notificación que puede tener $ a= b $ < / SPAN>):

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

En otras palabras, está tratando a dos símbolos $ a $ y $ a '$ como si estuvieran eran idénticos. Cada vez que lea un símbolo "regular" (es decir, uno de $ \ gamma $ ) escribirá un símbolo "Prime". Cada vez que lea un símbolo "Prime" (es decir, uno de $ \ gamma '\ setminus \ gamma $ ) Escribirá un símbolo "regular".

Answer 2

Está claro que un TM puede simular un TM cambiante, por lo que solo necesita mostrar lo contrario. Permítanme permitir usar el movimiento "Estancia" en la máquina cambiante. Es fácil (pero tedioso) eliminar este supuesto y mantenerlo hace que el siguiente argumento sea más intuitivo.

Puede hacer lo siguiente: Comience desde un TM $ t $ con un conjunto de estados $ q $ y cinta alfabeto $ \ gamma $ . Luego, cree un cambio de TM $ t '$ con estados $ q'= q \ taza (Q \ Times \ Gamma \ veces \ {l, r \}) $ y cinta alfabeto $ \ gamma '=gamma \ cuco \ {\ gamma \} $ .

intuitivamente, estado $ q \ in q $ de $ t '$ representa el estado $ Q $ de $ t $ , mientras que el estado $ (q, a , m) \ en Q \ Times \ Gamma \ Times \ {l, r \ \ \ {span> de $ t '$ representa el hecho de que planeamos Escribe $ A $ en la celda de cinta actual, luego la transición a estado $ q $ y muévase en el Dirección especificada por $ m $ (notifique que este estado, no no una transición, solo estamos realizando un seguimiento de nuestros planes futuros). < / p>

Reemplace cada transición $ (q, a) \ a (q ', b, m) $ de $ t $ con las siguientes transiciones en $ t '$ :

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

intuitivamente, esto reemplaza la escritura de un símbolo $ b $ en la cinta con dos operaciones: 1) Escribimos $ \ gamma $ sin mover la cabeza, y 2) sobrescribimos $ \ gamma $ con $ b $ , mueva la cabeza en la dirección prevista $ m $ y la transición al estado correspondiente $ q '$ de $ t $ .

---

Este es un simulatón tedioso de un TM con un TM cambiante si no se permite el "movimiento de estancia". Define $ \ gamma '=gamma \ cuco \ {\ gamma_1, \ gamma_2 \} $ y $ q'= q \ CUP (Q \ Times \ Gamma \ Times \ {L, R \ \ Times \ Gamma ') $ . Reemplace cada transición $ (q, a) \ a (q ', b, m) $ de $ t $ Con las siguientes transiciones en $ 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 \ forall x \ in \ gamma $ ,
• $ ((q ', b, m, x), \ gamma_1) \ a ((q', b, m, x), \ gamma_2, r) $ < / span> $ \ quad \ forall x \ in \ gamma $ ,
• $ ((q ', b, m, x), \ gamma_2) \ a ((q', b, m, \ gamma_1), x, l) $ < / span> $ \ quad \ forall x \ in \ gamma $ ,
• $ ((q ', b, m, \ gamma_1), \ gamma_2) \ a (q', b, m) $

Lo que estamos haciendo es lo siguiente: 1) Escribimos $ \ gamma_1 $ y muévete a la derecha, 2) almacenamos el símbolo de cinta actual $ x $ , reemplácelo con $ \ gamma_2 $ y muévase a la izquierda, 3) Reemplazamos el símbolo de cinta $ \ gamma_1 $ con $ \ gamma_2 $ y muévase a la derecha, 4) Escribimos el símbolo de tipo almacenado $ x $ en lugar de $ \ gamma_2 $ y muévete a la izquierda, 5) finalmente escribimos $ B $ , muévase de acuerdo con $ m $ y transición a estado $ q '$ .