Um exemplo de uma linguagem decidível é o idioma `a ={
| M é um DFA que aceita w} `. Em outras palavras, o idioma consiste em pares de um autômato finito determinístico (DFA) codificado como uma string e uma string `W`, de modo que o DFA aceite a sequência` W`.
Eis por que é decidível e como uma máquina de Turing pode decidir:
decidabilidade: Um idioma é decidível se existe uma máquina de Turing que interrompe todas as entradas e aceita a entrada, se estiver no idioma e rejeitar -a, se não for.
Turing Machine decora: Podemos construir uma máquina de Turing `d` que decide` a` da seguinte maneira:
1. entrada: `D` toma como entrada` `, onde` m` é a codificação de um DFA e `w` é uma string.
2. simulação: `D` simula o dfa` m` na string de entrada `w`. Isso é possível porque `d` pode acompanhar o estado atual de` m` e o símbolo atual que está sendo lido em `w '. A simulação prossegue da seguinte maneira:
* Inicie `m` em seu estado inicial.
* Para cada símbolo em `w`, transição` m` para o próximo estado de acordo com sua função de transição.
3. aceitar/rejeitar:
* Se `m` termina em um estado de aceitação depois de ler a string inteira` w`, então `d` aceita` `.
* Se `m` termina em um estado não aceito depois de ler a string inteira` w`, então `d` rejeitar` `.
Por que isso funciona:
* dfas sempre param: DFAS, por definição, processe cada símbolo de entrada exatamente uma vez e depois pare. Eles não têm loops infinitos ou comportamento indefinido.
* simulação é possível: Uma máquina de Turing pode simular facilmente o comportamento determinístico de um DFA porque possui memória e controle suficientes para rastrear o estado e a posição de entrada do DFA.
* interromper: A máquina de Turing `d` sempre pára porque a simulação DFA sempre pára.
* correção: `D` aceita exatamente as strings` `onde` m` aceita `w`, e rejeita exatamente as strings` `onde` m` faz * não * aceitar `w`.
prova formal (esboço):
Para provar rigorosamente a decidabilidade, você precisaria:
1. Defina formalmente a codificação: Especifique como um DFA `m` e uma string` w` são representados como strings no alfabeto de entrada da máquina de Turing `d`.
2. Defina formalmente a máquina de Turing `d`: Dê um diagrama de estado ou uma descrição formal das transições de `d`.
3. Prove a correção: Mostre que se `` estiver no idioma `a`, então` d` aceitará, e se `` não é * não * no idioma `a`, então` d` rejeitar.
4. Prove a interrupção: Mostre que `d` sempre pára em qualquer entrada.
em resumo: Como podemos construir uma máquina de Turing que sempre interrompe e aceita corretamente ou rejeita com base no fato de um determinado DFA aceitar uma determinada string, o idioma `a` é decidível. Este é um exemplo fundamental e importante na teoria da computação.
