Para cualquier idioma

9

Estoy tratando de encontrar una prueba de lo siguiente:

Para cualquier idioma , existe un lenguaje de B tal que A T B pero B T A .UNAsiUNATsiTUNA

Estaba pensando en dejar que sea A T M , pero me doy cuenta de que no todos los idiomas son Turing reducibles a A T M , por lo que A T B no se mantendría. ¿Qué otra opción de B tengo que me permita escribir una TM que use un oráculo para que B decida A ?siUNATMETROUNATMETROATBBBA

¡Gracias!

usuario1354784
fuente
¿Qué tal ? B=NPUNA
Eugene
3
Pensar en el problema de la parada de las máquinas de Turing con Oracle . UNA
Willard Zhan
2
@ user1354784 Las máquinas de Turing con Oracle se pueden enumerar. Así que trate de utilizar la diagonalización estándar, donde el único cambio es que para cada α sigma * , M α representa un TM Oracle con Oracle Una vez de una MT normal. UNAαΣMETROαUNA
Willard Zhan
1
@DavidRicherby Sí, pero B no está arreglado, está construido sabiendo qué es A. Si se nos da algo de A, construimos un B que acepta cada oráculo TM con un oráculo para este A específico que acepta cadenas en A. Si se nos da una A diferente, la lista de TM en B será diferente.
user1354784
1
@ user1354784 Exactamente. Quise decir ese comentario como otra explicación de por qué no podemos tomar como usted sugirió (y ya rechazó, por una razón diferente) en su pregunta. Olvidé explicar que ese era el punto que estaba haciendo, perdón por la confusión allí. si=UNATMETRO
David Richerby

Respuestas:

1

Sea si=UNA , el salto de Turing de UNA . Este es un resultado básico en la teoría de los grados de Turing.

Bjørn Kjos-Hanssen
fuente
1

Antes de sumergirnos en la buena respuesta, es decir, que podemos relativizar el problema de detención para asignar a cada idioma X un idioma X tal que (entre otras cosas) X<TX , vale la pena ver la tonta respuesta:

  • Cantor demostró que hay innumerables idiomas.

  • Pero cada idioma específico UNA solo puede calcular contablemente muchos idiomas: una sola máquina de Turing solo puede producir una reducción de un idioma A dadoUNA , y solo hay muchas máquinas de Turing.

De hecho, sabemos, sin hacer ningún trabajo serio, que:

Para todos los idiomas A , la mayoría (= todos menos cantidad numerable) lenguas B satisfacen BTUNA .

Ahora combinamos esto con el Turing unirse a : lenguajes dados X,Y , al unirse a XY consiste en "entrelazado" X e Y . Hay varias formas de definirlo, por ejemplo, pensando en X e Y como conjuntos de elementos naturales, generalmente dejamos que XY={2i:iX}{2i+1:iY} - pero la característica importante es que XYTX,Y (y de hecho es sulímite superiorT menos).

Entonces podemos aplicar lo anterior, para obtener:

Para todos los idiomas A , la mayoría (= todos menos cantidad numerable) lenguas B satisfacen A<TAB .


Esto plantea la cuestión de dar una prueba no estúpida , es decir, una forma natural de producir un lenguaje estrictamente más complicado que uno dado, y para eso es el salto de Turing; pero vale la pena entender este argumento no constructivo por sí solo.

Noah Schweber
fuente