Trabalho de biologia mercantil

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.

3. 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