Estoy interesado en encontrar una prueba simple (sin el teorema de la jerarquía de tiempo) de lo siguiente:
Para mostrar que hay una recurrente establezca que no está en clase de $\mathsf{P}$.
Respuesta
¿Demasiados anuncios?
La clase $\mathsf P$ es efectivamente enumerable: Si definimos $$ A_k = \{n\mid \text{Turing machine number $k$ accepts $n$ in at most $n^k+k$ steps}\}$$ después de cada juego en $\mathsf P$ $A_k$ algunos $k$.
Esto funciona debido a que cada una de las polinomio es pointwise más pequeño que algo de la forma $x^k+k$, y cada máquina de Turing (en efecto) arbitrariamente grandes índices, es decir, podemos añadir inaccesible a los estados a que hasta que el índice es tan grande como queramos. (Podríamos evitar este razonamiento en el costo de la introducción de un tupling función y las correspondientes proyecciones).
Ahora podemos diagonalize a encontrar $$ D = \{ n \mid \text{Turing machine number $n$ does not accept $n$ in at most $n^n+n$ steps}\} $$ lo que es claramente recursiva, sino por la construcción difiere de todas las $A_k$s y por lo tanto no es en $\mathsf P$.
Si esta prueba es significativamente diferente de la aplicación de la jerarquía de tiempo es el teorema de, supongo, en el ojo del espectador.
