Me encontré con el siguiente problema en este pdf :
Dado un TM M, si M alguna vez escribe un símbolo que no esté en blanco cuando se inicia en la cinta vacía.
La solución dada es la siguiente:
Deje que la máquina solo escriba en blanco símbolo. Entonces, su número de configuraciones en el cálculo de com en w es q × 2, donde q es el número de estados de M; el factor 2 es para las opciones re. la dirección del movimiento de las cabezas; no hay ningún factor para el símbolo escrito porque siempre está en blanco. Entonces, el problema es decidible, decidido por la siguiente máquina: ingrese (M, w), ejecute M en w para q × 2 pasos; si M alguna vez escribe un símbolo que no esté en blanco, deténgase con una respuesta afirmativa; si M nunca escribe un símbolo que no esté en blanco, deténgase sin respuesta
Dudas:
Q1. Cómo estar seguro de que se realizarán todas las configuraciones qx 2 mientras ejecuta qx 2 pasos en w? Algunas configuraciones pueden repetirse en qx 2 pasos.
Q2. La pregunta dice «cuando se inició en el cinta vacía «, pero la respuesta intentó simular TM en una cadena no vacía w. ¿Qué sentido tiene?
Respuesta
Q1: Un estado puede repetirse. El punto es que si un estado se repite y ni siquiera se ha escrito un símbolo que no esté vacío, entonces sabrá que la máquina de Turing nunca se detendrá, ya que necesariamente está atascada en el ciclo de algunos de los estados encontrados hasta ahora. Dado que ninguno de los estados del ciclo hizo que la TM escribiera un símbolo que no estuviera en blanco, la TM nunca escribirá un símbolo que no esté en blanco.
Después de $ 2q $ pasos, se ha escrito un símbolo que no está en blanco y puede responder «sí», o todos los símbolos escritos estaban en blanco y (al menos) se debe haber encontrado un estado dos o más veces, lo que significa que puede responder «no».
Q2: Supongo que $ w $ se define en algún lugar para ser la cadena vacía. Si la TM puede iniciarse con alguna cadena arbitraria $ w $ , entonces una variación de la solución anterior aún funciona. Suponga que el encabezado de la MT comienza al principio de $ w $ . El número de estados aumenta en un factor de como máximo $ 1+ | w | $ para tener en cuenta todos los estados posibles de la cinta (si solo se escriben símbolos en blanco , entonces la cinta siempre contiene uno de los sufijos $ 1+ | w | $ de $ w $ ). Si la cabeza puede comenzar en cualquier lugar, entonces este factor será como máximo $ 1+ | w | ^ 2 $ .
Comentarios
- En Q1. ¿Quiere decir " que se ha escrito un símbolo que no está en blanco y puede responder sí … y puede responder no "? Porque la pregunta pregunta " si M alguna vez escribe un símbolo que no esté en blanco ". En Q2. No obtuve " en el número de estados correspondientes al número de subconjuntos de posiciones de w que se han sobrescrito con un símbolo en blanco "
- Tienes razón. Arreglé mi respuesta. También aclaré la última parte.