máquina de turing con exactamente 42 estados / estado que se visita al menos 42 veces

Estoy tratando de resolver los siguientes problemas:

Prueba de si los siguientes problemas son decidibles/indecidibles:

  1. Dada la máquina de turing M: ¿M tiene exactamente 42 estados?
  2. Dada la máquina de Turing M: ¿M tiene un estado que se visita al menos 42 veces cuando se inicia en una cinta vacía?
  3. Dada la máquina de turing M: ¿M tiene un estado que no se visita más de 42 veces cuando se inicia en una cinta vacía?

Soy bastante nuevo en el tema de la teoría de la computabilidad y mi intuición es la siguiente:

  1. Decidible, ya que el número de estados podría establecerse de alguna manera mediante la codificación de la máquina de Turing (he leído algo sobre la codificación por un número de Gödel en línea, sin embargo, aún no hemos aprendido esto en mi conferencia).

  2. y 3. son probablemente indecidibles. Traté de probar esto reduciendo el problema al problema de la detención en una cinta vacía, pero aún no obtuve la idea correcta.

Agradecería cualquier idea que me indique la dirección correcta...

Critica del lenguaje: es "decidible", no "decisivo". Y es "teoría de la computabilidad" en inglés, no "teoría de la decisión". El último se trata de elegir qué acción tomar como ser humano con preferencias sobre los resultados.
@HenningMakholm Gracias, corregí mi publicación :)

Respuestas (2)

Sugerencia para (2): Supongamos METRO tiene norte estados Después 42 norte + 1 pasos, la máquina se habrá detenido o...

(3) es de hecho indecidible. Aquí hay un boceto de prueba, por reducción del problema de detención:

Suponer q es alguna máquina y queremos saber si se detiene en la cinta vacía. Entonces podemos, de manera sistemática, construir una máquina METRO q que hace lo siguiente:

  1. Escribe una descripción de q a la cinta

  2. Simule la máquina cuya descripción está en la cinta hasta que se detenga. (Esto incluye técnicas de la máquina universal que, con suerte, sabrá cómo construir).

  3. Borre todo el contenido de la cinta.

  4. Una vez que se borre la cinta, vaya al paso 1 (es decir, el estado inicial de M).

Ahora si q se detiene, entonces METRO q seguirá dando vueltas, haciendo todo una y otra vez, por lo que cada estado se cumplirá infinitamente muchas veces , lo cual es más grande que 42 . Por otro lado si q no se detiene, entonces los estados que implementan el paso 3 se ejecutarán cero veces, que es menos de 42.

Entonces, si tenemos un algoritmo que decide el problema (3), entonces aplicándolo a METRO q nos dirá si q se detiene Y obviamente podemos escribir un programa que construya METRO q dado q .

Donde esto se complica es en asegurarse de que todos los estados en METRO q en realidad se verá durante una ejecución final de q . Puede ser que haya alguna característica de las máquinas de Turing que q en realidad no usa, tal vez nunca escribe un 1en la cinta y se mueve hacia la izquierda mientras hace la transición a un estado cuyo número es un múltiplo de 17. Y si nuestra máquina universal tiene un estado que solo se ejerce cuando la máquina que se simula hace exactamente eso, entonces estamos en problemas.

Una salida sería, después de haber programado el simulador para el paso 2 de METRO q , para encontrar una máquina fija PAG tal (a) cuando PAG se inicia en una cinta vacía, también se detendrá en una cinta vacía, (b) simulando PAG ejercita todos los estados del simulador particular que hemos escrito.

Entonces, para decidir si q paradas, forma METRO PAG ; q (dónde PAG ; q es una máquina que primero hace PAG y luego pasa al primer estado de q ) y pregunte si este tiene un estado que se visita como máximo 42 veces.

Con todo, esta prueba se siente más complicada de lo que debería ser. Quizás hay una construcción más simple que estoy pasando por alto.

...o tiene que haber un estado que haya sido visitado 42 veces?! Entonces, ¿el problema es solo una instancia específica del problema de la cinta en blanco y, por lo tanto, indecidible?
@eva: Sí a la primera parte de tu comentario, no a la segunda. El punto es que puedes decidir la propiedad simplemente simulando 42 norte + 1 pasos de la máquina y llevar la cuenta de cuántas veces se ve cada estado. O la máquina se detiene antes 42 norte + 1 , y en ese momento solo mirará los conteos para encontrar la respuesta, o todavía se está ejecutando en el paso 42 norte + 1 , en cuyo caso sabe que la respuesta debe ser "sí" incluso sin mirar los conteos.
Tenga cuidado en particular de que una instancia específica de un problema indecidible no tiene por qué ser indecidible. Por ejemplo, el problema de la detención es indecidible, pero si lo restringimos al caso específico de máquinas que no tienen un estado de detención, ¡se vuelve trivial!
¡Por supuesto! Eso tiene sentido, gracias... Intentaré "captar" por completo las respuestas 1 y 2 hasta que pase a la pregunta 3;)
Guau, gracias por la explicación sobre 3. No estoy muy seguro de poder imaginar cómo se vería la máquina P, pero definitivamente entendí la idea. La forma en que construiste los pasos 1 a 4, ¿es así como generalmente se hacen las reducciones? Parece que esto podría funcionar en múltiples problemas con pequeñas modificaciones como la de nuestro caso de asegurarse de que cada uno de los estados de MQ sea realmente visitado.
@eva: PAG normalmente sería una secuencia lineal de operaciones sin sentido como "escribir 1, mover a la izquierda, retroceder, borrar el 1, ....". Podemos construirlo iterativamente: en cada paso tienes un candidato PAG . Calcula cómo lo simula la máquina universal. Si se visitan todos los estados de la máquina universal, entonces hemos terminado. De lo contrario, elija un estado que no se visite, averigüe para qué sirve ese estado en primer lugar y arme una extensión para su candidato PAG que lo ejercerá. Enjuague y repita hasta que esté listo.
@eva: En cuanto a las reducciones, los cuatro pasos particulares aquí se eligen específicamente para el problema particular (3) que suponemos ( por una contradicción) se puede decidir. Hay un tema común aquí, ya que el problema que queremos demostrar que es indecidible toma una máquina de Turing como entrada , la reducción debe producir esa máquina de Turing como salida . Y cuando el problema del que estamos reduciendo también tiene que ver con las máquinas de Turing, entonces la reducción tiene que tomar un mecanizado de Turing como entrada . Entonces, es inherente a las condiciones de contorno que la prueba consistirá en describir cómo transformar un Turing...
... máquina q a otra máquina de Turing METRO q . Pero no es un hecho universal que esto tenga que hacerse incorporando una máquina universal; es una idea general muy útil para familiarizarse, pero no siempre es lo que funciona.
@HenningMakholm, por favor, ¿puede elaborar este párrafo? "Ahora, si Q se detiene, entonces MQMQ seguirá en bucle, haciendo todo una y otra vez, por lo que cada estado se cumplirá infinitamente muchas veces, lo que es más grande que 4242. Por otro lado, si QQ no se detiene, entonces los estados que implementan el paso 3 se ejecutarán cero veces, que es menos de 42".

Entonces, si cree que es indecidible , la reducción es del problema de detención al problema 2/3. El paso clave en esta prueba surge del hecho de que si los problemas 2/3 son realmente indecidibles, entonces puede tomar cualquier instancia del problema de detención y transferirla a una instancia del problema 2/3. Resuélvelo allí, lo que implica una solución al problema de detención original. Esta es la mejor manera en que puedo expresarlo sin revelar demasiada prueba.

máquina de turing con exactamente 42 estados / estado que se visita al menos 42 veces
RespuestasAquíPolítica de privacidad1y, 0v