¿Cuáles son algunos de los ejemplos más interesantes de problemas indecidibles sobre las máquinas de Turing?

Me he divertido mucho aquí en Quora con la mordaza sobre “Por qué la teoría de la computabilidad dice que estás manguera”. Esta será la sexta entrega, pero primero déjame dar un resumen rápido de las anteriores.

En mi primera respuesta en esta serie, di un teorema encantador que muestra que casi cualquier propiedad que te pueda interesar es indecidible para grupos finitamente generados. Por ejemplo, no hay algoritmos que determinen las respuestas a “¿Es [matemática] G [/ matemática] finita?”, “¿Es [matemática] G [/ matemática] cíclica?”, “Es [matemática] G [/ matemática] ] abelian? ”o“ ¿[math] G [/ math] es generado por menos de 5 elementos? ”
En la segunda respuesta, mostré que no hay un algoritmo que acepte una serie convergente y genere si el límite es algebraico o no.
En la tercera respuesta, señalé que no existe un algoritmo que acepte una serie convergente y devuelva un algoritmo que escupirá la expansión decimal del límite. (No probé esto, aunque di algunas referencias de cómo uno podría hacerlo).
En la cuarta respuesta, probé que no hay un algoritmo que acepte una serie y devuelva si converge o no.
En la quinta entrega, probé que no hay un algoritmo que acepte dos números irracionales y determine si el producto es irracional.

Hoy, voy a demostrar algo aún más decepcionante: no hay un algoritmo que acepte un número computable (es decir, un número real especificado por un algoritmo que escupe el número real con la precisión que quiera) y devolverá si es cero o no!

A primera vista, esto parece completamente imposible, ¿cómo es posible que ni siquiera se pueda saber si un número computable es cero o no? Pero es verdad; si pudiera escribir un algoritmo que haga esto, podría resolver el problema de Detención. Aquí hay una prueba.

Elija cualquier programa P y defina [math] 0 \ leq \ epsilon <1 [/ math] de la siguiente manera: el dígito [math] n [/ math] -th en la expansión decimal de [math] \ epsilon [/ math] es [matemática] 1 [/ matemática] si el programa P se detiene después de [matemática] n [/ matemática] pasos, y es [matemática] 0 [/ matemática] de lo contrario. Claramente, [math] \ epsilon [/ math] es computable; simplemente ejecute el programa P el tiempo suficiente y habrá determinado [math] \ epsilon [/ math] con la precisión que desee.

Por otro lado, [math] \ epsilon = 0 [/ math] si y solo si P no se detiene. Por lo tanto, cualquier algoritmo que pueda decirle si [math] \ epsilon = 0 [/ math] también le dice si P se detiene o no. Es decir, tenemos una solución al problema de detención. Esto es imposible: ergo, no hay un algoritmo que haga lo que queremos.

informáticaInformática teóricaMáquina de TuringPruebasTeoría de la computación

Cómo calcular el número de subsecuencias distintas de una palabra dada de una longitud dada

¿Cuál es el significado de los lenguajes regulares [matemática] \ omega [/ matemática] en informática?

¿Qué es una introducción a vista de pájaro a la teoría de grafos?

Cómo probar la independencia entre variables continuas

¿Cuál es la diferencia entre problemas decidibles e indecidibles en teoría de la computación?

En 2006, aprendí que el valor de una PC solo dura 5 años. ¿Qué te parece ahora?

No soy un matemático fundamental, y no estoy exactamente seguro de lo que se necesita para ser indecidible. Así que solo mencionaré mi problema favorito de Turing: el castor ocupado: Wikipedia. Dada una máquina de Turing con n estados y solo los símbolos 0/1, ¿cuántos 1s puede escribir en cinta (inicialmente cero) antes de detenerse?

Puede pensar que no debería ser demasiado difícil calcular eso para valores pequeños de n, y el resultado nunca puede ser tanto, digamos [matemática] 2 ^ n [/ matemática] más o menos?

Aquí están los pequeños valores conocidos:

BB (1) = 1
BB (2) = 6
BB (3) = 21 (Lin y Rado 1965)
BB (4) = 107 (Brady 1975)

Hasta aquí todo bien. ¿Después de esto?

El actual campeón de castores ocupados de 5 estados produce 4098 1s, usando 47176870 pasos (descubiertos por Heiner Marxen y Jürgen Buntrock en 1989), pero quedan cerca de 40 máquinas con un comportamiento no regular que se cree que nunca se detendrán, pero que aún no se han detenido. Se ha demostrado que funciona infinitamente.

En este momento, el campeón récord de 6 estados produce más de [matemáticas] 3.5 \ veces 10 ^ {18267} [/ matemáticas] 1s, utilizando más de [matemáticas] 7.4 \ veces 10 ^ {36534} [/ matemáticas] pasos (encontrado por Pavel Kropitz en 2010). Como se señaló anteriormente, estas son máquinas de Turing de 2 símbolos.

Una extensión simple de la máquina de 6 estados conduce a una máquina de 7 estados que escribirá más de [matemática] 10 ^ {10 ^ {10 ^ {10 ^ {18705352}}}} [/ matemática] 1s en la cinta, pero indudablemente hay máquinas de 7 estados mucho más ocupadas.

Entonces eso crece bastante rápido. De hecho, crece más rápido que cualquier función computable y, por lo tanto, es indiscutible.

Y luego está esto: el número 8000 de Busy Beaver elude la teoría de conjuntos ZF donde los autores prueban que en algún lugar alrededor de 8000 el número BB se vuelve indecidible bajo los axiomas de la teoría de conjuntos.

Victor Eijkhout

Aquí hay algunos problemas interesantes que han demostrado ser indecidibles. (Un problema es indecidible si es imposible escribir un programa de computadora para resolverlo).

El ejemplo más famoso se llama problema de detención. El brillante británico, Alan Turing, demostró en 1936 que es imposible escribir un programa que diga si algún programa terminará en todas las entradas. Este habría sido un programa maravilloso, ya que no queremos escribir programas que no terminen.
Aquí hay un problema que los matemáticos no quieren resolver. Dada una proposición matemática bien definida sobre números naturales, escriba un programa que indique si la proposición es verdadera o no. Los matemáticos pueden relajarse, porque es imposible escribir dicho programa. Por lo tanto, no se irán a la quiebra pronto.
Supongamos que tenemos un programa para resolver un problema. Esto significaría que el problema es decidible. Pero ahora queremos el programa más corto que resuelva exactamente el mismo problema. (Por ejemplo, sabemos cómo factorizar números. Pero podríamos querer el programa más corto que factorice números). La mala noticia es que es imposible escribir un programa de “obtener el programa más corto”.
Más importante que el programa más corto es encontrar el programa más rápido que resuelva un problema que sea decidible. Tomemos el problema de factorizar nuevamente. Sabemos cómo factorizar un número, pero no sabemos qué tan rápido podemos factorizar. Por ejemplo, si N es el producto de dos números primos de 300 dígitos, factorizar N sin conocer los números primos puede llevar cientos, miles o incluso millones de años. Por lo tanto, nos gustaría saber la forma más rápida de factorizar. Desafortunadamente, no podemos escribir un programa que siempre brinde la forma más rápida de resolver un problema. Los matemáticos están trabajando duro tratando de encontrar formas cada vez más rápidas de factorizar números. Si alguna vez encuentran una forma realmente rápida de hacerlo, algunos de nuestros sistemas de cifrado más importantes pueden romperse.
¿Qué tal el problema de “¿Debería darle un beso de buenas noches?”. Si alguien resuelve esto, avíseme de inmediato.

Estudio gratuito

Máquina de Turing: teoría de la computación | Estudio libre9

Una computadora de propósito general puede programar para resolver diferentes tipos de problemas.
El cajero automático también puede comportarse como una computadora de uso general.
Una máquina Turing universal es una máquina Turing Tu que funciona de la siguiente manera.
Se supone que recibe una cadena de entrada de la forma e (T) e (z) , donde T es una TM arbitraria, z es una cadena sobre el alfabeto de entrada de T , y e es una función de codificación cuyos valores son cadenas en {0 , 1} *. El cálculo realizado por Tu en esta cadena de entrada satisface las siguientes dos propiedades: Tu acepta la cadena e (T) e (z) si y solo si T acepta z . Si T acepta z y produce la salida y , entonces Tu produce la salida e (y )
UTM debería poder simular todas las máquinas de Turing. La simulación de un Turing implicará: Codificar el comportamiento de un TM particular como un programa. Ejecución del programa anterior por UTM.