Computabilidade e Decidibilidade
A teoria da computabilidade estuda os limites fundamentais da resolução algorítmica de problemas, marcando a fronteira entre problemas que podem ser resolvidos por algum procedimento eficaz e aqueles que nenhum algoritmo pode decidir.
Definition
A teoria da computabilidade é o estudo de quais funções e problemas de decisão são computáveis por um procedimento eficaz; um problema é decidível se algum algoritmo sempre para com a resposta correta de sim ou não, e indecidível se tal algoritmo não existe.
Scope
Esta área abrange modelos formais de computação eficaz, como as máquinas de Turing, a tese de Church-Turing que identifica esses modelos com a noção intuitiva de algoritmo, a existência de problemas indecidíveis, incluindo o problema da parada, reduções usadas para transferir a insolubilidade entre problemas, e a estrutura dos graus de insolubilidade que classificam problemas além do computável.
Sub-topics
Core questions
- O que significa para um problema ser solúvel por um algoritmo?
- Existem problemas bem definidos que nenhum algoritmo pode resolver?
- Como a insolubilidade de um problema pode ser usada para provar a insolubilidade de outro?
- Como os problemas insolúveis são classificados por sua dificuldade relativa?
Key theories
- Modelo de computação de Turing
- A máquina abstrata de Turing formalizou a noção de um procedimento eficaz e foi usada para provar que os problemas de parada e decisão para a lógica de primeira ordem são insolúveis, estabelecendo limites inerentes à computação.
- Existência de problemas indecidíveis
- Por um argumento diagonal, existem problemas, mais notoriamente o problema da parada, que nenhum algoritmo pode decidir, de modo que a indecidibilidade é uma característica estrutural pervasiva, e não uma curiosidade.
- Equivalência de modelos de computação
- Máquinas de Turing, o cálculo lambda e funções recursivas definem exatamente a mesma classe de funções computáveis, a convergência que sustenta a tese de Church-Turing.
Clinical relevance
Os resultados de indecidibilidade estabelecem limites rígidos para o que as ferramentas de software podem garantir: nenhum algoritmo geral pode decidir se um programa arbitrário para, está correto ou está livre de certos erros, razão pela qual as ferramentas de verificação dependem de aproximação, linguagens restritas e orientação humana, em vez de análise automática completa.
History
Impulsionados pelo Entscheidungsproblem de Hilbert, Church e Turing mostraram independentemente em 1936 que nenhum algoritmo pode decidir toda a lógica de primeira ordem, com o modelo de máquina de Turing e o cálculo lambda de Church provando-se equivalentes. Post e Kleene estenderam a teoria para o estudo dos graus de insolubilidade nas décadas seguintes.
Key figures
- Alan Turing
- Alonzo Church
- Kurt Gödel
- Emil Post
Related topics
Seminal works
- turing1937
- church1936
- sipser2013
Frequently asked questions
- Qual a diferença entre decidível e indecidível?
- Um problema é decidível se existe um algoritmo que sempre para e fornece a resposta correta de sim ou não para cada entrada. É indecidível se tal algoritmo não pode existir, como provado para o problema da parada; um problema indecidível ainda pode ser reconhecível, o que significa que um algoritmo pode confirmar instâncias de sim, mas pode rodar indefinidamente em instâncias de não.
- A indecidibilidade significa que esses problemas nunca podem ser abordados?
- Significa que nenhum algoritmo único resolve todas as instâncias corretamente. Na prática, as ferramentas lidam com casos restritos, fornecem respostas aproximadas ou conservadoras, ou resolvem muitas instâncias enquanto ocasionalmente falham ou pedem ajuda, de modo que a indecidibilidade molda como os problemas são atacados, em vez de proibir todo o progresso.