As linguagens em $\mathsf{coRE} \setminus \mathsf{R}$ possuem máquinas de Turing?

Question

O que podemos dizer sobre línguas em $\mathsf{coRE} \setminus \mathsf{R}$?Existem máquinas de Turing para essas linguagens?

eu sei que $\overline{HP} \in \mathsf{coRE}$ não possui uma máquina de Turing, e também que todas as linguagens que possuem máquinas de Turing estão em $\matemática{RE}$, então é verdade que para qualquer idioma que esteja em $\mathsf{coRE} \setminus \mathsf{R}$ não existe uma máquina de Turing?Eu me pergunto por que isso acontece, alguém pode explicar?

Answer 1

Podemos associar uma linguagem a uma máquina de Turing de várias maneiras.

Se a máquina de Turing interrompe em todas as entradas, o idioma aceito pela máquina de Turing consiste em todas as palavras que fazem com que a máquina de Turing parasse em um estado de aceitação. A classe $ \ mathsf {r} $ consiste em todos os idiomas que são aceitos por alguma máquina de Turing.

Para uma máquina de Turing arbitrária, a linguagem reconhecida pela máquina de Turing consiste em todas as palavras que fazem com que a máquina de Turing parasse (em qualquer estado). A classe $ \ mathsf {re} $ consiste em todos os idiomas que são reconhecidos por alguma máquina de Turing.

Se $ l \ in \ mathsf {core} \ setminus \ setminus \ mathsf {r} $ , em particular $ L \ notin \ mathsf {r} $ e, portanto, nenhuma máquina de Turing aceita $ l $ . Se $ l $ foram reconhecidos por alguma máquina de Turing, em seguida, $ l \ in \ mathsf {re} $ . No entanto, isso é impossível, desde então $ l \ in \ mathsf {re} \ cap \ mathsf {core}=mathsf {r} $ .

.

Answer 2

Deixe-me expandir a primeira frase da resposta de Yuval Filmus:

Podemos associar uma linguagem a uma máquina de Turing de diversas maneiras.

Yuval menciona dois: aceitação (que caracteriza $\matemática{R}$) e reconhecimento (que caracteriza $\matemática{RE}$).Existem outros, no entanto.Obviamente, poderíamos considerar o "co-reconhecimento" - digamos que uma máquina de Turing $M$ "co-reconhece" uma linguagem $L$ se as cordas em $L$ são exatamente as cordas nas quais $M$ faz não parar.Então é claro que o co-reconhecimento caracteriza $\mathsf{coRE}$.

No entanto, isso é um pouco antinatural.Muito mais natural, na minha opinião, é a noção de limitar computabilidade.Formulado em termos de números naturais para simplificar, é o seguinte:

Uma função $f:\mathbb{N} ightarrow\mathbb{N}$ é limite computável se existe uma função computável $h:\mathbb{N}^2 ightarrow\mathbb{N}$ de tal modo que $$f(x)=\lim_{s ightarrow\infty} h(x,s),$$ ou mais precisamente tal que para todos $x$ há algum $n$ tal que para todos $s>n$ Nós temos $h(x,s)=f(x)$.

A definir $X$ é limite computável, entretanto, se houver alguma função limite computável $f$ de tal modo que $X=\{eu:f(eu)=1\}$.(Existem muitas outras formulações equivalentes disso.)

Acontece que a computabilidade limite tem uma caracterização alternativa muito boa:

(Shoenfield) Uma função $f$ é limite computável se for computável relativo a o problema da parada $\emptyset'$.

(E através Publicar obtemos outra caracterização em termos de “complexidade de definição”.)

É claro que isso inclui ambos $\matemática{RE}$ e $\mathsf{coRE}$, e muito mais além:existem conjuntos computáveis ​​em relação ao problema da parada que não são equivalentes de Turing a qualquer conjunto em $\matemática{RE}$.(Isso é difícil de provar!)

E há ainda mais maneiras de atribuir idiomas a conjuntos;por exemplo, podemos falar sobre "limitar a capacidade de reconhecimento" (que é limitar a computabilidade assim como a capacidade de reconhecimento é para a aceitação), o que nos dá a $\Sigma^0_2$ línguas.