A Teoria das Funções Recursivas de Kleen

Introdução

A presente revisão literaria tem como objetivo fazer um levantamento geral da linha do tempo de:

- Entscheidungsproblem, o trabalho de David Hilbert,

- Incompleteness Theorem, o trabalho de Kurt Godel,

- A Hipótese de Church,

- Teoria das Funções Recursivas de Kleen,

e um paralelo com o atual cenário da computação;

        Entscheidungsproblem, o trabalho de David Hilbert,

(1862) - David Hilbert foi um matemático alemão que nasceu em Konigsberg, Prússia Oriental, hoje a cidade tem o nome de Kaliningrado, ele é considerado por muito como um dos maiores matematicos do śeculo XX.

 David Hilbert (1921): propˆos o programa de Hilbert, como

uma meta estabelecidos para os matem´aticos para formalizar

a matem´atica e provar que essa est´a livre de contradi¸c˜oes.

(1928) - O Entscheidungsproblem, termo alemão para "Problema de decisão", é atribuído a David Hilbert: Na conferência de 1928 Hilbert fez questões bastante precisas. Ele é resolvido quando conhecemos um procedimento que permite, para qualquer expressão lógica dada, decidir sua validade ou satisfatibilidade, exemplo, se algo é verdadeiro ou falso, ou seja os Entscheidungsproblem são problemas de determinar se um determinado elemento de algum universo pertence ou não a um determinado conjunto.

Um exemplo clássico do Entscheidungsproblem: Dado um número inteiro qualquer, saber se esse numero é primo ou não

(1936) - Em 1936, trabalhando independentemente, Alonzo Church e Alan Turing mostraram que é impossível decidir algoritmicamente se um enunciado na lógica de primeira ordem é verdadeiro ou falso.

Embora o Entscheidungsproblem fosse um problema impossível de resolver o mesmo foi de extrema importância para o desenvolvimento da computação já que com base no Entscheidungsproblem, Turing imaginou uma máquina com a capacidade de decodificar símbolos e após estes decodificados através de uma programação seria decidido o destino destes símbolos (TURING, 1937).

 Incompleteness Theorem, o trabalho de Kurt Godel

(1906) - Kurt Friedrich Gödel foi um matemático austríaco, naturalizado norte-americano.Seu trabalho mais conhecido é seu teorema da incompletude.

Kurt G¨odel (1931): provou os teoremas de incompletude,

mostrando que o objetivo de Hilbert n˜ao pode ser alcan¸cado.

Os teoremas da incompletude de Kurt Godel, vêm por um fim dramático à tentativa de unificar a matemática num sistema formal como propôs Hilbert.

Os teoremas de Godel dizem que é impossível definir um sistema de axiomas completo que seja simultaneamente consistente. Isto é, ou é completo ou é consistente.

Os teoremas da incompletude de Gödel são dois teoremas da lógica matemática que estabelecem limitações inerentes a quase todos os sistemas axiomáticos, exceto aos mais triviais. No qual afirma que qualquer sistema axiomático suficiente para incluir a aritmética dos números inteiros não pode ser simultaneamente completo e consistente. Isto significa que se o sistema é auto-consistente, então existirão proposições que não poderão ser nem comprovadas nem negadas por este sistema axiomático.

De grosso modo pode exprimir-se o primeiro teorema assim: