Para cualquier idioma

Estoy tratando de encontrar una prueba de lo siguiente:

Para cualquier idioma , existe un lenguaje de tal que pero B . $A$ $B$ $A \le_{\mathrm{T}} B$ $\nleq_{\mathrm{T}} A$

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

¡Gracias!

computability reductions undecidability usuario1354784
fuente

¿Qué tal

B = N P^{A}

$B = NP^A$

Eugene

Pensar en el problema de la parada de las máquinas de Turing con Oracle

A

$A$

Willard Zhan

@ 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

representa un TM Oracle con Oracle

vez de una MT normal.

A

$A$

α \in Σ^{*}

$\alpha\in\Sigma^*$

M_{α}

$M_\alpha$

A

$A$

Willard Zhan

@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

@ 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í.

B = A_{T M}

$B=A_{\mathrm{TM}}$

David Richerby

Respuestas:

Sea $B=A'$ , el salto de Turing de $A$ . Este es un resultado básico en la teoría de los grados de Turing.

Bjørn Kjos-Hanssen
fuente

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 $A$ solo puede calcular contablemente muchos idiomas: una sola máquina de Turing solo puede producir una reducción de un idioma dado $A$ , 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 $B\not\le_TA$ .

Ahora combinamos esto con el Turing unirse a : lenguajes dados $X,Y$ , al unirse a $X\oplus Y$ 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 $X\oplus Y=\{2i: i\in X\}\cup\{2i+1: i\in Y\}$ - pero la característica importante es que $X\oplus Y\ge_TX,Y$ (y de hecho es sulímite superior $\le_T$ menos).

Entonces podemos aplicar lo anterior, para obtener:

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

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