A Teoria da Computação

ENTSCHEIDUNGSPROBLEM, TEOREMA DA INCOMPLETUDE, HIPÓTESE DE CHURCH, TEORIA DAS FUNÇÕES RECURSIVAS E A SUA RELAÇÃO COM O DESENVOLVIMENTO DA COMPUTAÇÃO

Saul Augusto Silva

1. INTRODUÇÃO

        Este artigo tem como objetivo fazer um levantamento geral sobre o Entscheidungsproblem de David Hilber, o teorema da incompletude de Kurt Godel, a hipótese de Church de Alonzo Church e a teoria das funções recursivas de Kleen.

        Sobre cada um destes estudos será dado ênfase sobre quem são os seus criadores, qual é a ideia de cada estudo, como é o funcionamento de cada um e quais foram as suas contribuições para a computação moderna.

        Com base nessa pesquisa feita sobre cada um destes estudos será possível observar que todos apresentam uma ligação entre si e ajudaram a desenvolver a computação até chegar aos dias atuais onde todos os equipamentos computacionais atuais apresentam em seu desenvolvimento os conceitos apresentados nestes estudos.

2. RERENCIAL TEÓRICO

2.1 Entscheidungsproblem (Problema de Decisão)

2.1.2 O Criador

        David Hilbert foi um matemático alemão que nasceu em Konigsberg, Prússia Oriental, hoje a cidade tem o nome de Kaliningrado, ficou conhecido por ser professor de geometria euclidiana em Gottingen, sendo doutor na Universidade de

Konigsberg (1884) e professor pela mesma (1886- 1895) mudando-se mais tarde para a Universidade de Gottingens (1895-1930) continuando seus trabalhos na área da matemática. Nasceu em 1862 e morreu em 1943 (BIOGRAFIAS, DAVID HILBERT).

2.1.3 A Ideia

De todos os assuntos o que mais chamava a atenção de David Hilbert era o infinito, a ideia de Hilbert era criar uma solução que resolvesse todos os problemas á respeito dos fundamentos da matemática (HILBERT, 1923).

Em 1928 Hilbert expõe o seu ponto de vista para a resolução do problema de decisão da seguinte maneira (TEIXEIRA, 1998):

“O Entscheidungsproblem é resolvido quando conhecemos um procedimento que permite, para qualquer expressão lógica dada, decidir sua validade ou satisfatibilidade.”

Em simples palavras o problema de decisão recebe uma entrada analisando-a e retornando um resultado “verdadeiro” ou “falso”. Este algoritmo seria capaz de concluir, por exemplo, se a conjectura de Goldbach ou a hipótese de Riemann são verdadeiras ou falsas (HILBERT, 1923).

2.1.4 Funcionamento do Entscheidungsproblem

        O Entscheidungsproblem funciona da seguinte maneira, especificada uma  fórmula qualquer referente ao cálculo de predicados sendo sistemas formais simples de primeira ou de segunda ordem, o algoritmo consegue verificar se há um procedimento  que consiga determinar se tal entrada é demonstrável ou não (HILBERT , 1923).

Um exemplo de problema de decisão seria (TEIXEIRA, 1998):

“Dados dois números x e y, y é divisível por x?”.

2.1.5 Contribuição do Entscheidungsproblem para a computação moderna

Em 1936 realizando estudos independentes Alonzo Chuch e Alan Turing publicou estudos comprovando que o problema de decisão de Hilbert era impossível de ser resolvido não havendo a possibilidade de o algoritmo conseguir saber se um enunciado matemático fosse verdadeiro ou falso (TURING, 1937).

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).

2.2 Incompletenss Theorem (Teorema da Incompletude)

2.2.1 O criador

Kurt Friedrich Godel nasceu em Brunn antigo império austro-húngaro em 1906 foi um matemático naturazilado norte-americano. Participou do Círculo de Viena formado por Hans Hahn e Moritz Schlick onde consideravam que tudo podia ser explicado pela lógica matemática. Seu trabalho mais conhecido é o teorema da incompletude (HAHN, 1896).

2.2.2 A ideia

O Incompleteness Theorem (Teorema da Incompletude) surgiu em seu artigo na Proposição VI de 1931 onde qualquer sistema axiomático onde temos que axiomas são verdades onde estas verdades são inquestionáveis sendo válidas na construção de uma teoria ou servindo de base para argumentação, logo um sistema axiomático é constituído por vários axiomas, ou seja, um conjunto de verdades que servem para demonstrar os teoremas (HAHN, 1896).

O teorema da incompletude é utilizado para provar que existem fórmulas referentes às linguagens dos números naturais e suas negações podem ser provadas (HAHN, 1896).

2.2.3 Funcionamento do Imcompleteness Theorem

São dois os teoremas da incompletude. No primeiro teorema dependendo da complexidade das linguagens dos números naturais existem alguns termos dessas linguagens que não podem ser provadas mesmo aumentando o número de axiomas que é o conjunto de verdades utilizado para demonstrar o teorema, estas não são provadas (EPSTEIN, 1989).

Segue abaixo a proposição do primeiro teorema de incompletude (EPSTEIN, 1989):

Existe uma sentença G de C, tal que:

1.  Se o sistema C é consistente, então G não é demonstrável em C;

2.  Se o sistema C é w-consistente, então ¬G não é demonstrável em C;

Ou seja, se C é w-consistente, então C contém uma sentença indecidível.

Com essa proposição é possível determinar que mesmo aumentando o conjunto de verdades para demonstrar as sentenças utilizando o primeiro teorema sempre existirá afirmações impossíveis de serem demonstráveis (EPSTEIN, 1989).

Este primeiro teorema comprova que não é possível que existam programas passíveis de testar a sua complexidade (EPSTEIN, 1989).

O segundo teorema especifica que os sistemas utilizados no primeiro teorema são suficientes para demonstrar a sua própria consistência, ou seja, não existem programas capazes de testar a consistência com base no grau de complexidade (HAHN, 1896).

Segue abaixo a proposição do segundo teorema de incompletude (HAHN, 1896):

Seja Consc uma fórmula de C que representa a consistência de C.