-
Gödel, Turing e a História da Computação
José Luiz Goldfarb
[email protected]
PUC-SP
Danilo Gustavo Bispo
[email protected]
PUC-SP
Quando pensamos na história do computador ou do smart phone
estamos
seguros de que o assunto é tecnologia; para muitos a "maior
revolução tecnológica na
história da humanidade". A história da computação seria
entendida nesta perspectiva
como uma história de transformações tecnológicas.
Tomando um rumo diverso, neste trabalho procuramos mostrar o
quanto a
computação inclui em sua história problemas teóricos
relacionados aos fundamentos da
lógica e da matemática na virada do século XIX para o século XX,
problemas oriundos
de vários desenvolvimentos do XIX, especialmente o surgimento
das novas geometrias
não euclidianas que colocam em questão a verdade e objetividade
no domínio tido como
inabalável da geometria, da matemática e da lógica. Através dos
teoremas apresentados
por Kurt Gödel e Alan Turing - respondendo negativamente a
algumas questões do
famoso "programa de Hilbert" - vamos relacionar estes
desenvolvimentos teóricos ao
surgimento dos modernos algoritmos e suas codificações, a
verdadeira alma da ciência
da computação e suas múltiplas e mirabolantes aplicações
tecnológicas. Nossos
documentos primários serão os artigos publicados por Gödel (On
Formally Undecidable
Propositions in Principia Mathematica and Related Systems, 1931)
e por Turing (On
Computable Numbers, with an Aplication to the
Entscheidungsproblem, 1936). Assim
procuraremos demonstrar o quão complexas podem se dar as
relações históricas entre
ciência e técnica: aonde esperávamos encontrar questões práticas
como manipulação de
materiais para a construção das máquinas computacionais,
buscando maior capacidade
de processamento e armazenamento de memória, somos surpreendidos
com fantásticas
construções teóricas e formais de Gödel e Turing. Finalmente
arriscaremos adiantar
algumas consequências destas reflexões históricas sobre
computadores e smart phones,
mailto:[email protected]:[email protected]
-
apontando possíveis limites da computação e da sociedade
digital. Afinal, podemos
aprender alguma lição com Gödel e Turing e suas provas da
incompletude, não
decidibilidade e não demonstrabilidade da consistência, para
avaliarmos os limites dos
computadores?
Motivações históricas: Geometrias Não-Euclidianas
Durante muito tempo um ramo da matemática conhecido como
geometria foi
estudado por Euclides através de sua obra nomeada como
Elementos, uma obra editada
por todo o planeta por mais de um milênio; um best-seller só
superado pela Bíblia. Os
Elementos de Euclides são descritos como uma série de definições
seguidas por cinco
postulados e algumas noções básicas. O livro é um guia que
demonstra a partir destes
poucos pressupostos, a possibilidade de se derivar uma
diversidade de teoremas1.
O que acontece é que dentre os postulados existe um que durante
muito tempo
na história da matemática ficou conhecido por ser fonte de
paradoxos e por ficar
registrado como intuitivamente controverso. Este postulado seria
o quinto.
Resumidamente é o que apresenta as condições sob as quais as
linhas são paralelas,
determinando que elas jamais se encontrarão ao serem estendidas
indefinidamente. Já na
Idade Média encontramos muitos estudos sobre indagações árabes
sobre o quinto
postulado.
No início do século XIX na Europa, alguns matemáticos começaram
a explorar
um outro tipo de abordagem. Passaram a assumir algo contrário ao
quinto postulado,
propor que talvez duas linhas retas sempre se encontrem,
independentemente do ângulo
que elas formem com outra reta. Seguindo esta linha de
raciocínio, personagens como
Carl Friedrich Gauss (1777-1855), János Bolyai (1802-1860) e
Nikolai Lobachevsky
(1792-1856) formularam alternativas ao quinto postulado de
Euclides e observaram que
estas formulações não resultavam necessariamente em
contradições, em vez disso,
levavam à construção de universos geométricos novos e estranhos,
mas inteiramente
pertinentes2. Em pouco tempo, os matemáticos aceitaram e
começaram por praticar
essas alternativas a geometria euclidiana.
1 Heath, Euclid’s Elements, 154-155. 2 Greenberg, Euclidean and
Non-Euclidean Geometries, 177.
-
Em seguida a questão que surgiu foi: essas geometrias
não-euclidianas possuíam
representatividade ao que chamamos consensualmente de mundo
real? O que muitas
vezes soava como controverso é que este tipo de geometria não
euclidiana descrevia o
espaço de maneira não linear e estático, muitas vezes
assemelhando-se, em certo
aspecto, a uma espécie de esfera3.
Outra questão é que dependendo do cálculo geométrico que
estivéssemos
dispostos a construir, os postulados nem sempre coincidiam com o
plano da intuição
comum compatível com o mundo enxergado sob o plano de três
dimensões, de modo
que, embora esses novos sistemas permitissem derivar uma gama
válida de muitos
teoremas, seus pressupostos em última instância, os tornavam
mutuamente excludentes.
Esse contexto fez com que os matemáticos do século XIX
presenciassem uma
certa angústia por parte da comunidade, mas também
desenvolvessem um interesse
novo e profundo pelo método geométrico e suas particularidades.
Foi aí que então
surgiu um dos principais desafios. Criar um modelo autônomo de
conhecimento que
fosse capaz compatibilizar os novos tipos de geometrias sem que
em último caso fosse
preciso recorrer a intuição humana para validação dos
postulados.
Ao mesmo tempo, com sistemas excludentes mas igualmente validos
para a
pesquisa matemática, surge a necessidade de se rever os próprios
fundamentos da
matemática pois sua validade e objetividade, celebrada desde os
tempos da Geometria
de Euclides passaram agora a não parecer mais tão obvia. A
partir de diferentes
postulados podemos construir teorias alternativas. Como fica a
verdade de tais teorias?
O Programa de Hilbert
O matemático David Hilbert (1862-1943) foi um dos personagens
mais
engajados na missão de elaborar um projeto capaz de contemplar
os novos tipos de
geometrias que vieram a surgir ao longo do século XIX 4 . Para
Hilbert, dispor a
geometria em um fundamento rigoroso era mais importante do que
prover a solução dos
próprios teoremas.
3 Greenberg, Euclidean and Non-Euclidean Geometries, 290. 4
Reid, Hilbert, 25.
-
No início do século XX, Hilbert propôs uma lista de problemas
que precisavam
ser solucionados a fim de estabelecer uma base rigorosa para
toda a matemática. Os
problemas marcariam o início do novo século para a
matemática5.
Para isso criou o que ficou conhecido como programa de
fundamentos da
matemática. Na concepção de Hilbert, a construção de um sistema
matemático formal
começa com definições, axiomas e regras para construir teoremas
a partir dos axiomas,
através do uso de inferências lógicas válidas e bem definidas.
Idealmente, o sistema
resultante deve exibir algumas qualidades inter-relacionadas
(Consistência,
Completude, Decidibilidade)6.
A Consistência significa que dado um conjunto de axiomas, não
deve ser
possível derivar como resultado dois teoremas que se
contradizem. Por exemplo,
suponha que seja criado algum novo sistema matemático. Este
sistema contém axiomas
e regras que podem ser utilizados para derivar teoremas dos
axiomas estabelecidos. Isso
pode ser feito estabelecendo-se algumas regras. Essas regras
implicam a sintaxe do que
é conhecido como fórmula bem formada. É possível montar uma
fórmula bem formada
sem primeiro derivá-la do sistema e então demonstrar que é uma
consequência dos
axiomas.
Quanto a Completude, pode ser descrita como a capacidade de
derivar todas as
fórmulas verdadeiras dos axiomas. Obtém-se fórmulas verdadeiras
utilizando-se provas.
Se você não puder derivar uma determinada fórmula do axioma,
significa então que a
fórmula não é demonstrável, logo o sistema estará
incompleto.
Outro conceito importante colocado por Hilbert foi de
Decidibilidade ou
Entscheidung. Conceito que exigia um procedimento de decisão
para responder se um
determinado problema tinha solução ou não. Um problema de
decisão é uma questão
sobre um sistema formal com uma resposta do tipo sim-ou-não. Por
exemplo, o
problema: "dados dois números x e y, y é divisível por x? Ou
dado um determinado
número x, x é um número primo?". Esses são exemplos de problemas
de decisão.
Gödel: O Teorema da Incompletude e não demonstrabilidade da
Consistência
De um modo geral podemos afirmar que as pessoas comuns e os
matemáticos
em particular puderam lidar com números por milênios. A “mágica”
dos números
5 Reid, Hilbert, 148. 6 Reid, Hilbert, 168.
-
consiste no fato de que iniciando com poucos fatos (como os
axiomas da geometria
acima citados) podemos derivar muitas e muitas consequências –
os teoremas – fazendo
uso de argumentos baseados na lógica ordinária e que parecem
intuitivamente válidos.
Assim se aceitamos com válidos os axiomas de uma teoria, e os
argumentos das
derivações usam inferências válidas, podemos concluir que a
matemática é a ciência das
verdades. Por muitos séculos este era o quadro e não se requeria
um aprofundamento
dos fundamentos da matemática.
No entanto o século XIX como apontamos anteriormente assistiu a
crescente
necessidade em aprofundarmos nossos conhecimentos sobre os
fundamentos da
matemática e logo se percebeu que a forma tradicional de se
apresentar a matemática
era demasiadamente intuitiva e imprecisa. Mostrou-se necessário
formalizar o
formalismo, apresentar as provas matemáticas de maneira muito
mais precisa do que a
prática tradicional. Esta tarefa foi realizada com a construção
de teorias axiomáticas da
matemática apresentadas formalmente como teorias de primeira
ordem. Uma teoria de
primeira ordem tem seus símbolos básicos perfeitamente
definidos. A seguir são
definidas regras de formação de conjuntos de símbolos, as
formulas da teoria, ou seja,
definimos sua sintaxe. Assim saberemos qual conjunto de símbolos
da teoria é uma
formula bem formada e qual não é. Tudo preciso de tal modo que
um sistema mecânico
pode ser construído para determinar se um conjunto de símbolos é
ou não é uma
formula válida. Assim estamos prontos para eleger as formulas
bem formadas do
sistema que representaram nossos axiomas da teoria. A partir
destes teoremas
poderemos definir as regras de inferência logica que nos
permitirão engendrar deduções
até chegarmos aos nossos teoremas. Novamente queremos definir as
regras que nos
permitem avançar nas deduções de modo tão preciso que podemos
imaginar uma
máquina que possa checar se um determinado movimento é válido ou
não. Com estas
restrições nas formulações das teorias matemáticas, os problemas
de fundamentação da
matemática passaram a ser problemas sobre teorias axiomatizadas
de primeira ordem.
A questão apresentada por Hilbert sobre estas teorias e que
Gödel respondeu
com suas provas são: uma teoria axiomatizadas de 1a ordem
adequada para expressar a
aritmética é completa?7 Em outras palavras, todos os fatos que
conhecemos mais ou
menos de uma forma intuitiva e imprecisa possuem uma
demonstração rigorosa na
teoria? Podemos exibir sempre uma sequencia de formulas que
constituam uma
7 Yandell, Hilbert’s Problems and Their Solvers, 217.
-
demonstração da verdade apresentada. Provar esta questão
significa provar a
completude da teoria. Muitas provas completude foram
apresentadas antes de Gödel
mas todas tinham um defeito fatal: elas assumiam fatos sobre a
aritmética que não
haviam sido provados. É dizer eram provas que relativas que
assumiam determinados
fatos que tornavam o valor das provas apenas relativos. Era
preciso encontrar uma prova
absoluta. E esta foi a tarefa que Gödel enfrentou.
Em sua prova, que adianto, não se efetivou como completude, mas
pelo
contrário como Prova da Incompletude, Gödel precisou fazer com a
aritmética falasse
sobre ela mesmo! Ou seja Gödel desenvolveu um método de
codificação associando a
cada símbolo do sistema um único número8; a cada formula do
sistema novamente um
único número. E agora a relação entre conjuntos de formulas da
matemática torna-se
uma relação entre números. Assim se quero afirmar que um
determinado teorema possui
uma prova representada por um conjunto de formulas, eu
estabeleço uma relação entre
números também. Eu posso então falar da matemática usando apenas
a própria
linguagem da matemática. Para realizar esta tarefa Gödel cria o
sistema de numeração
de Gödel. E a seguir Gödel constrói uma formula particular,
conhecida como G, é uma
relação verdadeira entre números mas que não pode ser
demonstrada. Porque G não
pode ser demonstrada? Por uma simples razão: se assumirmos que G
é demonstrável,
segue que não G também seria demonstrável e a matemática não
seria consistente.
Assim se assumirmos a Consistência, provamos a Incompletude.
Fica então
demonstrada que a aritmética não é completa!!! 9
Como consequência desta prova, Gödel responde também a questão
da
demonstrabilidade da Consistência na matemática colocada por
Hilbert: Gödel
demonstra que se existisse uma prova da consistência da
matemática, haveria uma prova
de G; mas já havia demonstrado que existir uma prova de G
implica na prova de não G;
portanto existir uma prova da consistência implica formalmente,
logicamente, na prova
da inconsistência.10
Gödel responde assim negativamente a duas das questões
levantadas por Hilbert:
prova a incompletude e a não demonstrabilidade da
consistência.
8 Ernest & James. A prova de Gödel, 63. 9 Ernest &
James. A prova de Gödel, 74. 10 Ibid
-
O problema da Decibilidade
Na mesma época em que surgiram os resultados dos trabalhos de
Gödel, um
outro problema também estava em evidência, Hilbert propunha a
existência de um
procedimento de decisão geral ao qual seria capaz de analisar
fórmulas arbitrárias da
lógica matemática e chegar à conclusão se elas poderiam ou não
serem provadas pelo
próprio sistema formal. O procedimento de decisão existiria
mesmo que o sistema não
estivesse completo, ou seja, mesmo algumas de suas asserções não
fossem
demonstráveis. Tal procedimento de decisão identificaria as
fórmulas como verdadeiras,
mesmo que nenhuma delas pudessem ser comprovadas11.
Hilbert comentou, pela primeira vez, sobre a ideia de um
procedimento de
decisão em seu discurso em Paris 1900. Em 1917 em Zurique sobre
"Pensamento
Axiomático" Hilbert também abordou o problema da decisão de uma
questão
matemática em um número finito de operações. De todos os
aspectos dos sistemas
axiomáticos, segundo ele, a decidibilidade é o mais conhecido e
mais discutido, pois
estaria de acordo com suas palavras, relacionado a essência do
“pensamento
matemático”12. Para diversos tipos de fórmulas em lógica
matemática, os processos de
decisão já tinham sido desenvolvidos e na época nada indicava
que um processo de
decisão geral também não seria possível construir.
A Resposta de Alan Turing
A teoria de Turing, a princípio tinha como proposta justamente
apresentar uma
solução ao problema de decisão do programa de fundamentos da
matemática idealizado
por David Hilbert. Turing formulou sua teoria sob a publicação
do documento On
computable Numbers, with an Aplication to the
Entscheidungsproblem escrito e
publicado em abril de 1936. Este documento traz uma abordagem
para uma prova
matemática.
O método de sua prova descreve uma máquina de computação
ficcional de
operação simples e direta. Ele define essas máquinas para
trabalhar o que ele chama de
números de computação ou números computáveis.
11 Yandell, Hilbert’s Problems and Their Solvers, 240. 12
Yandell, Hilbert’s Problems and Their Solvers, 395.
-
Como primeiro exemplo, a máquina que Turing apresenta, calcula o
número 1/3
em forma binária (0.010101...). O segundo calcula um número
irracional
(0.001011011101111...). Ele comprova que as máquinas também
podem ser definidas
para calcular π, e, e outras constantes matemáticas bem
conhecidas. Suas máquinas
possuem um número finito de operações e representando estas
operações com números
elas são capazes de mostrar que cada máquina pode ser unicamente
descrita por um
único número inteiro denominado número de descrição.13
Turing também demonstra que é possível definir uma máquina
que
simplesmente não execute todo o processo de maneira plena ou
satisfatória em termos
de resultados.
Como as máquinas de Turing são inteiramente definidas por um
número de
descrição, é possível criar uma máquina de Turing que analise
estes números de
descrição para determinar se uma máquina particular é
satisfatória ou não? Turing prova
que isto não é o possível: Não há nenhum processo geral que
determine se uma máquina
de Turing é satisfatória ou não, logo nenhum algoritmo de modo
geral pode existir ao
passo que possa analisar o resultado da execução de outro
algoritmo com uma certa
entrada e determinar sua validade.
Isso deu origem ao que hoje ficou conhecido como Problema da
Parada14, pois
trata-se em outras palavras de decidir se um dado programa é um
algoritmo. O problema
da parada é um interessante exemplo do que um computador não
consegue realizar
como tarefa. Ele consiste em demonstrar que todos os
computadores que já foram ou
que serão construídos baseados na estrutura das máquinas de
Turing, sempre que forem
processados com dados de entrada, podem parar depois de
processar a informação ou
então entrar em um loop infinito, não permitindo que tenhamos a
percepção do
encerramento da execução do processo.
Uma evidência da complexidade deste problema é que, se
pudéssemos resolvê-
lo, também poderíamos resolver muitos outros problemas famosos
de matemática não
solucionados até então. Por exemplo, a Conjectura de Goldbach ao
qual diz que todo
número par maior ou igual a 4 pode ser descrito como a soma de
dois números primos.
De fato, decidir se o programa sempre para, equivale a
demonstrar a verdade da
conjectura de Goldbach.
13 Hodges, Alan Turing, 60. 14 Ibid
-
No caso, a teoria de Turing tinha como proposta justamente
comprovar que não
há programa capaz de resolver o problema da parada15. Seguindo
esta linha Turing cria
um exemplo de máquina utilizando a simbologia da lógica aos
moldes e requisitos do
problema proposto pelo programa de fundamentos e assim chega à
conclusão que o
método geral para o Entscheidungsproblem de Hilbert é insolúvel,
ou seja, o problema
de decisão de Hilbert não pode ter solução16.
Turing e a ideia da Máquina Universal
A máquina que Turing descreve em uma das seções do seu artigo,
ficou conhecida
como a Máquina de Turing Universal, assim chamada pelo fato de
ser a única máquina
que se precisa para implementar todos os processos de
computação. A máquina
universal, pode simular outras máquinas quando implementadas com
seus números de
descrição. A Máquina Universal é o que podemos hoje dizer de
máquina programável.
Desde que Turing formulou o conceito de número computável, ou
seja, a
Máquina de Turing Universal (UTM)17, os matemáticos puderam
desenvolver sobre esta
teoria uma poderosa ferramenta essencialmente empregada para
determinar a validade
da execução de um algoritmo na resolução de um problema baseado
em uma
determinada entrada de dados. Assim, hoje a ideia de máquina
universal representa a
base conceitual de todos os computadores digitais modernos.
Fisicamente uma UTM é comumente implementada com base na
arquitetura von
Neumann, podendo ser representada como um dispositivo que requer
uma unidade
central de processamento (CPU), memória, entrada e saída de
dados.
15 Ibid 16 Turing, On computable numbers, 231. 17 Davis,
Computability & Unsolvability, 54.
-
18
Outro aspecto importante sobre a máquina de Turing Universal e
que devemos
considerar como algo inerente a todo sistema de computação, é
que os softwares
também são inteiramente definidos por números de descrição, uma
espécie de
identidade de cada programa, de modo que não podemos implementar
um programa que
analise os números de descrição de outros programas a fim de
determinar se tais
programas em particular são executáveis. A estrutura dos
computadores implementados
com base nas máquinas de Turing comprovam que isto não é o
possível, logo não há
nenhum processo geral que determine se um programa é executável
ou não. Em suma,
deve-se realmente executar o sistema para poder determinar o que
será apresentado
como resultado. O que vale para as máquinas de Turing também se
aplica aos
programas de computador, em geral, não é possível que um
programa de computador
analise o outro, exceto através da simulação de programa passo a
passo ou processo de
depuração19. Isto é aplicado independente do tipo de linguagem
de programação que
esteja sendo utilizada para criar o software.
Reflexões finais
Alguns aspectos das demonstrações aqui apresentadas nos chamam
atenção e
nos aproximam de problemáticas da computação, como apontado nas
construções de
Turing. Em seu sistema de numeração Gödel utiliza os números
primos para garantir a
18 Figura1: A CPU contém uma unidade de controle que direciona a
operação da máquina e todas funções aritméticas e lógicas
necessárias à execução da máquina. A memória serve para armazenar
e
organizar o encadeamento das informações conforme os dados de
entrada. A saída representa o resultado
do ciclo de processamento. 19 Bispo, A Teoria da Computação de
Alan Turing, 36.
-
relação um a um entre os símbolos e os números. O uso de números
primos não se
tornariam a chave para criptografia na computação? E por último
e talvez a reflexão
mais desafiante, o fato de Gödel construir um método que nos
permite falar da
matemática usando relações matemáticas não seria um ensaio
teórico da futura
construção de algoritmos na computação?
Além das relações já apontadas entre os trabalhos de Gödel e
Turing em relação
ao futuro do desenvolvimento da computação, apontando para as
questões teóricas da
fundamentação da matemática que antecederam o mundo das máquinas
eletrônicas, fica
também uma questão mais profunda para nossa reflexão. As
respostas negativas ao
programa de Hilbert que em duas décadas completarão um século de
exame e
confirmação dos lógicos matemáticos, devem ou não significar uma
limitação aos
avanços da inteligência artificial que hora assistimos? Os
limites formais do pensamento
da lógica formal implicam em limites para os cérebros
eletrônicos?
Vamos terminar recordando que Mário Schenberg em seu livro
Pensando a
Física coloca os resultados de Gödel como talvez a maior
revolução científica do século
XX, talvez só comparável na história da ciência com a descoberta
dos números
irracionais pelos gregos20. Cremos que vale a pena seguir a
intuição de Schenberg e
ainda refletirmos com intensidade e profundidade os teoremas
aqui apresentados.
Referências
BISPO, Danilo Gustavo. A Teoria da Computação de Alan Turing.
Tese de doutorado
em História da Ciência, Pontifícia Universidade Católica de São
Paulo, São Paulo,
2018. p. 36
CARNIELLI, Walter & RICHARD L. Epstein. Computability:
Computable Functions,
Logic and the Fundations of Mathematics. 3ª ed. Novo México:
ARF, 2008.
20 Schenberg, Pensando a Física, 32-33.
-
DAVIS, Martin. Computability & Unsolvability. 2ª. ed. New
York: Dover Publications,
1982. p. 54
GREENBERG, Marvin J. Euclidean and Non-Euclidean Geometries:
Development and
History. 4ª. ed. New York: W.H. Freeman and Company, 2007.
p.177-290
KÖRNER, Stephan. Uma introdução à filosofia da matemática. Rio
de Janeiro: Zahar,
1985.
YANDELL, Ben H. The Honors Class: Hilbert's Problems and Their
Solvers. Natick: A
K Peters LTD, 2002. p. 217-240-395
HILBERT & Ackermann. Principles of Mathematical Logic. Trad.
e ed. Cyril S. Smith,
& Martha T. Gnudi. Mineola, Chelsea Publishing Company,
1950.
HODGES, Andrew. Alan Turing: The Enigma. New York: Walker &
Company, 2000.
p. 60
NAGEL, Ernest & NEWMAN James. A prova de Gödel. Trad. Gita
K. Guinsburg. 2ª.
ed. São Paulo: Editora Perspectiva, 2009. p.63-74
MARIO, Schenberg. Pensando a Física. São Paulo: Editora Landy,
2001. p.32-33
REID, Constance. Hilbert. New York: Springer-Verlag, 1996. p.
25-148-168
-
Stanford Encyclopedia of Philosophy. “Classical Logic.” Stanford
Encyclopedia of
Philosophy. https://plato.stanford.edu/entries/logic-classical
(acessado em 15 de julho de 2018).
Stanford Encyclopedia of Philosophy. “Kurt Gödel.” Stanford
Encyclopedia of
Philosophy. https://plato.stanford.edu/entries/goedel (acessado
em 16 de julho de 2018).
THOMAS L. Heath. The Thirteen Books of Euclid’s Elements,
Cambrige University
Press, 1926, Dover Publications, 1956. p.154-155
TURING, Alan. “On Computable Numbers, with an Application to
the
Entscheidungsproblem”
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
