Este es un problema con un sorprendente y única historia. Ver la encuesta
Marcus Schaefer: Una visita guiada a un mínimo de los índices más corto y descripciones. Arch. De matemáticas. Registro de. 37(8): 521-548 (1998)
para más discusión. Una prueba de que el problema no es el núcleo puede ser extraído de la página 6 de la encuesta. Por comodidad voy a dar un argumento aquí. Por desgracia, no es tan simple como el "no-RE" de la prueba!
Vamos a mostrar una reducción de Turing $L_{ALL}$ = { $ M~|~L(M) = \Sigma^{\star} $} a $L_{min}$, lo cual es suficiente ya que $L_{ALL}$ es completa para el segundo nivel de la jerarquía aritmética (lo que implica que no es obligatorio). Intuitivamente, esto significa que dado un oracle para $L_{min}$ podríamos decidir la suspensión problema para las máquinas que han oráculos a detener el problema. Un núcleo del lenguaje no tienen esta propiedad.
Deje $\hat{M}$ ser el lexicográficamente primera máquina que no acepta entradas, en algunas de codificación de las máquinas.
En primer lugar, observamos que, dado un oráculo para $L_{min}$, que efectivamente se puede determinar si $M(M)$, se detiene o no, para un determinado $M$. (Recordemos que esto es suficiente para determinar si $M(x)$, se detiene o no, por $M$, $x$.)
Definir una máquina de $N_M$ que en la entrada de $t$, simula $M(M)$ a a $t$ pasos y se detiene iff la simulación se detiene. Para determinar si $M(M)$ detiene, hacer una lista de ${\cal L}$ de todas las máquinas de $M' \neq \hat{M}$ $M' \leq N_M$ tal que $M' \in L_{min}$. Esta lista puede calcularse mediante un oráculo para $L_{min}$. Observar que todas esas máquinas de aceptar al menos una entrada, ya que se excluyeron $\hat{M}$, y todos ellos son mínimas. A través de la vinculación, que efectivamente se puede encontrar enteros $t'$ de manera tal que cada una de las $M'(M')$ detiene en $t'$ pasos. Deje $t''$ ser el más grande de $t'$. A continuación, $M(M)$ detiene iff $M(M)$ se detiene en la mayoría de los $t''$ pasos.
Ahora que podemos decidir la suspensión problema, nos volvemos a calcular una función de la versión de $L_{min}$: dado un oráculo para $L_{min}$, se puede dar salida a la mínima equivalente de la máquina de $M'$ a la entrada de $M$. Si $M \in L_{min}$ esto es fácil. De lo contrario, hacemos una lista de ${\cal L}$ de todas las máquinas que están en $L_{min}$ y son más pequeños que los $M$. Entonces empezamos a calcular, por el aumento de las entradas de $x$, poco tablas indicando la aceptación/rechazo de comportamiento de todas las máquinas en ${\cal L}$, en las entradas visto hasta ahora. (Podemos hacer esto porque podemos resolver la suspensión problema con el oráculo!) Cuando nos encontramos con que una máquina de $M''$ diferencia en una entrada de $M$, lo eliminamos de ${\cal L}$. Si $M$ no es mínima, al final habrá una sola máquina $M'$ a la izquierda que todavía no difería de la de $M$, ya que todas las máquinas en ${\cal L}$ son mínimos. Si $M$ no es mínima, a continuación, esta $M'$ debe ser la mínima de la máquina.
Finalmente, definimos una máquina de $N$ que reconoce a $L_{ALL}$ con un oráculo para $L_{min}$. Deje $M_{ALL}$ ser el mínimo máquina de Turing que acepta todo. Si la entrada de $M$ es de menos de $M_{ALL}$, la salida NO. ($M$ debe rechazar algo.) Otra manera de calcular el mínimo de la máquina equivalente a $M$. Si $M = M_{ALL}$, la salida de SÍ, de lo contrario, la salida NO. Nota:$L(N) = L_{ALL}$.
