Ok, vamos explorar o domínio dos idiomas não reconhecíveis e como eles diferem das línguas reconhecíveis de Turing (recursivamente enumeráveis) e decidíveis com Turing (recursivo). É uma paisagem do que os computadores * não podem fazer, e é bastante interessante!

Entendendo a paisagem primeiro

Antes de mergulhar em exemplos, vamos esclarecer as categorias:

* idiomas decidáveis ​​(recursivos): São idiomas para os quais uma máquina de Turing pode * sempre * parar e responder corretamente "sim" (aceitar) se a sequência de entrada estiver no idioma ou "não" (rejeitar) se a sequência de entrada não estiver no idioma. A máquina de Turing sempre fornece uma resposta definitiva.
* idiomas reconhecíveis (recursivamente enumeráveis): São idiomas para os quais uma máquina de Turing interromperá e aceitará se a sequência de entrada * estiver * no idioma. No entanto, se a sequência de entrada não estiver * no idioma, a máquina de Turing poderá interromper e rejeitar, ou poderá correr para sempre (loop). A chave é que ela * eventualmente * diz "sim" para cordas no idioma.
* Idiomas não reconhecíveis (não recursivamente enumeráveis): São idiomas para os quais a Máquina * de Turing pode até ser projetada para reconhecer com segurança strings no idioma. Não importa o quão inteligente você seja, você não pode construir uma máquina de Turing que aceite todas as cordas no idioma (e potencialmente pare quando não for). O complemento de um idioma reconhecível por Turing é reconhecível.

Exemplos de idiomas não reconhecíveis

Os exemplos mais comuns de idiomas não reconhecíveis geralmente envolvem os complementos de problemas indecidíveis conhecidos.

1. o complemento do problema de interrupção (−halt):

* O problema de interrupção (HALT): Este é o idioma que contém todas as codificações da máquina de Turing `⟨m, w⟩` onde a máquina de Turing` m` interrompe na sequência de entrada `W`. (Isso é reconhecível por Turing, mas * não * decidível).
* −halt: Este é o idioma que contém todas as codificações da máquina de Turing `⟨m, w⟩` onde a máquina de Turing` m` não * não * para na string de entrada `w`.
* Por que não é reconhecível: Se fossem reconhecíveis por Turing, a Halt seria decidível (poderíamos simular `m` em` W` e se nosso reconhecimento por ¬halt aceitar, sabemos que 'm` não parar; se rejeitar, sabemos `m` pares). Mas Halt é * comprovado * indecidível. Como a HALT é reconhecível por Turing, mas não é decidível, seu complemento, Halt, deve ser reconhecível por não-ator. Se a HALT fosse decidível, tanto a sua e o elogio seria reconhecível.

2. ):

* O problema de aceitação (A _{TM ):} Este é o idioma que contém todas as codificações da máquina de Turing `⟨m, w⟩` onde a máquina de Turing` m` aceita string de entrada `W`. (Isso é reconhecível por Turing, mas não é decidível de Turing).
* ¬a tm : Este é o idioma que contém todas as codificações da máquina de Turing `⟨m, w⟩` onde a máquina de Turing` m` faz * não * aceita string de entrada `w`. `M` pode rejeitar ou loop.
* Por que não é reconhecível: Raciocínio semelhante ao ¬halt. Se −a tm foram reconhecíveis por Turing, então um tm seria decidível, contradizendo a indecidibilidade conhecida de um tm .

3. o complemento do problema do vazio para as máquinas de Turing (−e _{tm ):}

* O problema do vazio (e Este é o idioma que contém todas as codificações da máquina de Turing `⟨m⟩` onde o idioma reconhecido pela máquina de Turing` m` está vazio (ou seja, `l (m) =∅`). (Isso não é * * reconhecível).
* −e : Esta é a linguagem que contém todas as codificações da máquina de Turing `⟨m⟩` onde o idioma reconhecido pela máquina de Turing` m` não * não * vazio (ou seja, `l (m) ∅ ∅`).
* Por que é reconhecível com Turing: Uma máquina de Turing pode reconhecer esse idioma simulando a máquina `m` em todas as entradas possíveis até que 'M' aceite.

4. A linguagem das máquinas de Turing que não param * de * entrada *

* Considere o idioma das máquinas de Turing que, quando iniciado * qualquer string de entrada, nunca interromperá. Não há algoritmo geral para determinar isso.
* Você pode tentar executar a máquina em muitas entradas diferentes, mas nunca terá certeza de que ela não interromperá em alguma outra entrada não testada.

Como os idiomas não-titulares diferem

A principal diferença está na capacidade de criar uma máquina de Turing que * de maneira confiável * reconhece seqüências de caracteres no idioma:

* Turing-Decidable: Uma máquina de Turing * sempre * fornece uma resposta correta ("sim" ou "não") e interrompe.
* Turing-reconhecível: Uma máquina de Turing fornece uma resposta "sim" se a string estiver no idioma, mas poderá fazer uma pausa para sempre se a string não estiver * no idioma.
* não-ator reconhecível: * Não é possível construir a Máquina de Turing para reconhecer com confiabilidade Strings no idioma. Qualquer máquina de Turing que você tentar aceitará algumas seqüências que * não estão * no idioma, percorrem sempre as cordas que * estão * no idioma ou falham de alguma outra maneira fundamental.

Intuição

Pense assim:

* Decidível: Você tem um teste perfeitamente confiável que sempre oferece a resposta certa.
* reconhecível: Você tem um teste que * definitivamente * diz "sim" se for a resposta correta, mas pode não ser capaz de dizer se a resposta é "não".
* Não reconhecível: Você não pode nem criar um teste que identifique com segurança os casos "sim". Qualquer teste que você fizer será falho e poderá fornecer resultados incorretos.

implicações importantes

A existência de idiomas não reconhecíveis tem implicações profundas para a ciência da computação e a matemática:

* limites de computação: Isso demonstra que existem limitações inerentes ao que os computadores podem fazer, por mais poderosos que se tornem.
* indecidibilidade: Ele destaca a existência de problemas que são fundamentalmente indecidíveis - não há algoritmo que possa resolvê -los em todos os casos.
* Técnicas de prova: É necessário o uso de técnicas de prova sofisticada (como diagonalização e reduções) para demonstrar a indecidibilidade ou a não reconhecibilidade de certos problemas.

Em resumo, os idiomas reconhecíveis não-Turing definem o limite do que é fundamentalmente não computável. Eles são uma parte crucial da compreensão dos limites teóricos da computação.