Problema concluído para a classe de TODOS os idiomas

Você não especificou sua noção de redução, portanto, assumirei que você escolheu alguma classe contável de funções $\cal F$ que pode ser usada para reduções (qualquer subconjunto das funções computáveis funcionaria aqui). Deixei $\cal L$ qualquer classe de idiomas sobre algum alfabeto fixo $\Sigma$ digamos $\Sigma = \{0,1\}$ . Uma linguagem $K$ é difícil para $\cal L$ (em relação a $\cal F$ ) se para cada $L \in \cal L$ existe $f \in \cal F$ de tal modo que $x \in L$ iff $f(x) \in K$ . Se também $K \in \cal L$ então dizemos isso $K$ está completo para $\cal L$ .

Agora vou mostrar que nenhum idioma é difícil para $\mathsf{ALL}$ . Suponha que $K$ estavam $\mathsf{ALL}$ -Difícil. Deixei $f_x : x \in \Sigma^*$ ser uma enumeração das funções em $\cal F$ (existe uma enumeração porque os dois $\Sigma^*$ e $\cal F$ são contáveis). Definir um idioma $L$ de

L = {x : f_{x} (x) \notin K} .

$L = \{x : f_x(x) \notin K \}.$ Desde a

L \in A L L

$L \in \mathsf{ALL}$ , existe uma função

f \in F

$f \in \cal F$ tal que para todos

x \in Σ^{*}

$x \in \Sigma^*$ ,

x \in L

$x \in L$ iff

f (x) \in K

$f(x) \in K$ . Desde a

f \in F

$f \in \cal F$ , existe

x \in Σ^{*}

$x \in \Sigma^*$ de tal modo que

f = f_{x}

$f = f_x$ . Para este particular

x

$x$ ,

x \in L

$x \in L$ iff

f_{x} (x) \in K

$f_x(x) \in K$ . No entanto, por definição

x \in L

$x \in L$ iff

f_{x} (x) \notin K

$f_x(x) \notin K$ .

Yuval Filmus
fonte

Argumento interessante de cardinalidade. E o problema que eu dei na pergunta (dada uma descrição da função, retorne sua tabela de verdade)? Parece que esse problema (que é obviamente muito indecidível) permitiria que qualquer problema fosse resolvido (obtenha a tabela verdade do oráculo e, em seguida, procure o problema). Você pode explicar onde meu argumento dá errado, além do fato de que (obviamente) esse oráculo não existe?

Demi

É a sua intuição que dá errado. Você não pode inserir um "problema", pois os problemas não têm descrições finitas em geral.

Yuval Filmus

Então, basicamente, mesmo um oráculo todo-poderoso (que poderia responder a qualquer pergunta) ainda é inadequado para resolver alguns problemas, porque não há como fornecer ao oráculo as informações necessárias?

Demi

Não existe um oráculo todo-poderoso, exatamente por esse motivo. A prova de indecidibilidade do problema de parada pode ser estendida para mostrar que, dado qualquer oráculo

O

$O$ , o problema de decidir se uma máquina de Turing com acesso a

O

$O$ pára permanece indecidível, mesmo tendo acesso a

O

$O$ . Por outro lado, podemos construir um oráculo que pode "redirecionar" para

O

$O$ ou resolver o problema de parada da máquina com acesso a

O

$O$ . Este oráculo é mais poderoso do que

O

$O$ .

Yuval Filmus

Ah ok. Portanto, a razão pela qual oráculos todo-poderosos não existem, enquanto

E X P / e x p = A L L

$EXP/exp = ALL$ , é porque o conselho pode depender de uma quantidade infinita de informações sobre o problema?

Demi

Problema concluído para a classe de TODOS os idiomas

Respostas: