A tese de Church–Turing
De acordo com a tese de Church–Turing, se um cálculo puder ser feito de forma automatizada — por um dado método, num número finito de passos — então também pode ser feito por uma máquina de Turing. Neste artigo faz-se uma breve introdução à tese de Church–Turing e ao contexto histórico da sua formulação. Inclui-se uma tradução comentada de parte do artigo de Alan Turing de 1936 - 37, “Oncomputablenumbers, withan
applicationtotheEntscheidungsproblem” [24], onde é possível entender a origem da máquina de Turing.
Decidibilidade
Introdução
Na imensa gama de problemas computacionais, é habitual a busca da solução para eles de forma algorítmica. Entretanto, fora essa classe de problemas solúveis ou decidíveis, existe também a classe dos problemas insolúveis ou indecidíveis que não têm solução algorítmica. Esse artigo aborda essas duas classes a fim de mostrar quais problemas estão de um lado ou de outro do limiar computacional e mostrar como é importante conhecer e obter provas sobre a insolubilidade a fim de modificar ou simplificar tais problemas antes mesmo de se tentar criar uma solução algorítmica
Antes disso, devemos explanar alguns conceitos, como a tese de Church-Turing, que servirá de base para a criação de Máquinas de Turing. A partir dessas, poderemos criar modelos para a definição de algoritmos que, enfim, servirão para as provas sobre decidibilidade
Decidibilidade
Antes de definir decidibilidade, é necessário algum conhecimento relativo a máquinas de Turing. Máquinas de Turing são modelos computacionais. Ao se iniciar uma máquina de Turing sobre uma entrada, três resultados são possíveis: aceitar a entrada, rejeitar ou entrar em loop. Ao entrar em loop a máquina pode não estar, necessariamente, repetindo os mesmos passos, mas pode acarretar comportamento simples ou complexo que nunca leva a um estado de parada, ou seja, um estado que possa aceitar ou rejeitar a entrada. As máquinas que nunca entram em loop são chamadas decisores porque essas sempre tomam uma decisão de aceitar ou rejeitar. Um decisor que reconhece uma linguagem decide essa linguagem.
Um sistema lógico ou de teoria é decidível se um conjunto de todas as fórmulas válidas bem-formadas no sistema são decidíveis, o que significa dizer que existe um algoritmo tal que, para toda fórmula no sistema, o algoritmo é capaz de decidir em etapas finitas se uma fórmula é válida no sistema ou não. Por exemplo, a lógica proposicional é decidível porque existe um algoritmo – construção da tabela verdade – tal que, para cada fórmula que combina M fórmulas atômicas, existe um número máximo N = 2M de etapas tal que, depois de compilar essas N etapas, o algoritmo sempre decidirá se a fórmula é válida ou não. Uma maneira mais simples e intuitiva de descrever decidibilidade é como sendo uma técnica para determinar o limite de solubilidade de um problema.
Por outro lado, existem os problemas não decidíveis, os quais são classificados como algoritmicamente insolúveis, o que demonstra que os computadores são limitados de uma maneira muito fundamental em relação ao seu poder de solucionar problemas. O interessante de saber se um problema é algoritmicamente insolúvel é que o problema pode ser simplificado ou alterado sem que você tente, inutilmente, encontrar uma solução para ele.
Linguagens Decidíveis
Uma linguagem decidível é uma linguagem em que existe uma máquina de Turing que, quando recebe uma cadeia de entrada aceita-a ou à rejeita, dessa forma, a máquina de Turing sempre a decide.
Exemplo 1:
Neste exemplo será testado o problema de aceitação referente a um AFD, ou seja, se o mesmo aceita uma cadeia w. Para isso será estabelecida uma linguagem Aafd e sua decibilidade é constatada após o processo, ela esta definida como:
Aafd = {<B,w> | B é um AFD que aceita a cadeia de entrada w}
Algoritmo para a máquina de Turing M:
-
Simule o autômato B com respeito à entrada w
-
Verifique se ela termina em um estado de aceitação, caso sim , aceita, senão, rejeite.
Detalhes referentes á simulação do AFD foram abstraídos para não fujir ao escopo, mas é bom deixar claro que a maquina M faz verificações de corretude da entrada <B,w> bem como realiza a simulação diretamente, fazendo registro de estados e realizando as transições pertinentes descritas na função de transição do AFD.
Na realidade tanto AFDs tal como o acima,um AFN ou expressão regular poderiam ser computados por uma máquina de Turing pois todos eles podem ser convertidos uns para os outros.
O próximo exemplo faz referencia ao chamado teste de vacuidade(Sipser) para a linguagem de um autômato finito.Nela o objetivo é verificar a aceitação ou não de alguma cadeia por um AFD.
Exemplo 2:
Vafd = { <A> | A é um AFD e L(A) = ø }
Vafd é decidível ?
Algoritmo:
-
Marque o estado inicial A e vá para 2.
-
Enquanto nenhum novo estado for marcado, marque qualquer estado que possua uma transições chegando nele vindos de estados já macardos.
-
Se nenhum estado de aceitação estiver marcado, aceite, senão, rejeite.
Os exemplos à seguir tratam de problemas decidíveis com relação à linguagens livres do contexto.
Exemplo 3:
Analogamente ao problema de teste de aceitação do exemplo 1, o exemplo atual demonstra o problema de testar a geração de uma cadeira por um GLC para assim constatar a decibilidade de uma linguagem, no caso, Aglc definida como:
Aglc = { <G,w> | G é uma GLC que gera a cadeia w }
A primeira idéia que surge é tentar todas as possíveis derivações de G para constatar se alguma delas é igual à w. Apesar de simples e correta, a idéia é inviável tendo em vista que se G não gerar w a máquina entraria em loop infinito.
Assim uma forma mais inteligente faz-se necessária. Utilizando a Forma Normal de Chomsky, é certo que qualquer derivação terá 2n-1 com n sendo igual ao comprimento de w. Com base nisso e abstraindo dados específicos sobre a construção da Forma Normal o algoritmo ficará como:
Algoritmo sobre <G,w> , sendo G a GLC e ‘w’ a cadeia:
-
Aplique o processo para converter G de sua forma inicial para um GLC equivalente na Forma Normal de Chomsky.
-
Verifique o comprimento de w, se for maior que 0, liste todas as derivações de 2n-1 passos ( com n = |w| ) , senão liste todas as derivações com 1 passo.
-
Se alguma das derivações gerar w, aceite, caso contrário, rejeite.