Computabilidade
Origem: Wikipédia, a enciclopédia livre.
A Teoria da Computabilidade (mais comumente chamada de Teoria da Computação) começa no fim do século XIX com a pergunta
- "Existe alguma atividade que não possa ser feita de maneira mecânica?",
onde a expressão "de maneira mecânica" quer dizer que não é necessária nenhuma inteligência ou intuição para executar a atividade, apenas passos repetitivos. A palavra algoritmo já era conhecida na época, e tinha como significado precisamente "processo mecânico". Vemos então que a questão acima induz outra, especificamente
- "Qual a definição matemática de algoritmo?",
e um pouco de divagação filosófica mostra que este tópico está relacionado com as fundações da matemática.
As técnicas utilizadas pelos estudantes desta área advém de áreas como a lógica matemática, e em especial, o Intuicionismo, embora seus objetivos sejam diversos dos usuais.
[editar] Principais Resultados
Os primeiros resultados relevantes na direção da solução destas questões foram dados no ano de 1931 pelo matemático austríaco Kurt Gödel em seu artigo "On Formally Undecidable Propositions of Principia Mathematica and Related Systems", onde ele define questões solúveis mecanicamente como aquelas onde a solução pode ser dada por uma função recursiva (em estudos prévios Gödel acreditou que as funções algoritmicas fossem funções recursivas primitivas, mas felizmente descartou tal hipótese). Este artigo é famoso por ter mostrado que uma das questões do Programa de Hilberti era insolúvel.
O próximo passo relevante é dado por Alan M. Turing, em seu artigo "On Computable Numbers, with an Application to the Entscheidungsproblem", onde ele diz que um problema é solúvel mecanicamente se existe uma Máquina de Turing que resolve aquele problema, e demonstra que existe pelo menos um problema insolúvel algoritmicamente (se tal problema, definido em toda sua generalidade, pode ser eficientemente resolvido por cérebros humanos ainda é uma polêmica questão em aberto). A demonstração de Turing, apesar de ter um apelo intuitivo bastante didático para os estudantes de computação, é basicamente a mesma do artigo de Gödel.
Resultados subsequentes de autores como Alonzo Church incluem a demostração que uma função é recursiva se e somente se é computável por uma Máquina de Turing.
[editar] Tópicos Relacionados
- Teoria de Algoritmos
- Teoria da Computação
- Máquina de Turing
- Problema da Parada
- Programa de Hilbert
