Para qualquer idioma

Estou tentando criar uma prova para o seguinte:

Para qualquer idioma , existe uma linguagem tal que , mas B . $A$ $B$ $A \le_{\mathrm{T}} B$ $\nleq_{\mathrm{T}} A$

Eu estava pensando em deixar ser , mas eu percebo que nem todos os idiomas são Turing redutível a , então não iria realizar. Que outra opção de eu tenho que me permitiria escrever uma TM que usa um oráculo para decidir ? $B$ $A_{\mathrm{TM}}$ $A_{\mathrm{TM}}$ $A \le _T B$ $B$ $B$ $A$

Obrigado!

computability reductions undecidability user1354784
fonte

Que tal

B = N P^{A}

$B = NP^A$

Eugene

Pense no problema da parada em máquinas de Turing com oráculo

A

$A$

Willard Zhan #

A

$A$

α \in Σ^{*}

$\alpha\in\Sigma^*$

M_{α}

$M_\alpha$

A

$A$

@DavidRicherby Sim, mas B não é fixo, é construído sabendo o que A é. Se recebermos um A, construímos um B que aceita todos os TM oracle com um oracle para esse A específico que aceita strings em A. Se recebermos um A diferente, a lista de TMs em B será diferente.

precisa saber é o seguinte

B = A_{T M}

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

Respostas:

$B=A'$ $A$

Bjørn Kjos-Hanssen
fonte

$X$ $X'$ $X<_TX'$

Cantor mostrou que existem inúmeras línguas.
$A$ $A$

Então, de fato, sabemos, sem fazer nenhum trabalho sério, que:

$A$ $B$ $B\not\le_TA$

$X,Y$ $X\oplus Y$ $X$ $Y$ $X$ $Y$ $X\oplus Y=\{2i: i\in X\}\cup\{2i+1: i\in Y\}$ $X\oplus Y\ge_TX,Y$ $\le_T$

Portanto, podemos aplicar o acima, para obter:

$A$ $B$ $A<_TA\oplus B$

Isso então levanta a questão de fornecer uma prova não estúpida , a saber, uma maneira natural de produzir uma linguagem estritamente mais complicada do que uma dada, e é para isso que serve o salto de Turing; mas vale a pena entender esse argumento não construtivo por si só.

Noah Schweber
fonte