Existem problemas mais complexos que o Problema da Totalidade que aparecem no mundo prático?

Sabemos que o problema da parada está no 1º nível da hierarquia aritmética. Sabemos que o Problema da Totalidade está no 2º nível da hierarquia aritmética. Quais são alguns exemplos de problemas no terceiro nível (ou superior) da hierarquia aritmética. +1 para problemas cujas instâncias são resolvidas no mundo prático (programadores, matemáticos etc.).

computability reference-request Otakar Molnár López
fonte

Mais alguma ajuda para fazer disso uma pergunta compreensível é apreciada.

Otakar Molnár López

Não tenho certeza, mas talvez decidir se duas máquinas (desiguais) de Turing geram as mesmas saídas para todas as entradas é um problema mais difícil que a totalidade.

rus9384

en.wikipedia.org/wiki/…

@ rus9384 Acho que deveria ser equivalente: você pode escrevê-lo na forma com recursivo, como Totalidade. Aqui é a entrada e é um número de etapas grandes o suficiente para interromper as duas TMs (uma vez que é conhecido, verificar se a saída é a mesma é trivial).

\forall x . \exists y . p (x, y)

$\forall x.\exists y.p(x,y)$

p

$p$

x

$x$

y

$y$

y

$y$

chi

Que tal lógica -order? Talvez avaliar se a afirmação nessa lógica é verdadeira é um problema completo para ?

n^{t h}

$n^{th}$

Σ_{n}^{0}

$\Sigma^0_n$

rus9384

Respostas:

Seja uma lista canônica do recursivamente enumerável, isto é, computávelmente enumerável, ou seja, Turing reconhecível, idiomas (ou conjuntos). $\{W_e\}_{e\in\mathbb N}$

A propriedade que é realmente recursiva, ou seja, computável, é : $W_e$ $\Sigma^0_3$

\exists d \forall n (n \in W_{e} \leftrightarrow n \notin W_{d}) .

$\exists d\forall n(n\in W_e\leftrightarrow n\not\in W_d).$

Está no terceiro nível da hierarquia: não é de menor complexidade que . Veja, por exemplo, Soare: conjuntos e graus recursivamente enumeráveis, Teorema 3.4 , para a prova. $\Sigma^0_3$

Bjørn Kjos-Hanssen
fonte