Muestra que para cada idioma existe un lenguaje más difícil.

Question

Me encontré con este problema que no pude averiguar ... para todos los idiomas $ a $ , se supone que hay un idioma $ b $ tal que:

$$ A \ leq_t b $$

pero:

$$ B \ no \ leq_t a $$

Si es $ a \ leq_tb $ y $ b \ leq_t a $ , esto es fácilDado que podemos simplemente dejar que $ b:=bar {a} $ , pero para lo anterior no pude pensar en nada.¿Alguna ayuda?

Answer 1

Hay algunas formas de abordar esto.

Se puede usar un argumento de conteo para mostrar que para cada $ A $ no existe $ B $ tal que $ b \ nleq_t a $ . Deje $ l_a={b | B \ le_T A \} $ denota el conjunto de todos los idiomas reducible a $ A $ . Demostrar que $ f: L_A \ rightarrow \ mathbb {N} $ que mapea idiomas $ B \ en L_A $ a $ n $ tal que $ m_n $ es una reducción de $ B $ a $ a $ es una inyección, y concluyen que existe una fuera del lenguaje de $ L_A $ . A continuación, desea que sea comparable a $ a $ . Podemos obtener un idioma de este tipo con el Operador de Único:

$ A \ sqcup B={0 W | w \ en A \} \ taza \ {1w | w \ en B \}. $

lo dejo a usted para demostrar que $ A \ sqcup B $ es el extremo superior de $ A, B $ , es decir, $ a, B \ le_T a \ sqcup B $ y, además, para cada $ L $ tal que $ A, B \ le_T L $ tenemos $ A \ sqcup B \ le L $ < / SPAN> (solo se preocupa por el primero). Demostrar que si $ B \ nleq_T A $ después $ A \ sqcup B \ nleq_T A $ .

Otra forma de probar esto es utilizar la salto operador . Hay que introducir la noción de máquina oráculo y, a continuación, mostrar que $ b=\ \ \ {\ izquierda (m ^ a, w \ derecha) | \ text {$ M ^ A $ detiene en $ w $} \ right \} $ es un lenguaje estrictamente con más fuerza. La prueba es idéntica a la indecisión del problema de la parada normal, solo que ahora mostramos la propiedad más fuerte que ninguna máquina con acceso a Oracle a $ A $ puede decidir $ B $ .

También puede construir directamente tal idioma a través de la diagonalización. Define $ b=izquierda {n | M_n (n) \ notin a \ derecha \} $ . Hemos construido $ B $ tal que cualquier función computable $ m_n $ deja de ser una reducción de $ B $ a $ a $ sobre al menos una entrada (específicamente, la codificación de la reducción). Ahora puede usar el Operador de Único para hacerlos comparables.