Mostre que para cada idioma existe uma linguagem mais difícil

Question

Eu me deparei com este problema que não consegui descobrir ... Para cada idioma $ a $ , é suposto ser uma linguagem $ B $ tal que:

$$ A \ leq_t b $$

mas:

$$ B \ não \ leq_t a $$

Se for $ a \ leq_tb $ e $ b \ leq_t A $ , isso é fácilComo podemos simplesmente deixar $ b:=bar {a} $ , mas para o acima, não consegui pensar em nada.Qualquer ajuda?

Answer 1

Existem algumas maneiras de abordar isso.

Você pode usar um argumento de contagem para mostrar que para cada $ a $ existe $ b $ De tal modo que $ b \ nleq_t a $ . Deixe $ l_a= {B | B \ le_t a \} $ denotam o conjunto de todos os idiomas redutible para $ a $ . Mostrar que $ f: l_a \ righttarrow \ mathbb {n} $ que mapas idiomas $ b \ in l_a $ para $ n $ tal que $ m_n $ é uma redução do recipiente de matemática $ B $ para $ a $ é uma injeção e concluir que existe uma linguagem fora da $ L_a $ . Em seguida, você quer compará-lo para $ a $ . Podemos obter essa linguagem com o operador de junção:

$ a \ sqcuço b={0w | w \ in a \} \ copo \ {1w | w \ in b} $ . Deixo para você mostrar que $ a \ sqcup b $ é o menor limite superior para $ a, B $ , ou seja $ a, b \ le_t a \ sqcup b $ e adicionalmente para cada $ l $ tal que $ a, b \ le_t l $ temos $ a \ sqcup b \ le L $ < / span> (você só se importa com o primeiro). Mostrar que se $ b \ nleq_t a $ então $ a \ sqcup b \ nleq_t A $ . .

Outra maneira de provar que isso é usar o Jump Operator . Precisamos apresentar a noção de Máquinas Oracle e, em seguida, mostram que $ b=left \ {\ esquerda (m ^ a, w \ à direita) | \ Texto {$ m ^ A $ a $ para $ W $} \ Direita \} $ é uma linguagem estritamente mais difícil. A prova é idêntica à indecidificação do problema de interrupção padrão, apenas que agora mostramos a propriedade mais forte que nenhuma máquina com o oracle Access para $ a $ pode decidir $ b $ .

Você também pode construir diretamente essa linguagem via diagonalização. Definir $ b=left \ {n | M_n (n) \ notin a \ direito \} $ . Nós construímos $ b $ tal que qualquer função computável $ m_n $ não é uma redução da $ B $ para $ a $ em pelo menos uma entrada (especificamente, a codificação da redução). Agora você pode usar o operador de junção para torná-los comparáveis.