Para mostrar que uma linguagem é decidível, precisamos para criar uma máquina de Turing que irá parar em qualquer string de entrada do alfabeto da linguagem. Como M é um dfa, já temos a Máquina de Turing e só precisamos mostrar que o dfa para em cada entrada.
Como você calcula a Decidibilidade?
Uma linguagem é decidível se e somente se ela e seu complemento são reconhecíveis. Prova. Se uma linguagem é decidível, então seu complemento é decidível (por fechamento sob complementação).
Como você prova a Decidibilidade de Turing?
Prove que o idioma que ele reconhece é igual ao idioma fornecido e que o algoritmo pára em todas as entradas. Para provar que uma determinada linguagem é Turing-reconhecível: Construa um algoritmo que aceite exatamente aquelas strings que estão na linguagemEle deve rejeitar ou fazer um loop em qualquer string que não esteja no idioma.
Como você sabe se um idioma é reconhecível?
Uma linguagem L é reconhecível se e somente se existe um verificador para L, onde um verificador é uma máquina de Turing que pára em todas as entradas e para todo w∈Σ∗, w∈L↔∃c∈Σ∗. V aceita ⟨w, c⟩.
Como você mostra que um problema é indecidível?
O Problema da Totalidade é Indecidível
O problema da parada pode ser usado para mostrar que outros problemas são indecidíveis. Problema da Totalidade: Diz-se que uma função (ou programa) F é total se F(x) for definido para todo x (ou similarmente, se F(x) parar para todo x). Determinar se uma função F é total ou não é indecidível.
