La pregunta no es decidable, desde la detención problema se reduce a ella.
Supongamos que tenemos una máquina de Turing $M$ y queremos determinar si se detiene en la entrada 0. El cese de cálculo puede ser descrito como una secuencia finita finita TM configuraciones, de tal manera que la configuración inicial se muestra el adecuado para M y cada paso de la configuración de la siguiente manera el cómputo de las reglas especificadas por M y la configuración final muestra la máquina en el cese de configuración. Estas propiedades de una secuencia de configuraciones que puede ser descrito en una sola instrucción $\varphi$, utilizando un lenguaje que nos permite hablar de las células de la cinta y de sus contenidos y la posición de la cabeza de una configuración determinada y así sucesivamente.
Por lo tanto, M se detiene si y sólo si $\varphi$ tiene un modelo finito.
Finalmente, podemos organizar los detalles, de manera que $\varphi$ trivialmente tiene una infinita modelo. Supongamos que $\varphi$ describe las configuraciones de tal manera que una vez que la máquina se ha detenido, simplemente podemos repetir la detención de configuración en la siguiente etapa. Es decir, $\varphi$ debe afirmar que el sucesor pasos de cálculo que funcione correctamente, si el cálculo no ha cesado, pero si lo tiene, entonces la siguiente configuración sólo se copia la anterior como un duplicado exacto. Ahora, si M no se puede detener, se puede generar una secuencia infinita de las configuraciones correspondientes para que, y a continuación, añadir otra $\mathbb{Z}$-bloque de configuraciones y todas de la misma, mostrando un (falso) detener la configuración. Este será un infinito modelo de $\varphi$.
Por lo tanto, para esta $\varphi$, podemos ver que $M$ detiene si y sólo si la respuesta a su pregunta es no. Por lo que su investigación no es el de pedir a un decidable pregunta.
