¿Por qué es esto una máquina de Turing no válida?

Question

Mientras que haciendo revisión de exámenes que estoy teniendo problemas para responder a la siguiente pregunta del libro, "Una Introducción a la Teoría de la computación" por Sipser. Desafortunadamente no hay solución a esta pregunta en el libro.

Explica por qué los siguientes no es una máquina de Turing legítima.

M = {

La entrada es un polinomio p sobre las variables x1, ..., xn

1. Trate todas las posibles configuraciones de x1, ..., xn a valores enteros
2. Evaluar p en todos estos ajustes
3. Si cualquiera de estos ajustes se evalúa a 0, aceptar; de lo contrario rechazar. }

Esto me está volviendo loco! Sospecho que es porque el conjunto de los enteros es infinito? No exceda de alguna manera este tamaño permitido del alfabeto?

Answer 1

A pesar de que esta es una manera bastante informal de la descripción de una máquina de Turing, yo diría que el problema es uno de los siguientes:

• otherwise reject - Estoy de acuerdo con Welbog en eso. Puesto que usted tiene un conjunto infinito numerable de posibles ajustes, la máquina nunca puede saber si un entorno en el que se evalúa a 0 está por venir, y el bucle de voluntad para siempre si no se encontró ninguna - solamente cuando se encuentra una configuración tal, la máquina se puede detener. Esta última afirmación no sirve para nada y nunca será verdad, a menos que, por supuesto, se limita la máquina a un conjunto finito de números enteros.

• El orden código: Me gustaría leer este pseudocódigo como "primera escritura todas las configuraciones posibles abajo, a continuación, evaluar p en cada uno" y no es tu problema: Una vez más, por tener un conjunto infinito de posibles ajustes, ni siquiera la primera parte será nunca termina, porque nunca hay un último ajuste de escribir y continuar con el siguiente paso. En este caso, no puede ni siquiera la máquina nunca decir "no hay ninguna configuración 0", pero ni siquiera se puede empezar a evaluar para encontrar uno. Esto, también, sería resuelto mediante la limitación del conjunto entero.

De todos modos, no creo que el problema es el tamaño del alfabeto. Que no se usará un alfabeto infinita, ya que sus números enteros pueden ser escritos en decimal / binario / etc, y los que sólo se utilice una (muy) alfabeto finito.

Answer 2

Estoy un poco oxidado en las máquinas de Turing, pero creo que su razonamiento es correcto, es decir, el conjunto de los enteros es infinito, por tanto, no se puede calcular a todos. No estoy seguro de cómo demostrar esta teoría, sin embargo.

Sin embargo, la forma más fácil de obtener su cabeza alrededor de las máquinas de Turing es recordar "Cualquier cosa que un ordenador real puede calcular, una máquina de Turing también puede calcular.". Por lo tanto, si se puede escribir un programa que da un polinomio puede resolver sus 3 preguntas, usted será capaz de encontrar una máquina de Turing que también puede hacerlo.

Answer 3

Creo que el problema está en la última parte: otherwise reject.

Según fundamentos conjunto numerable , cualquier espacio vectorial sobre un conjunto numerable es sí contable. En su caso, usted tiene un espacio vectorial sobre los números enteros de n tamaño, que es contable. Por lo que su conjunto de los enteros es numerable y por lo tanto es posible probar todas las combinaciones de ellos. (Es decir, sin perder cualquier combinación.)

Además, el cálculo de la consecuencia de p en un conjunto dado de insumos también es posible.

Y entrar en un estado de aceptación cuando p evalúa a 0 también es posible.

Sin embargo, puesto que hay un número infinito de vectores de entrada, puede no Rechazar la entrada. Por lo tanto, ninguna máquina de Turing puede seguir todas las reglas definidas en la pregunta. Sin esa última regla, es posible.