Me dieron una pregunta para demostrar que existe una máquina de Turing que resuelve la pregunta
¿Hay vida más allá de la Tierra?
y es decidible. En realidad no entiendo cómo demostrar que una máquina de Turing decide esto.
Gracias.
Esta es una pregunta con trampa, la idea es que la respuesta no depende de la entrada (o más bien, no tiene entrada; pero se suele suponer que las máquinas de Turing tienen una entrada implícita). Si la respuesta es SI entonces la máquina de Turing que imprime SI resuelve el problema. Lo mismo ocurre con la respuesta NO . Por supuesto, no sabemos que de estas dos máquinas de Turing resuelve el problema, pero sabemos que una de ellas lo hace.
Por el contrario, supongamos que queremos resolver el problema de detención de esta manera. Entonces se necesitaría una tabla en la que para cada programa se registrara si se detiene en la entrada vacía o no. Esta tabla es infinita, por lo que este enfoque no funciona.
En lugar de "no depende de la entrada" quizás sería más preciso decir que hay no es ninguna entrada al menos si por "entrada" nos referimos a los datos que indican a la máquina qué instancia del problema debe resolver, porque este problema sólo tiene una instancia.
Agradezco la explicación. Creo que esa pregunta en particular no es adecuada como ejemplo de una función de máquina constante.
¿Así que la máquina de Turing que resuelve el problema es decidible porque es una unión de 2 máquinas de Turing que son decidibles?
1) Demuestre que todos los universos posibles pueden ser codificados en una tira de cinta. Deberá demostrar que existe un número finito (aunque muy grande) de universos posibles: La edad del universo es aproximadamente 1,4*10^10 años. La distancia máxima que puede haber recorrido la luz desde el Big Bang es de aproximadamente 1,3*10^26 metros (incrementa 26 en uno o dos si quieres tener en cuenta la inflación cósmica) La longitud de Planck 10^-35 metros, lo que nos da una anchura máxima del universo de 2 * 1,3*10^26 * 10^35 = 2,6 * 10^58. El cubo que para el número de lugares cuantificables en el universo = 1,8 * 10^175. Redondeemos a 10^200, sólo porque es un buen número redondo. Determina el número de estados en los que puede estar cada lugar cuantificable del universo (por ejemplo, vacío, contiene una cadena de tipo x, y, z, etc.). Que el número de estados sea S. Ahora tienes el número de universos posibles con la misma edad / tamaño que el nuestro como S^(10^200). Es un número grande, pero sigue indicando un número finito de universos posibles.
2) Dado 1, demuestre que el conjunto de todos los universos posibles es contable.
3) Formar un conjunto de cintas, compuesto por todas las que codifican universos que contienen vida más allá de la Tierra.
4) Tus lecciones y ejercicios anteriores sobre máquinas de Turing deberían haberte enseñado a demostrar que, dada una colección finita de cintas, existe una máquina de Turing que se detiene y produce "SÍ" en esas cintas y en ninguna otra. Como mínimo, una máquina de Turing que realice una comparación de cadenas en todos los conjuntos de datos "SÍ" será suficiente.
Además, esto supone que puedes codificar el universo actual en una cinta.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
5 votos
Argumentaré que no es decidible. Paso 1: destruir toda la vida del universo. Paso 2: poner en marcha la máquina de Turing. Paso 3: lanzar un astronauta al espacio profundo. Paso 4: ejecutar la máquina de Turing de nuevo, desde el mismo estado inicial. Como las salidas dadas en los pasos 2 y 4 eran las mismas, y las respuestas correctas eran diferentes, la máquina de Turing no resuelve correctamente el problema. (Las preguntas con trampa merecen respuestas con trampa).
0 votos
La respuesta correcta es una pobre broma sobre una definición descuidada. Una definición adecuada de "decidible" sería que hay un algoritmo que decide si la afirmación dada es verdadera y no que hay un algoritmo que da el resultado correcto, lo cual es siempre el caso porque un algoritmo produce "no" y el otro "sí". Esta definición es completamente inútil porque, en este sentido, casi TODAS las preguntas sí-no son decidibles.