O teorema de Gödel e a computação
22
ago
A prova que Kurt Gödel formalizou para a teoria dos números deveria ser seguida por um documento que demonstrasse que o mesmo método de aplicasse a grandes sistemas axiomáticos formais em outros contextos, a abordagem moderna feita pela Máquina de Turing (é importante dizer que foi feita quase simultaneamente por Emil Post), que é uma prova mais geral e que toca o problema proposto por David Hilbert originalmente, que foi abordado por Gödel.
A prova agora escrita em linguagem de sistemas, de Gödel aplicava-se a formalização
particular da teoria dos números e procurou demonstrar que servia a sistemas axiomáticos formais, mas um conceito que não poderia ser determinado pelo documento original de Gödel, devido à falta de definição matemática de um procedimento efetivo de um algoritmo computacional, ou aquilo que Turing chamou de Máquina de Estado Finito.
Depois que Alan Turing conseguiu determinar o procedimento efetivo, inventando um computador idealmente idealizado, agora chamado de máquina de Turing (também feito de forma independente por Emil Post), tornou-se possível avançar de forma mais geral.
O requisito fundamental de Hilbert para um sistema matemático formal era que havia um critério objetivo para decidir se uma prova estava escrita na linguagem do sistema. Em outras palavras, existe uma prova mais moderna seja ela a máquina de Turing, seja um algoritmo, ou um programa de computador, feito para verificação de provas.
Assim a definição moderna e compacta do sistema axiomático formal como um conjunto de asserções recursivelmente enumerável é uma conseqüência imediata de um programa que trabalhe com um grande conjunto de teorema, que pela quantidade de axiomas, se tratados humanamente, levariam uma quantidade astronomica de tempo, algumas proposta foram feitas mais cedo em LISP (Levin, 1974) e mais recentemente por Gregory Chaitin (1982) ao propor que a Teoria da Informação de Algoritmos se propõe a trabalhar sobre objetos individuais em vez de conjuntos e distribuições de probabilidades propostos por Claude Shannon e Norbert Wiener. Assim a questão correta seria (Chaitin, 1982) quantos bits são necessários para calcular um objeto individual ?
A teoria da informação algorítmica se concentra em objetos individuais, em vez de nos conjuntos e distribuições de probabilidade considerados na teoria da informação de Claude Shannon e Norbert Wiener. Quantos bits é necessário para definir como calcular um objeto individual? Estes problemas levaram a teoria da Computabilidade.
A chamada teoria da computabilidade, também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 30 com o estudo das funções computáveis e dos graus de Turing, foram estudadas por Kolmogorov, Chaitin, Levin, Martin-Löf e Solomonoff, ainda há inúmeros trabalhos sobre a questão.
A questão da completude, ou a classe NP-completo, é o subconjunto dos problemas NP da complexidade computacional, verifica de que modo que todo problema em NP pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo, verificando se o problema é computável, na prática, se o algoritmo existe.
