Uma breve Historia da Computação (parte III)
[I,II] Para responder negativamente à questão de Gödel, Turing mostrou inicialmente que a intuição de que problemas progressivamente mais complexos necessitavam de máquinas cada vez mais complexas, estava errada. Turing construiu uma máquina U que dado um problema computável P era capaz de simular a execução de uma qualquer máquina capaz de resolver P, sendo, portanto, capaz de resolver o problema em questão. Por esta razão, Turing chamou à máquina U a máquina universal. É a existência teórica desta máquina que deu origem, algumas décadas depois, aos computadores actuais. Turing provou que o entscheidungsproblem poderia ser traduzido num outro problema, denominado por problema da paragem (do inglês, The Halting Problem):
Entretanto, o número de formalismos apresentados na literatura científica aumentava (por exemplo, as máquinas URM, o cálculo lambda, as funções parciais recursivas). Todos se exprimiam uns nos outros e quando não acontecia era porque o sistema proposto tinha falhas que lhe reduziam a capacidade efectiva. As mais variadas formas de expressão da computabilidade – baseadas em diferentes abordagens – eram análogas. Kleene, em 1952, apelidou de Tese de Church a conjectura vigente que a máquina de Turing e os equivalentes exprimiam o conceito intuitivo de algoritmo.
Mas, apesar desta nova e inesperada limitação da Matemática – e provavelmente a descoberta mais significativa e profunda da Matemática de todo o Século XX – o caminho teórico estava aberto para a construção dos computadores. [cont.]
ps: Referi na 1ª parte que Hilbert, em 1900, apresentou 23 problemas como desafios para o Século XX. Já só restam 3 por resolver, o 6º, o 8º e o 16º. Curiosamente, ontem surgiu a notícia que uma estudante de 22 anos em Estocolmo resolveu parcialmente o 16º, resultado que será apresentado em breve.
Seja uma máquina de Turing M e um conjunto de dados iniciais I. Será que a execução de M sobre I termina?Assim, demonstrou por redução ao absurdo, que se existisse uma máquina de Turing capaz de garantir o problema da paragem de qualquer máquina de Turing, a execução dessa máquina, para certos casos, conduzia a situações contraditórias. Isto implicava que não havia nenhuma máquina capaz de resolver o problema da paragem nem o Entscheidungsproblem. O resultado negava a questão deixada em aberto por Gödel! A matemática revela-se incompletamente mecanizável, i.e., por mais complexo que seja o formalismo apresentado haverá sempre proposições indecidíveis que nem sequer podem ser identificadas como tal nessa formalização.
Entretanto, o número de formalismos apresentados na literatura científica aumentava (por exemplo, as máquinas URM, o cálculo lambda, as funções parciais recursivas). Todos se exprimiam uns nos outros e quando não acontecia era porque o sistema proposto tinha falhas que lhe reduziam a capacidade efectiva. As mais variadas formas de expressão da computabilidade – baseadas em diferentes abordagens – eram análogas. Kleene, em 1952, apelidou de Tese de Church a conjectura vigente que a máquina de Turing e os equivalentes exprimiam o conceito intuitivo de algoritmo.
Mas, apesar desta nova e inesperada limitação da Matemática – e provavelmente a descoberta mais significativa e profunda da Matemática de todo o Século XX – o caminho teórico estava aberto para a construção dos computadores. [cont.]
ps: Referi na 1ª parte que Hilbert, em 1900, apresentou 23 problemas como desafios para o Século XX. Já só restam 3 por resolver, o 6º, o 8º e o 16º. Curiosamente, ontem surgiu a notícia que uma estudante de 22 anos em Estocolmo resolveu parcialmente o 16º, resultado que será apresentado em breve.
Sem comentários:
Enviar um comentário