Teoria da Computabilidade
A teoria da computabilidade estuda quais problemas podem, em princípio, ser resolvidos por um algoritmo e classifica os problemas insolúveis pelo seu grau de dificuldade.
Definition
A teoria da computabilidade, também chamada de teoria da recursão, é o ramo da lógica matemática que precisa a noção de uma função efetivamente calculável, estuda os conjuntos e funções que os algoritmos podem e não podem computar, e mede a dificuldade relativa de problemas insolúveis.
Scope
Esta área abrange modelos formais de computação e a tese de Church-Turing, conjuntos computáveis e computavelmente enumeráveis, problemas indecidíveis como o problema da parada, as redutibilidades e graus de Turing que medem a insolubilidade relativa, e a hierarquia aritmética que estratifica a definibilidade pela complexidade do quantificador.
Sub-topics
Core questions
- O que significa para uma função ou conjunto ser computável?
- Quais problemas naturais são algoritmicamente indecidíveis?
- Como a dificuldade dos problemas insolúveis pode ser comparada e classificada?
- Como a complexidade lógica corresponde aos níveis de computabilidade?
Key theories
- Tese de Church-Turing
- A noção intuitiva de calculabilidade efetiva coincide com a computabilidade da máquina de Turing, equivalentemente com as funções recursivas e as funções lambda-definíveis, fixando uma definição matemática robusta de algoritmo.
- Insolubilidade do problema da parada
- Nenhum algoritmo pode decidir para cada programa e entrada se o programa para, fornecendo o primeiro e prototípico exemplo de um problema indecidível.
- Graus de Turing
- A redutibilidade de Turing classifica conjuntos pela computabilidade relativa, e os graus induzidos formam uma ordem parcial rica cuja estrutura, incluindo a existência de graus intermediários, é um objeto central de estudo.
Clinical relevance
A teoria da computabilidade delimita o limite absoluto da solucionabilidade algorítmica, fundamentando a ciência da computação teórica e fornecendo os resultados de indecidibilidade, como a insolubilidade dos problemas da parada e da palavra, que recorrem em toda a matemática e informam a teoria da complexidade computacional.
History
A teoria da computabilidade surgiu na década de 1930, quando Church, Turing, Kleene e Post formalizaram independentemente a noção de um procedimento efetivo através do cálculo lambda, máquinas de Turing, funções recursivas e sistemas combinatórios, todos provados equivalentes. Post e Kleene desenvolveram a teoria dos graus e a hierarquia aritmética, e o método de prioridade introduzido na década de 1950 impulsionou o estudo estrutural profundo dos graus computavelmente enumeráveis.
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- soare1987
- rogers1987
- cutland1980
Frequently asked questions
- A teoria da computabilidade é o mesmo que a teoria da complexidade?
- Não. A teoria da computabilidade pergunta se um problema pode ser resolvido por qualquer algoritmo, ignorando recursos, enquanto a teoria da complexidade pergunta quanto tempo ou memória um problema solúvel requer. A computabilidade traça a linha entre o solúvel e o insolúvel; a complexidade classifica o lado solúvel.
- Por que a tese de Church-Turing não é um teorema?
- Ela equipara uma noção informal, calculabilidade efetiva, com uma noção matemática precisa, portanto não pode ser provada formalmente. Sua aceitação baseia-se na convergência de muitas formalizações independentes para a mesma classe de funções, o que é uma forte evidência em vez de uma prova.