El problema de detención acotada es decidible. ¿Por qué esto no entra en conflicto con el teorema de Rice?

Una declaración del teorema de Rice se da en la página 35 de "Complejidad computacional: un enfoque moderno" (Arora-Barak):

Una función parcial de $\{0,1\}^*$ a $\{0,1\}^*$ es una función que no está necesariamente definida en todas sus entradas. Decimos que una TM $M$ calcula una función parcial $f$ si por cada $x$ en la que se define $f$ , $M(x) = f(x)$ y por cada $x$ en la que $f$ no está definida $M$ entra en un bucle infinito cuando se ejecuta en la entrada $x$ . Si $S$es un conjunto de funciones parciales, definimos $f_S$ ser la función booleana que en la entrada $\alpha$ salidas 1 si y sólo si $M_\alpha$ calcula una función parcial en $S$ . El teorema de Rice dice que para cada no trivial $S$, la función $f_S$ no es computable.

Wikipedia afirma que los idiomas de las máquinas de tiempo limitado están COMPLETAMENTE completos. Supongo que este lenguaje se parece a $\{(\alpha,x,n) : M_\alpha$ acepta $x$ en menos de $n$ pasos $\}$ . Deje que $M$ sea ​​un DTM que decida este lenguaje limitado en tiempo exponencial. Parece que este DTM está decidiendo algunas propiedades para TODAS las máquinas de turing, por lo que mi intuición me dice que el teorema de Rice impide esa decisión. Pero obviamente $M$ calcula una función total.

¿Qué me estoy perdiendo acerca de la relación entre este lenguaje y el teorema de Rice?

El idioma

$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$

no es un conjunto de índices, es decir, no tiene la forma

$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$

para algún conjunto de (recursivas parcial) funciones , con la función (parcial) calculada por TM . El teorema de Rice hace declaraciones solo sobre tal ; muchas reformulaciones "intuitivas" no son útiles. Ver también aquí .f M M L $P$$f_M$$M$$L_P$

Tenga en cuenta que esto no es solo un detalle técnico aquí. El teorema de Rice no se aplica a

$\qquad L = \{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \}$ ,

ya sea. ¿Puedes ver por qué?

Para cada máquina en se puede construir fácilmente muchas máquinas que aceptan el mismo idioma, pero se ejecutan durante más de pasos, y por lo tanto no están en . Por lo tanto, no es un conjunto de índices.⟨ M ⟩ L $L$$\langle M \rangle$$L$$L$

$L$ es decidible, usando el mismo argumento que para el lenguaje original que estamos discutiendo.

El teorema de Rice dice que no se puede decir nada sobre el comportamiento final de un programa cuando se deja ejecutar hasta el infinito; no importa cómo clasifique los programas, habrá dos programas que convergerán en el mismo comportamiento final (función calculada ) aunque los haya clasificado de manera diferente.

Pero dejar que los programas se ejecuten hasta el infinito es esencial. Para saber qué hacen en los primeros pasos, puede simularlos para los primeros pasos y luego terminar dando su veredicto sobre cómo se comportó el programa. Una simulación similar hasta el infinito no funciona porque si el programa simulado nunca termina en una entrada simulada, su clasificador también divergerá, en lugar de proporcionar una clasificación.$n$$n$

Primero, las palabras en su idioma no son codificaciones de máquinas, contienen más información, por lo que no puede aplicar directamente el teorema de Rice. Dicho esto, el teorema de Rice habla de la imposibilidad de razonar sobre la función calculada por una máquina de Turing (es decir, si se encuentra en algún conjunto ). Este no es el caso aquí, ya que como mencionó Raphael, existen dos máquinas que calculan la misma función, pero una se encuentra en su idioma y la otra no (aquí estoy ignorando el problema sintáctico, y me olvido de el hecho de que son parte de la entrada). El punto es que la propiedad que está viendo aquí es mecánica y no semántica (las máquinas pueden calcular la misma función, pero de una manera diferente).M , M ′ x , $S$$M,M'$$x,n$

El teorema de Rice dice que, para cualquier conjunto no trivial de idiomas, el conjunto de máquinas de Turing que reconocen un idioma en  es indecidible. Wikipedia dice que un lenguaje específico es decidible. Entonces no hay contradicción.$\mathcal{L}$$\mathcal{L}$