¿Cuál es la máquina de Turing más pequeña donde se desconoce si se detiene o no?

31

Sé que el problema de la detención es indecidible en general, pero hay algunas máquinas de Turing que obviamente se detienen y otras que obviamente no. De todas las máquinas de turing posibles, ¿cuál es la más pequeña donde nadie tiene una prueba de si se detiene o no?

halting-problem Aaron
fuente

10

La respuesta depende de los detalles del modelo de máquina (número de símbolos, etc.). Según el artículo de Wikipedia sobre Busy Beaver, hay una máquina de 2 símbolos y 5 estados que no se sabe si se detiene o no.

Kaveh

1

Tenga en cuenta que la pregunta de Aaron no se trata de la capacidad de decisión de un idioma dado, sino de la existencia de una prueba de que una máquina específica de Turing se detiene. Para cualquier máquina de Turing, "su" problema de detención (si esta misma máquina se detiene en la entrada vacía) es "decidible": es Sí o No, y los dos idiomas {Sí} y {No} son decidibles. Esto es muy diferente de si uno tiene una prueba de que la máquina se detiene o no. Aaron, si quieres decir "¿cuál es la

más pequeña de tal manera que el lenguaje

detiene en

es indecidible", ¿puedes editar tu pregunta?

M

$M$

{w ∣ M

$\{w \mid M$

w}

$w\}$

Michaël Cadilhac

1

@ MichaëlCadilhac El problema de detención generalmente se interpreta como: "Dada una máquina

y una entrada

, ¿se detiene

para la entrada

?" no "Dada una máquina

, ¿

detiene todas las entradas?"

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

M

$M$

David Richerby

@DavidRicherby: Para mí, el problema de detención es el lenguaje de la máquina (códigos) que se detiene en la entrada vacía. Si no es el significado previsto aquí, creo que debería especificarse para disipar la posible confusión (ok, mi).

Michaël Cadilhac

Múltiples formas de estudiar el problema son válidas e interrelacionadas y, de hecho, hay una sutileza en distinguirlas que el interrogador no hizo.

vzn

38

Las máquinas de Turing más grandes para las cuales el problema de detención es decidible son:

(donde es el conjunto de máquinas de Turing con estados y símbolos). $TM(2,3), TM(2,2), TM(3,2)$ $TM(k,l)$ $k$ $l$

La capacidad de decisión de y está en el límite y es difícil de resolver porque depende de la conjetura de Collatz, que es un problema abierto. $TM(2,4)$ $TM(3,3)$

Véase también mi respuesta sobre teoría sobre máquinas Turing tipo Collatz y " Pequeñas máquinas Turing y competencia generalizada de castores ocupados " por P. Michel (2004) (en el que se conjetura que también es decidible). $TM(4,2)$

El comentario de Kaveh y la respuesta de Mohammad son correctos, por lo que para una definición formal de las máquinas Turing estándar / no estándar utilizadas en este tipo de resultados, ver Turlough Neary y Damien Woods trabajan en máquinas Turing universales pequeñas, por ejemplo, la complejidad de las máquinas Turing universales pequeñas: una encuesta (los Reglamentos de la Norma 110 son débilmente universales).

Marzio De Biasi
fuente

2

¿No es el problema de detención para cualquier conjunto finito de máquinas de Turing siempre decidible? Como solo hay muchas máquinas en

, debe ser posible construir una tabla de búsqueda que indique correctamente qué máquinas se detienen y cuáles no, por lo que debe haber una máquina de Turing que utilice esta búsqueda tabla para responder correctamente la pregunta.

T M (4, 2)

$TM(4, 2)$

Tanner Swett

2

@TannerSwett: Aquí consideramos el conjunto detención

o, en otras palabras, para los que las máquinas de Turing

es decidible (véase Michel papel).

{⟨ M, x ⟩ ∣ M halts on x}

$\{\langle M,x \rangle \mid M \text{ halts on } x\}$

H A L T_{M} = {x ∣ M halts on x}

$HALT_M = \{ x \mid M \text{ halts on } x\}$

Marzio De Biasi

32

Me gustaría agregar que hay algunas máquinas de Turing para las cuales el problema de detención es independiente de ZFC.

Por ejemplo, tome una máquina Turing que busca una prueba de contradicción en ZFC. Entonces, si ZFC es consistente, no se detendrá, pero no puede probarlo en ZFC (debido al segundo teorema de incompletitud de Gödel).

Por lo tanto, no solo se trata de no haber encontrado una prueba, a veces las pruebas ni siquiera existen.

Denis
fuente

ZFC? ¿Qué significa ZFC? Simplemente no puedo entenderlo por el contexto.

Acapulco

77

@Acapulco lmgtfy.com/?q=zfc&l=1

Sasho Nikolov

Jajaja Okay. Me lmgtfy'ed. Touchè. No pensé que serían iniciales que se relacionarían de manera única e inmediata con este tema. En cualquier caso, no creo que duela agregar una aclaración de cortesía "ZFC (teoría de conjuntos de Zermelo-Fraenkel)" la primera vez que se menciona, también para evitar la ambigüedad en caso de que exista. :)

Acapulco

16

@ Acapulco, consulte el recorrido y el centro de ayuda . Cualquier informático teórico sabría lo que significa ZFC, por lo que no es realmente necesario aclararlo.

Kaveh

1

2

$2$

5

Nadie tiene pruebas de si la máquina Universal Turing se detiene o no. De hecho, tal prueba es imposible como resultado de la indecidibilidad del problema de detención. La más pequeña es una máquina Turing universal de 2 símbolos y 3 símbolos que fue encontrada por Alex Smith por la cual ganó un premio de $ 25,000.

Mohammad Al-Turkistany
fuente

44

Sin embargo, tenga en cuenta que, de acuerdo con la página de Wikipedia citada, la prueba de la universalidad está en disputa. Además, este no es el modelo estándar de las máquinas de Turing: la máquina supuestamente universal no tiene un estado de detención, por lo que no puede simular ninguna máquina que se detenga, al menos en el sentido estándar de lo que hace una máquina de Turing universal.

David Richerby

2

@DavidRicherby: Creo que la universalidad débil de la regla 110 es bastante aceptada: requiere dos palabras diferentes repetidas a la izquierda y a la derecha de la entrada, y la condición de detención es la generación de un planeador especial (generado si y solo si la máquina simulada se detiene). Ver "Universalidad en autómatas celulares elementales" de Matthew Cook.

Marzio De Biasi

-4

una pregunta general inexacta pero razonablemente razonable que puede estudiarse de varias maneras técnicas particulares. hay muchas máquinas "pequeñas" medidas por estados / símbolos donde se desconoce la detención, pero no es posible una máquina "más pequeña" a menos que se presente una métrica justificable / cuantificable de la complejidad de una TM que tenga en cuenta tanto los estados como los símbolos (aparentemente nadie ha propuesto uno hasta ahora).

$x \times y$ $x$ $y$

$x,y$

vzn
fuente

2

No es necesario establecer una métrica teniendo en cuenta los símbolos y estados. Una vez que hay dos símbolos en la cinta, está claro que el problema de detención es indecidible para casi todos los números de estados; según recuerdo, es posible escribir una TM universal con solo cinco estados. Si supiéramos el límite exacto de la capacidad de decisión, estoy seguro de que sería fácil describir ese límite en términos de (# estados, # símbolos) pares.

David Richerby

la investigación de los castores ocupados de hecho implica encontrar pruebas de si las TM se detienen para las configuraciones iniciales con un pequeño número de estados, símbolos; Hay casos resolubles. si se quiere algo "más pequeño", se debe crear una métrica precisa que mida "pequeño". El punto anterior es que una métrica que solo involucra estados o símbolos solo puede considerarse engañosa en la medida en que representa el límite conocido que involucra a ambos (y máquinas que no se sabe que son universales). el límite de indecidibilidad en esta investigación no es "fácil" de especificar en términos de nada, esa es su naturaleza fundamental ...

vzn

1

2 \leq i \leq 4

$2\leq i\leq 4$

k_{i}

$k_i$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

David Richerby

nadie ha propuesto ninguna métrica hasta ahora. ningún límite importante en esta área es "trivial de describir" y uno esperaría que el escenario fuera imposible a través de Rices thm. Esto parece mostrar una falta de familiaridad con la investigación y la referencia citada que está interesada en la resolubilidad de las entradas para máquinas que son más pequeñas que las que se sabe que son universales (y se supone que no lo son). sus comentarios parecen centrarse en los límites de la máquina universal frente a los no universales, que no es lo mismo que los límites de la capacidad de decisión de los castores ocupados que se exploran, por ejemplo, en las referencias citadas (tanto las anteriores como las de Marzio).

vzn

x

$x$

y

$y$

x

$x$

y

$y$

¿Cuál es la máquina de Turing más pequeña donde se desconoce si se detiene o no?

Respuestas: