Indiomas indecidíveis são idiomas para os quais não se pode existir algoritmo (máquina de Turing) que decida corretamente, para cada sequência de entrada, se essa string é um membro do idioma. Idiomas decidíveis, por outro lado, * fazem * ter esse algoritmo. A principal diferença está na existência de um algoritmo de parada garantido.
Aqui estão alguns exemplos de idiomas indecidíveis, ilustrando diferentes maneiras de indecidibilidade surgir:
1. O problema de parada (h): *
Descrição do idioma: H ={⟨m, w⟩ | Turing Machine M Partia na entrada w}. Esse idioma consiste em todos os pares da codificação de uma máquina de Turing (⟨m⟩) e uma string de entrada (W), de modo que a máquina M pare quando recebe W como entrada.
*
indecidibilidade: Está provado que nenhum algoritmo pode existir que determine corretamente, para cada ⟨m, w⟩, se M pare em w. Este é um resultado fundamental na teoria da computação. Qualquer tentativa de construir esse algoritmo leva a uma contradição (normalmente através da diagonalização).
*
Por que é indecidível: A indecidibilidade do problema de interrupção decorre da natureza auto-referencial inerente das máquinas de Turing. Um algoritmo hipotético que resolve o problema de parada pode ser usado para criar uma máquina paradoxal que contradiz seu próprio comportamento previsto.
2. O problema de aceitação (a): *
Descrição do idioma: A ={⟨m, w⟩ | Turing Machine M aceita w}. Isso é semelhante ao problema de interrupção, mas se concentra especificamente na aceitação (a máquina é interrompida em um estado de aceitação).
*
indecidibilidade: Isso também é indecidível. Se pudéssemos decidir, também poderíamos decidir H (porque se M aceitar, ele é claramente parado em w). Como H é indecidível, um também deve ser indecidente.
3. O problema do vazio para as máquinas de Turing (e): *
Descrição do idioma: E ={⟨m⟩ | L (m) =∅} onde l (m) é o idioma aceito pela máquina de Turing M. Este idioma contém as codificações de todas as máquinas de Turing que não aceitam strings (o idioma deles está vazio).
*
indecidibilidade: Não há algoritmo que possa determinar, para cada máquina de Turing M, se L (m) está vazio. Isso está relacionado ao problema de parada; Se pudéssemos resolver e, poderíamos resolver o problema de parada construindo uma máquina m 'que interrompe se e somente se m parar e aceitar w.
4. Problema de correspondência post (PCP): *
Descrição do idioma: Este é um exemplo mais complexo envolvendo pares de cordas. É indecidente determinar se um determinado conjunto de pares de string tem uma solução (uma concatenação de seqüências de caracteres dos pares que correspondem).
*
indecidibilidade: A indecidibilidade do PCP é comprovada usando reduções (mostrando que se o PCP fosse decidível, o problema de parada também seria decidível - uma contradição).
Línguas decidíveis - Contraste: Línguas decidíveis, por outro lado, * têm * algoritmos que sempre interrompem e classificam corretamente as seqüências pertencentes ao idioma ou não. Exemplos incluem:
*
A linguagem dos palíndromos: Um algoritmo pode verificar facilmente se uma determinada sequência é a mesma para frente e para trás.
*
A linguagem das cordas contendo "ABC": Um algoritmo simples pode digitalizar uma string e verificar a substring "ABC".
*
A linguagem das cordas binárias pares: Um algoritmo pode verificar o comprimento da string.
Em essência, a diferença se resume a se um algoritmo pode ser projetado para * sempre * dar uma resposta sim/não correta em tempo finito. Para idiomas indecidíveis, esse algoritmo é provavelmente impossível de criar. A existência desse algoritmo é o recurso definidor que distingue a decisão de idiomas indecidíveis.
