A máquina de Turing

Dispositivo imaginário que formalizou os fundamentosda ciência da computação. Turing demostrou que a computação das operações de leitura, escrita e exclusão de símbolos binários poderiam ser satisfeitas por uma máquina que contivesse uma fita de comprimento ilimitado, com campos de tamanho definido sobre ela e um dispositivo com um número finito de estados realizando operações. Veja mais sobre o modelo ao lado: aturingmachine.com

Modelo em Lego

Em relação ao modelo do exemplo anterior, sua implementação pode ser mais fácil, porém vai requerer bastante trabalho para realizar as operações de leitura, escrita e exclusão e executar alguns algoritmos simples como somatório e subtração. No endereço indicado há um detalhamento da construção e o contato com os autores:
legoofdoom.blogspot.com

O conceito da máquina

Trata-se de um dispositivo imaginário revolucionário criado por Turing aos 24 anos de idade. A máquina de Turing formou a estrutura básica para fundamentar a ciência da computação moderna e a computabilidade. Sua invenção foi responsável, anos depois, pelo reconhecimento da comunidade científica internacional, nomeando Turing com o título simbólico de "pai da computação".

Números Computáveis

A teoria foi publicada em 1936, no artigo "On Computable Numbers, with an Application on the Entscheidungsproblem", em resposta ao tratamento do problema da decisão, formulado por Hilbert. Apesar da máquina de Turing não ter sido implementada fisicamente, na totalidade pelo seu autor, o processo computacional foi matematicamente demostrado e provado no artigo.

As bases matemáticas

Os Teoremas de Incompletude de Gödel, de 1931, representam o fim da idade romântica da Matemática.
Antes de Gödel, David Hilbert propôs que todo problema matemático é solúvel.
"Se existe um problema, ache a solução você pode encontrá-la apenas pensando, pois não há ignorabimus em matemática".

Consistência

Uma teoria axiomática é dita consistente quando nela não é derivada uma contradição, ou seja, não são derivados uma proposição e a sua negação. Por exemplo, a teoria das álgebras de Boole pode ser considerada consistente, pois possui um modelo finito. Quando as regras utilizadas correspondem a lógica clássica, se a teoria for inconsistente, a partir de uma contradição pode ser derivado qualquer enunciado, trivializando o sistema.

Completude

Uma teoria axiomática é dita completa se para cada proposição P da teoria (fórmula sem variáveis livres), ou bem pode ser deduzida P ou bem pode ser deduzida a negação de P. Como exemplos de teorias matemáticas completas podemos citar a teoria dos corpos algebricamente fechados de característica fixa e a teoria das álgebras de Boole sem átomos.

A proposta de Hilbert

Axiomatizar todo o corpo de conhecimento matemático (inclusive com objetivo de provar que todo problema matemático fosse solúvel).

Provar, por meios estritamente finitários, que a axiomática pretendida fosse consistente.

Gödel em Cena

Em 1931 Kurt Gödel timidamente anunciou: "Pode-se, de fato, exibir sentenças verdadeiras mas que são indemonstráveis no sistema formal da matemática".

O único dos presentes que imediatamente compreendeu a revolução que se iniciava foi John von Neumann.

Os matemáticos acabavam de ser expulsos do paraíso...

Jon Von Neumann

Foi um matemático húngaro e naturalizado norte-americano. Principais contribuições Matemáticas:

• Análise Funcional
• Teoria Ergódica
• Estatística
• Teoria dos Números
• Formalização da Computação