¿Probabilidad de que una máquina de Turing sea universal?

Question

Elijo una máquina de Turing T con n estados y una cinta de entrada al azar.

¿Qué se puede probar sobre la probabilidad P_A(n) de que no sea decidible si T se detendrá para una entrada particular? ¿Qué se puede demostrar sobre P_B(n) que T es universal, es decir, que existe un algoritmo que toma una codificación obvia de una máquina de Turing arbitraria A (sin cinta de entrada) y la transforma en una entrada para mi máquina de Turing aleatoria, de modo que T se detiene con esta entrada si y sólo si A se detiene? En particular: ¿Se sabe que P_A(n) es estrictamente menor que P_B(n) para algún n?

Answer 1

La respuesta dependerá del modelo de máquina de Turing que haya adoptado.

Por ejemplo, esto es algo fácil de decir. Supongamos que sus máquinas de Turing tienen el alfabeto $\{0,1\}$ , un conjunto $Q$ de $n$ estados, un único estado de parada (no se cuenta dentro de $Q$ ), y la capacidad de mover la cabeza a la izquierda y a la derecha, de manera que un programa es una función $p:Q\times\{0,1\}\to (Q\cup\{\text{halt}\})\times\{0,1\}\times\{\text{left},\text{right}\}$ , donde $p(s,i)=(t,j,\text{left})$ significa que cuando en el estado $s$ símbolo de lectura $i$ el programa cambia al estado $t$ , escribe el símbolo $j$ y se mueve a la izquierda. En particular, para este modelo el número total de programas es $(4(n+1))^{2n}$ .

Consideremos ahora la colección de programas que no tienen transición al estado de parada. El número total de tales programas es $(4n)^{2n}$ y lo interesante aquí es que $$\lim_{n\to\infty}{(4n)^{2n}\over (4(n+1))^{2n}}=\lim_{n\to\infty}[{n\over n+1}]^{2n}=\frac{1}{e^2}$$ que es alrededor del 13,5%.

Así, para este modelo de computación, al menos el 13,5% de los programas no se detienen con ninguna entrada y no son universales.

El tema es divertido, porque en efecto estamos considerando el comportamiento de un programa aleatorio, donde cada nueva línea de programa se elige al azar entre todas las líneas de programa legales. Y este tipo de argumento es el tema principal de mi artículo (J. D. Hamkins y A. Miasnikov, The halting problem is decidable en un conjunto de probabilidad asintótica uno, Notre Dame J. Formal Logic 47, 2006. http://arxiv.org/abs/math/0504351 ), que surgió también en algunas algunas otras preguntas de mathoverflow: Resolver problemas NP en (normalmente) en tiempo polinómico tiempo polinial? , máquinas de Turing que leen toda la cinta? . El teorema principal de ese artículo es el siguiente.

Teorema. Hay un conjunto $A$ de la máquina de Turing (para máquinas con cinta infinita de un solo sentido, un solo estado de parada, cualquier alfabeto finito) tales que:

• Se puede decidir fácilmente si un programa está en $A$ es decidible en tiempo polinómico.
• Casi todos los programas están en $A$ la proporción de todos los $n$ -programas estatales que están en $A$ converge a $1$ como $n$ se hace grande.
• El problema de detención es decidible para los miembros de $A$ .

Por lo tanto, existe un procedimiento de decisión para decidir casi todos los instancia del problema de detención. La forma de probarlo es calcular, para cualquier entrada fija, la probabilidad de que una máquina de Turing muestre un comportamiento fatalmente trivializador (caer en el extremo izquierdo de la cinta antes de repetir un estado), y observar que de hecho esto ocurre con probabilidad $1$ . Básicamente, el comportamiento de una máquina de Turing aleatoria es lo suficientemente cercano a un paseo aleatorio como para que se pueda lograr el fenómeno de recurrencia de Polya.

Un corolario de esta prueba, respondiendo a su pregunta, es que para este modelo de computación, la probabilidad de que un $n$ -el programa estatal es un programa universal va a cero como $n$ se hace grande, ya que casi todos los programas exhiben el comportamiento trivializador, que es incompatible con ser universal. Además, el conjunto de programas con ese comportamiento es decidible.

El teorema puede extenderse a otros modelos de computación como el modelo con cintas infinitas de dos vías y detención determinado por la especificación de un subconjunto de los estados para ser estados de parada. En este modelo, como se puede adivinar, las máquinas se detienen muy rápidamente (ya que cada nuevo estado tiene 50% de posibilidades de detenerse), por lo que hay un gran conjunto de programas para los que el problema de detención es decidible por esta razón (se detienen antes de repetir un estado).

Permítame también mencionar, ya que usted preguntó no sólo sobre la probabilidad de detención, sino también sobre la probabilidad de decidibilidad de la parada, que todo conjunto computablemente enumerable conjunto $B\subset\mathbb{N}$ que no es computable admite infinitamente muchos $n$ para lo cual $n\notin B$ pero esto no es demostrable en cualquier teoría de fondo fijo que prefieras, como PA o ZFC o ZFC + grandes cardinales. La razón es simplemente que si la no pertenencia a $B$ eran demostrables para todos los suficientemente grandes $n$ entonces tendríamos un procedimiento de decisión de decisión para $B$ buscando $n$ para ser enumerado en $B$ o bien buscando una prueba de que $n$ no está en $B$ y esto contradice nuestra suposición de que $B$ no es decidible.

Así, todo conjunto no computable c.e. se encuentra en un halo de indecidibilidad: hay infinitos números $n$ que no están en $B$ pero que también es consistente con su teoría favorita de que están en $B$ .