A Teoria da Computação

...

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.

Nessas condições:

- Se C é consistente, então Consc não é demonstrável em C.

Para demonstrar o segundo teorema de incompletude deve-se utilizar as fórmulas:

1.1 G ¬Dem ([G])

1.2 Consc ¬Dem ([G])

Com este segundo teorema foi invalidada a ideia de Hilbert onde ele imaginava um programa que fosse capaz de fundamentar a matemática através da derivação de uma teoria matemática complexa para uma mais simples (HAHN, 1896).

2.2.4 Contribuição do teorema da incompletude para a computação moderna

Os teoremas de incompletude preferencialmente o primeiro referente à meta-linguagem sendo introduzida na linguagem objeto foram fundamentais na teoria da recursão que permite que linguagens consigam voltar para um estado sem que ocorram paradoxos (HAHN, 18960).

2.3 Hipótese de Church

2.3.1 O Criador

Alonzo Church (1903 – 1995) foi um matemático lógico e filósofo estadunidense nascido em Washington DC, foi de extrema ajuda nos campos da lógica matemática, teoria da recursão e informática teórica seus dois trabalhos mais conhecidos são o teorema de Church e a tese de Church (DIVERIO, 2000).

2.3.2 A Ideia

Turing em 1936 apresentava um modelo abstrato chamado de máquina de Turing esta máquina consegue resolver qualquer problema deus que este problema seja computável sendo composto por uma função finita, consegue resolver qualquer problema em um tempo finito (DIVERIO, 2000).

Todos os demais trabalhos que surgiram após a máquina de Turing como, Máquina de Post e Funções Recursivas de Kleene ambas apresentadas em 1936, Máquina Norma e Autômato com Pilhas ambos apresentaram resultados muito semelhantes aos da máquina de Turing (DIVERIO, 2000).

Diante dos resultados semelhantes surgidos após o aparecimento da máquina apresentada por Turing, no mesmo ano Church chegou à conclusão de que a máquina de Turing era o limite, qualquer outro estudo que aparecesse na intenção de resolver problemas computáveis só iria conseguir apresentar no máximo os mesmos resultados que a máquina de Turing (DIVERIO, 2000).

2.3.3 Funcionamento da Hipótese de Church

A hipótese de Church não é demonstrável pelo fato de ser uma intuição que foi baseada em um conceito informal de algoritmo ela é apenas aceita como verdadeira sendo aceita como uma hipótese (DIVERIO, 2000).

A hipótese de Church não é um teorema ao qual utiliza-se os axiomas que são os conjuntos de verdades sendo utilizadas para testar o teorema, a hipótese de Church é apenas uma tese não possuindo instruções matemáticas (DIVERIO, 2000).

2.3.4 Contribuição da Hipótese de Church para a computação moderna

A hipótese de Church ajudou a concluir que a máquina de Turing ela o limite máximo que qualquer outro estudo conseguiria chegar, ajudando assim a considerar o principio básico da ciência da computação (DIVERIO, 2000).

2.4 Funções recursivas de Kleene

2.4.1 O criador

Stephen Cole Kleene foi um matemático americano (1909, 1994), foi aluno de Alonzo Church e fundador da teoria da recursão (DIVERIO, 2000).

2.4.2 A ideia

A ideia era construir funções que seriam capazes de chamar outras funções, ou seja, funções sobre funções. E para alcançar esse objetivo foram construídas utilizando alguns tipos de construções sendo utilizados três tipos: composição, recursão, minimização (DIVERIO, 2000).

2.4.3 Funcionamento das funções recursivas de Kleene

As funções recursivas de Kleene ou funções recursivas parciais são constituídas pela composição, recursão e minimização. A composição permite que essas funções sejam capazes de se unirem uma com base na outra. Com a recursão elas conseguem chamar elas mesmas até atingirem um objetivo final e com a minimização permite que essas funções atinjam o seu objetivo no menor tempo finito possível (DIVERIO, 2000).

2.4.4 Contribuição das funções recursivas de Kleene para a computação moderna

As