Capa: Fotografia de Kurt Gödel e Albert Einstein em Princeton, New Jersey, em 5 de dezembro de 1947, por Oskar Morgenstern (Foto: Cortesia do Arquivo do IAS).

Ao término de cada semestre, ao ministrar uma disciplina teórica, solicito que os alunos elaborem ensaios relacionados ao tema como parte da avaliação. Essa prática visa estimular uma reflexão ampla, indo além dos tópicos convencionais da ementa, permitindo a expressão de ideias por escrito, com a opção de utilizar a Inteligência Artificial, como o ChatGPT, para aprimoramento na edição. Neste semestre, em “Métodos Matemáticos da Física Teórica 1” (Álgebra Linear) observei alguns ensaios notáveis em termos de conteúdo e redação. Isso me motivou a convidar os alunos responsáveis para colaborarem na adaptação desses ensaios em artigos para este nosso site sobre IA, o ai-talks.org. Particularmente, gostaria de destacar o trabalho das alunas Letícia e Aishã, bem como o vídeo produzido por Arthur, acessível por meio do link fornecido no final deste artigo, explorando de forma aprofundada o(s) teorema(s) da incompletude de Gödel. Agradeço a todos os alunos, pois é por meio deles que continuo a aprender e aprimorar meu conhecimento.

Maurício Pinheiro
14/12/2023

---

Gödel, Turing, a Teoria de Tudo e Máquinas Inteligentes

Letícia Silveira Martins, Aishã Yasmim Rodrigues
(Discentes, Dep. de Física/UFMG)
Prof. Maurício Veloso Brant Pinheiro
(Dep. de Física/UFMG)

Keywords:  Gödel,Argumento de Diagonalização, Bertrand Russell, Cantor, Equação de Deus, Formalistas, Hilbert, IA, Infinito, Inteligência artificial, Intuicionistas, Lógica, Máquinas Inteligentes, O problema da Decisão, Os Problemas de Hilbert, Penrose, Problema da Parada, Stephen Hawking, Teoremas da Incompletude de Gödel, Teoria de Tudo, Turing.

---

Wir müssen wissen, wir werden wissen!
(Nós precisamos saber, nós saberemos!) — David Hilbert

O feito de Kurt Gödel na lógica moderna é singular e monumental — de fato, é mais do que um monumento, é um marco que permanecerá visível por muito espaço e tempo. … O tema da lógica certamente mudou completamente sua natureza e possibilidades com o feito de Gödel. — John von Neumann

É quase inacreditável que os sistemas educacionais atuais não tenham extinguido, por completo, a nobre chama da inquietação intelectual. — Albert Einstein

---

1 – Introdução

Desde o ideal visionário de uma matemática imaculadamente completa, concebido por David Hilbert, até a investigação meticulosa de Kurt Gödel sobre a incompletude de sistemas matemáticos e a visão perspicaz de Alan Turing sobre a impossibilidade de determinar o desfecho de todos os programas de computador, empreenderemos aqui uma jornada fascinante. Iniciaremos nossa exploração imergindo no contexto histórico que precede os teoremas de Gödel, destacando a obra de Cantor em sua tentativa de compreender o conceito de infinito. Este esforço desencadeou o embate entre Intuicionistas e Formalistas, culminando nos teoremas de incompletude de Gödel.

Examinaremos dos 23 problemas propostos por Hilbert, três questões cruciais para a matemática e a computação: 1) “A matemática é completa e, portanto, existe uma maneira de provar toda declaração verdadeira?”; 2) “A matemática é consistente e, portanto, completamente livre de contradições?”; e 3) “Existe algum algoritmo capaz de determinar se uma declaração segue diretamente dos axiomas?”.

Na sequência, abordaremos os próprios teoremas de Gödel e como eles respondem às duas primeiras perguntas. A terceira parte nos conduzirá para além dos números e da matemática, explorando o Problema da Parada de Turing como uma barreira intransponível na busca por um algoritmo universal que determine o término de todos os programas. Aqui, mergulharemos no domínio da computação, confrontando as limitações fundamentais que Turing impôs à capacidade dos sistemas formais de decidir questões cruciais, respondendo assim à terceira pergunta.

Prosseguindo, dirigiremos nossa visão para o horizonte do futuro da ciência e do conhecimento humano, questionando se alcançaremos um dia a maestria sobre todas as verdades do universo. Essa busca será fundamentada na ciência natural mais fundamental de todas as áreas do conhecimento científico, a Física, e em sua ferramenta mestra, a Matemática. Estabeleceremos conexões entre os teoremas de Gödel e a realização de uma Teoria de Tudo, inspirados pelas perspectivas de Stephen Hawking.

Por fim, na conclusão, refletiremos sobre a influência desses teoremas fundamentais no desenvolvimento da inteligência artificial e na busca pela autoconsciência das máquinas. Nesse contexto, ecoam ideias pouco convencionais, como as de Roger Penrose, físico, filósofo e ganhador do Prêmio Nobel, que sugere que máquinas verdadeiramente inteligentes serão limitadas por esses teoremas, incapazes de atingir a consciência e outras características notavelmente humanas, como a intuição.

Num mundo onde ciência se entrelaça com filosofia, este artigo busca desvendar os mistérios subjacentes aos números, algoritmos e à busca eterna pelo conhecimento, desafiando-nos a refletir sobre o verdadeiro alcance de nossa compreensão e a persistência diante das incertezas que o universo nos apresenta. Prepare-se para uma jornada que ultrapassa os limites do compreensível.

2 – Contexto Histórico

2.1 – Cantor, a Teoria de Conjuntos e quão grande pode ser um infinito

A odisseia que antecedeu as revelações consequentes do trabalho de Gödel envolveu diversos paradoxos e conflitos entre diferentes escolas de pensamento. Para explorar essas origens, precisamos retroceder até 1874. Nesse ano, o matemático Georg Cantor publicou um artigo que deu início a uma nova área da matemática, hoje conhecida como Teoria dos Conjuntos.

Sabemos da existência de vários conjuntos como os dos números naturais (ℕ), formados por todos os inteiros não negativos, assim como dos irracionais (ℝ-ℚ), compostos pelas dízimas não periódicas e raízes não exatas, e dos reais (ℝ) e complexos (ℂ), que englobam todos esses conjuntos e outros mais.

Durante a formulação dessa teoria, Cantor demonstrou que alguns infinitos são maiores que outros, como, por exemplo, o conjunto dos números reais (ℝ) sendo maior que o conjunto dos números naturais (ℕ). Essa tese foi comprovada por meio do Argumento de Diagonalização (ver no Apêndice 1). Nesse método, Cantor prova que existem conjuntos infinitos que não podem ser colocados em correspondência um a um com o conjunto infinito dos números naturais.

A verdade é que este foi apenas uma das gota d’água em um enorme oceano de descobertas matemáticas que estavam obrigando os pesquisadores do ramo a talvez ponderar as antes pensadas tão sólidas fundamentações da área. Por 2000 anos a geometria euclidiana havia sido considerada como única, até que no século XIX, Gauss e Lobachevsky descobriram geometrias não euclidianas, forçando-os a analisar novamente conceitos tão bem fundamentados. Agora, após o desenvolvimento do Cálculo e uma melhor aceitação da concepção de infinito (ou infinitos), talvez os matemáticos estivessem acabando de perceber que eles não conheciam nada acerca desse conceito tão abstrato e que era o coração de uma de suas áreas mais importantes. 

2.2 – Intuicionistas versus Formalistas

Cantor obviamente dividiu a comunidade, deixando de um lado os Intuicionistas, os quais pensavam que seus trabalhos não faziam o menor sentido e podiam ser considerados praticamente uma heresia matemática, defendendo que a mesma era uma invenção puramente humana, e que infinitos como os de Georg além de absurdos não eram reais. Do outro lado estavam os Formalistas, que defendiam que a matemática poderia ser completamente fundada em embasamentos lógicos baseados na Teoria de Conjuntos de Georg Cantor. Entre os integrantes do primeiro grupo poderíamos encontrar Henri Poincaré, o qual afirmava que “as gerações futuras iriam se lembrar da Teoria dos Conjuntos como sendo uma doença a qual felizmente os matemáticos teriam se curado“. Já do outro lado, estava David Hilbert, com o qual começamos este texto lhe fazendo referência. 

Hilbert liderava indiretamente os formalistas, e era um defensor ávido das ideias de Cantor. Entretanto, em 1901, Bertrand Russell percebeu que as ideias de Cantor, por mais bem fundamentadas que fossem, poderiam levar a uma contradição. Este resultado ficou conhecido como Paradoxo de Russell e é um paradoxo lógico (Dialético) exemplificado por Russell pelo famoso Paradoxo do Barbeiro (ver no Apêndice 2).

Para compreender o Paradoxo de Russell, considere inicialmente o conjunto Absoluto. Para simplificar a notação, vamos nos referir a Absoluto apenas como A. Iremos defini-lo como o conjunto de todos os conjuntos que não possuam a si próprios como elementos. Se todos os conjuntos estão formando o conjunto A, então ele não pode ser um conjunto, e daí surge o paradoxo: não existe conjunto de todos os conjuntos, nem classe de todas as classes. Quando se diz que a classe está dentro de todas as outras, então se diz que ela é maior que ela mesma, e isto, obviamente, é um absurdo. Formulando isso formalmente temos: E é elemento de A se, e somente se, E não é elemento de E. 

A = {E | E ∉ E} 

Na teoria definida por Cantor, A é um conjunto bem definido. Será que A contém a si mesmo? Se sim, não é membro de A de acordo com a definição. Por outro lado, supondo que A não contém a si mesmo, tem de ser membro de A, de acordo com a definição de A. Assim, as afirmações A é membro de A e A não é membro de A conduzem ambas a contradições. 

Por mais que este Paradoxo mostre que a Teoria de Conjuntos de Cantor tinha uma falha enorme, Zermelo e outros matemáticos ligados à Hilbert resolveram o problema limitando o conceito de conjuntos e fazendo com que conjuntos como A não sejam mais considerados conjuntos. 

Com isto, Hilbert queria garantir de uma vez por todas que a matemática estivesse construída por cima de uma base tão sólida que fosse impossível que problemas como este tornassem a acontecer. Basicamente, ele almejava desenvolver um sistema de provas que fizesse menção a métodos que remontavam a Grécia Antiga, começando com Axiomas – que seriam declarações básicas as quais seriam tomadas como verdadeiras – , e a partir das quais, outras declarações seriam derivadas, a fim de manter essas verdades – os Teoremas.

Entretanto, este novo sistema seria baseado em uma linguagem simbólica com uma lista rígida de manipulação desses símbolos. Tal sistema foi desenvolvido e publicado no livro Principia Mathematica, que é uma obra de três volumes sobre fundamentos da matemática escrita por Alfred North Whitehead e seu aluno Bertrand Russell, e publicada nos anos de 1910, 1912 e 1913. Sendo extremamente grande, confuso e de notação densa, seus autores desistiram de publicar um quarto volume por alegarem estar exaustos demais com a elaboração dos três primeiros. Entretanto, mesmo que demorando cerca de 700 páginas para simplesmente provar que 2+2=4, o sistema desenvolvido se mostrou extremamente eficiente em evitar erros e paradoxos estranhos surgidos de contradições lógicas, provando-se extremamente exato, e acima de tudo, permitindo que fossem refutadas objeções acerca dele mesmo (o sistema lógico). 

Além disso, também haviam 3 perguntas que Hilbert gostaria que fossem respondidas acerca da Matemática. Essas três perguntas faziam parte da famosa lista intitulada “Os Problemas de Hilbert”, a qual contém 23 problemas em matemática propostos na conferência do Congresso Internacional de Matemáticos de Paris em 1900. Nenhum dos problemas havia tido solução até então, e vários deles acabaram se tornando muito influentes na matemática do século XX. Os três problemas de fundamental interesse a este trabalho podem ser descritos da seguinte forma: 

• A matemática é completa, e portanto, existe alguma forma de provar toda declaração dita verdadeira? 

• A matemática é consistente, e logo, completamente livre de contradições? 

• Existe algum algoritmo capaz de determinar se alguma declaração segue diretamente de algum dos axiomas? 

Para Hilbert, a resposta para todas essas questões era sim: “Em oposição a tolice do Ignorabimus, nosso slogan deve ser nós precisamos saber, nós iremos saber!“. Estas foram as palavras proferidas por ele na reunião anual de 1930 da Sociedade Alemã de Cientistas e Físicos, um dia após Kurt Gödel, em uma mesa redonda durante Segunda Conferência sobre a Epistemologia das Ciências Exatas, realizada em Königsberg, ter anunciado a primeira expressão de seu Teorema da Incompletude. 

3 – Nem tudo que é verdade pode ser provado: os Teoremas da Incompletude de Gödel 

Mas para o filósofo, matemático e lógico austríaco Kurt Friedrich Gödel, a resposta para duas destas três perguntas seria não. 

Gödel usou lógica e matemática para provar afirmações sobre a lógica e a matemática. Ele basicamente formulou uma espécie de jogo de cartas (uma metalinguagem matemática), onde pegou cada um dos símbolos matemáticos que existiam, e deu a eles um número em uma carta, o número de Gödel. O número zero, teria como número de Gödel 6, e para escrever o número 1, seria colocado o 0 e o número correspondente ao símbolo de sucessor imediato de. Assim seria feito com todos os demais números. 

Portanto, a equação 1 = 1 (simbolicamente S0=S0) teria como números de Gödel 7, 6, 5, 7 e 6. Também seria possível criar um número único para cada equação, pegando os números primos e elevando eles a cada um dos números de Gödel que representam essa equação. Teríamos então o número: 

1=1 => 2⁷· 3⁶· 5⁵· 7⁷· 11⁶ = 4,25432 · 10²⁰ 

4,25432 · 10²⁰  é o número de Gödel da equação 1 = 1.

A beleza deste sistema desenvolvido por Gödel é que cada constatação terá um número único, e cada número pode ser fatorado a fim de descobrir quais são seus símbolos primários, e assim, ter de volta o conjunto de cartas e números primordiais. Nesse deque infinito, terão afirmações que são verdadeiras e afirmações que são falsas. Para prová-las é necessário recorrer aos axiomas, que também terão números de Gödel próprios. Entretanto, como essas declarações começam a ficar muito complexas, seus números começam a ficar extremamente gigantes, e letras serão introduzidas para representá-los e simplificar a notação. 

O número de Gödel mais importante é aquele da afirmação que diz não existe prova para a afirmação com Número de Gödel g. Entretanto, o número de Gödel desta afirmação é g. 

Logo essa carta não possui prova, e não existe nenhuma carta em nosso deque com números de Gödel infinitos, que contenha uma prova para ela. Mas se ela for falsa, e tiver uma prova, o que provamos  é que ela é verdadeira e não possui prova. Por fim, iremos acabar em um loop, um paradoxo, uma contradição. Isso implicaria que esse sistema criado por Gödel é inconsistente. 

Caso ela fosse verdadeira, e realmente não há nenhuma prova, isso mostraria que o sistema é incompleto, e é exatamente isso que o Primeiro Teorema da Incompletude de Gödel nos diz.

Teorema 1: Qualquer teoria axiomática recursivamente enumerável e capaz de expressar algumas verdades básicas de aritmética não pode ser, ao mesmo tempo, completa e consistente. Ou seja, em uma teoria consistente, sempre há proposições que não podem ser demonstradas nem verdadeiras, nem falsas. 

Este primeiro Teorema mostraria que a resposta para a primeira pergunta de Hilbert (A matemática é completa, e portanto, existe alguma forma de provar toda declaração dita verdadeira? ) é NÃO. Algumas pessoas poderiam esperar que a resposta para a segunda questão teria alguma abertura para ser respondida com um SIM, porém pouco tempo mais tarde, o Segundo Teorema da Incompletude de Gödel viria esmagar os sonhos de perfeição de Hilbert e tantos outros matemáticos. 

Teorema 2: Uma teoria, recursivamente enumerável e capaz de expressar verdades básicas da aritmética e alguns enunciados da teoria da prova, pode provar sua própria consistência se, e somente se, for inconsistente. 

Verdade e provabilidade não são equivalentes. Hilbert estava errado, e sempre haverão verdades na matemática que não poderão ser provadas. Não só isso, mas qualquer sistema consistente formal da matemática não pode provar sua própria consistência. Dessa forma, o melhor que os matemáticos podem esperar é um sistema consistente porém incompleto, sendo que um sistema desses não pode provar sua própria consistência, e portanto, alguma contradição poderá sempre em algum futuro próximo aparecer e jogar por terra todo esse sistema. E assim a resposta da segunda pergunta de Hilbert (A matemática é consistente, e logo, completamente livre de contradições?) também é NÃO.

4 – Turing, Indecidibilidade e o Problema da Parada

A última pergunta (Existe algum algoritmo capaz de determinar se alguma declaração segue diretamente de algum dos axiomas?) foi respondida em 1936 por Alan Turing, e para respondê-la foi necessária a criação do computador. Dessa forma, iremos deixar a matemática de lado por um momento, e começaremos a pensar em termos da computação. 

Assim como o os Teoremas da Incompletude de Gödel, o Problema da Parada, introduzido por Alan Turing, explora as limitações de sistemas formais, principalmente sobre a questão da indecibilidade. Em essência: o Problema da Parada demonstra que não existe um algoritmo que poderia decidir, para todas as Máquinas de Turing e para todos os inputs possíveis, se o programa iria parar ou não.

Similarmente ao Teorema de Gödel, o Problema também nasce da questão da formalização (neste caso da formalização da noção de computação) e da exploração das ideias de David Hilbert. Um dos desafios propostos pelo matemático ficou conhecido como Entscheidungsproblem (O problema da Decisão), onde ele questionava se existe algum algoritmo geral capaz de decidir se proposições matemáticas são verdadeiras ou falsas.

Em um artigo publicado em 1936, Turing buscava definir um modelo matemático preciso para a computação e, para tanto, ele introduziu o conceito de Máquinas de Turing: uma máquina teórica capaz de executar algoritmos mediante um conjunto finito de regras.

Nesse contexto, o trabalho do matemático diante do desafio de Hilbert foi formular o Problema da Parada que, ainda que simples, contém uma profundidade admirável.  O Problema da Parada reside na seguinte pergunta:

Dada uma descrição arbitrária de uma Máquina de Turing e seu input inicial, é possível determinar se essa máquina, após ser iniciada com o input informado, irá parar em algum momento ou continuará rodando indefinidamente?

A partir do argumento de diagonalização (o mesmo utilizado por Cantor e Gödel), Turing demonstrou que tal processo algorítmico é impossível, de forma a estabelecer um limite fundamental naquilo que pode ser decidido por meio de algoritmos e marcando o nascimento da área da Teoria da Computação. Uma demonstração do Problema da Parada se encontra no Apêndice 3. Um exemplo de um problema de parada simples, o do cálculo de números Palíndromos, implementado em Python está no Apêndice 4.

As similaridades entre os recursos argumentativos usados por Gödel e por Turing no estudo da indecidibilidade são notáveis, além de terem permitido uma exploração mais detalhada entre os paralelos dos trabalhos dos dois matemáticos. 

Dizemos, por fim, que o Problema da Parada é Indecidível nas Máquinas de Turing, e assim, trazendo esse resultado para a matemática, que esta não é decisiva. 

No âmbito da Física Quântica, uma das propriedades mais relevantes de sistemas de vários corpos está nas Lacunas Espectrais (ou Gaps de energia proibida), ou seja, a diferença de energia entre o estado fundamental e o primeiro estado excitado. Isso posto, existem sistemas que contêm essa descontinuidade entre esses estados, apresentando um gap ΔE entre eles conhecidos como sistemas com Gap (como semicondutores e isolantes); enquanto que outros são classificados como sem Gap por terem uma continuidade nos níveis de energia até o estado fundamental (metais).

Nesse contexto, em baixas temperaturas, sistemas com Gap precisam de uma determinada quantidade de energia para superar esse Gap de energia e, logo, não conseguem passar por transições energéticas que sistemas sem Gap são capazes. Apesar de ser uma diferença notável entre ambos sistemas, foi recentemente provado que, em geral, é impossível saber se dado uma Hamiltoniana, um sistema quântico de muitos corpos tem gap, ou não, e esta questão carrega consigo a Indecidibilidade para a grande maioria das situações. Um trecho do artigo que sintetiza bem essa ideia (Cubitt, Toby S., et al. “Undecidability of the Spectral Gap.” Nature, vol. 528, no. 7581, Dec. 2015.) e a relação dos temas tratados neste trabalho é (em tradução livre):

“Mesmo uma descrição perfeita e completa das interações microscópicas entre as partículas de um material nem sempre é o suficiente para deduzir suas propriedades macroscópicas.”

A demonstração consiste na formulação de uma Hamiltoniana para o estado fundamental que codifica a evolução de um algoritmo de estimativa de fase quântica e é seguida por uma Máquina de Turing Universal. Desse modo, o Gap espectral depende do resultado do Problema de Parada correspondente, implicando na não existência de um tal algoritmo e, consequentemente, também resulta no fato de que existem modelos para representar essa questão de presença ou não do Gap espectral que independem de axiomas matemáticos. 

Podemos considerar que o real legado do tão belo, porém irreal sonho de Hilbert na atualidade são todos os nossos sistemas computacionais. Já para a matemática, o sonho de Hilbert provocou Gödel a nos trazer uma verdade difícil de engolir, mas capaz de nos dar um pouco de esperança. 

5 – Algum dia saberemos todas as verdades do Universo? A Teoria de Tudo e a Equação de Deus

Desde os primórdios de sua existência, a raça humana tem tentado desvendar mistérios que permeiam o cerne de sua vida e o propósito da mesma. Somos curiosos por natureza, e questões têm nos guiado ao longo de toda a história. Sem nos indagarmos demais, não estaríamos onde estamos hoje. Sem ousadia e sonhos que poderiam se concretizar ou não, talvez nunca tivéssemos avançado como espécie. 

A cada dia que se passa, dominamos mais e mais a natureza. Temos certeza de que nosso conhecimento é tão excelente, que o sonho que mais tem intrigado e motivado os físicos nas últimas décadas é o da possibilidade de obter em breve uma Teoria de Tudo. Albert Einstein passou 30 anos da sua vida em busca de uma equação que unificasse as quatro forças fundamentais do universo: a gravidade, a força eletromagnética e as duas forças nucleares. O objetivo era encontrar uma única teoria que as englobasse, uma Equação de Deus. 

Uma gama enorme de cientistas têm dedicado suas vidas em busca dela. Stephen Hawking, por muitos anos um dos maiores nomes que se empenharam em obter essa conquista, se convenceu após muito tempo de que talvez esse sonho fosse inalcançável. 

— A verdadeira razão pela qual procuramos uma teoria completa é que queremos compreender o universo e sentir que não somos apenas vítimas de forças obscuras e misteriosas. Se compreendermos o universo, então o controlamos, em certo sentido. O modelo padrão é claramente insatisfatório neste aspecto. Em primeiro lugar, é feio e ad hoc. As partículas são agrupadas de forma aparentemente arbitrária, e o modelo padrão depende de 24 números cujos valores não podem ser deduzidos dos primeiros princípios, mas que devem ser escolhidos para se ajustarem às observações. Que entendimento há nisso? Poderá ser a última palavra da Natureza? […] O Teorema de Gödel é provado usando afirmações que se referem a si mesmas. Tais afirmações podem levar a paradoxos. Qual é a relação entre o teorema de Gödel e se podemos formular a teoria do universo em termos de um número finito de princípios? Uma conexão é óbvia. De acordo com a filosofia positivista da ciência, uma teoria física é um modelo matemático. Portanto, se existem resultados matemáticos que não podem ser provados, existem problemas físicos que não podem ser previstos. […] Embora isso seja uma espécie de incompletude, não é o tipo de imprevisibilidade a que me refiro. Dado um número específico de blocos, pode-se determinar com um número finito de tentativas se eles podem ser divididos em dois números primos. Mas acho que a teoria quântica e a gravidade juntas introduzem um novo elemento na discussão que não estava presente na teoria newtoniana clássica. Na abordagem positivista padrão da filosofia da ciência, as teorias físicas vivem gratuitamente num paraíso platônico de modelos matemáticos ideais. Ou seja, um modelo pode ser arbitrariamente detalhado e conter uma quantidade arbitrária de informações sem afetar os universos que descreve. Mas não somos anjos, que vemos o universo de fora. Em vez disso, nós e os nossos modelos fazemos parte do universo que estamos descrevendo. Assim, uma teoria física é auto referente, como no teorema de Gödel. Poderíamos, portanto, esperar que fosse inconsistente ou incompleta. As teorias que temos até agora, realmente são de fato, inconsistentes e incompletas. — Stephen Hawking

Como destacada por Hawking, somos habitantes desse Universo tentando desvendá-lo por meio de ferramentas repletas de auto-referências. As chances de que continuemos trabalhando por anos e anos a fio sem talvez nunca chegarmos a alguma conclusão satisfatória são bem maiores que 0. Existem limitações oriundas do nosso grau de avanço tecnológico que podem levar séculos, milênios para serem superados. Existem outros, intrínsecos a nossa natureza, leis que nos impeçam de ver mais longe e ter uma compreensão maior acerca de tudo aquilo que nos cerca. Não obstante, apenas no último século descobrimos que a matemática jamais poderá ser completa e se provar completamente consistente, além de que duas grandes teorias físicas tiveram de ser reformuladas, forçando os físicos a olharem para a realidade com outros olhos. A todo dia a ciência se expande, e somos obrigados a nos transformar completamente se quisermos continuar avançando. Talvez haja algumas pedras no caminho, mas precisamos sempre ser teimosos e obstinados para não desistirmos de nossos sonhos. Nossa mente jamais pode se fechar, por mais que às vezes ela tente fazê-lo inconscientemente, pois nenhum ser humano é perfeito o suficiente para estar livre de influências externas. Sequer as máquinas, inteligências as quais tentamos insistentemente replicar e forçar a serem como a nossa, talvez consigam fugir dessa influência. Afinal, nós as criamos, e possivelmente não conseguiremos evitar passar a elas inconscientemente traços nossos. 

Felizmente somos seres os quais sempre evoluem. Passamos por inúmeras metamorfoses, e nunca continuamos os mesmos. E essa foi a boa notícia que Gödel nos trouxe, e Hawking conseguiu enxergar. 

Hilbert disse que nós precisamos saber, nós iremos saber. A verdade dura que Gödel nos trouxe, é a de que nós não sabemos, e talvez nunca iremos. Algumas pessoas podem ficar desapontadas com isso, com a ausência de uma teoria tão bela e unificada, capaz de descrever o nascimento do universo e o seu fim. Mas a boa notícia é que o nosso conhecimento jamais terá um fim. A verdadeira beleza em ser um cientista não é constituída apenas das conclusões e objetivos que conquistamos, mas de todo o caminho e as descobertas que o recheiam, expandindo nossa mente ad infinitum. Saber que essa ferramenta a qual chamamos de ciência faz parte dos conjuntos incontáveis de Cantor, talvez seja a melhor coisa que um cientista possa ter descoberto. 

Nossa caçada pelo conhecimento nunca terá fim, e isso se deve ao fato de sempre termos o desafio de novas descobertas. Sem isso estaríamos estagnados. Nas palavras de Stephen Hawking, O teorema de Gödel garantiu que sempre haveria emprego para os matemáticos. Essa, sendo a linguagem do Universo, sob a qual toda a Física está pautada, talvez mostre que podemos estar em uma posição semelhante. 

6 – Conclusão: IA e Máquinas Inteligentes

Os teoremas de Gödel e o Teorema da Indecidibilidade de Turing representam marcos cruciais na matemática e ciência da computação, com implicações significativas para a inteligência artificial (IA). Publicado em 1931, o teorema da incompletude de Gödel, como vimos, revela limitações intrínsecas em sistemas axiomáticos, ao afirmar que nenhum sistema consistente e suficientemente rico pode provar todas as proposições verdadeiras dentro de si mesmo. Isso implica que sempre haverá verdades aritméticas que escapam à prova formal, desafiando a noção de um sistema axiomático perfeito. Em 1936, o Teorema da Indecidibilidade de Turing ampliou essas limitações ao demonstrar que não existe um algoritmo universal capaz de decidir se um programa de computador irá terminar ou não. Isso estabelece que não existe um algoritmo abrangente capaz de resolver todos os problemas de decisão. Essas conclusões revolucionaram a compreensão sobre os limites da computação e da lógica formal.

Quando aplicados à IA, esses teoremas sugerem que é impossível criar uma máquina inteligente que possa abarcar todas as verdades da aritmética ou resolver todos os problemas de decisão. Entretanto, essa impossibilidade não anula a viabilidade da inteligência artificial. Máquinas inteligentes podem, e de fato já o fazem, desempenhar tarefas complexas e desafiadoras, mesmo que não possuam a capacidade de abordar todas as facetas da inteligência humana.

Tomemos o xadrez como exemplo. Apesar de não existir um algoritmo perfeito que sempre vença, máquinas como o Deep Blue demonstraram uma notável capacidade de derrotar campeões humanos. A tradução automática é outro exemplo, onde algoritmos como o Google Translate realizam tarefas complexas de forma eficaz, embora não exista uma solução perfeita para a tradução de todos os textos.

Apesar desses sucessos, os teoremas de Gödel e Turing indicam que a inteligência artificial não pode reproduzir completamente a amplitude da inteligência humana. O físico e filósofo, premiado com o Nobel, Roger Penrose argumenta que a intuição humana, baseada em uma compreensão profunda da realidade, escapa à capacidade das máquinas inteligentes, pelo menos aquelas com computação clássica – não quântica. Ele enfatiza que, embora as máquinas possam realizar tarefas específicas com excelência, a compreensão holística e intuitiva da realidade permanece fora de seu alcance, estando segundo ele associadas a processos quânticos no nosso cérebro.

Essa discussão sobre a possibilidade das máquinas atingirem a inteligência humana continua sendo complexa e controversa. Enquanto os teoremas de Gödel e Turing oferecem uma base matemática sólida para essa reflexão, eles não proporcionam uma resposta definitiva. A IA permanece como uma área em constante evolução, desafiando os limites teóricos estabelecidos, enquanto a busca por compreender a verdadeira natureza da inteligência persiste.

---

7. Referências

Videos

Articles and Books

Cubitt, Toby S., David Perez-Garcia, and Michael M. Wolf. “Undecidability of the spectral gap.” Nature 528.7581 (2015): 207-211.

Ferreirós, José. “The crisis in the foundations of mathematics.” The Princeton companion to mathematics (2008): 142-156.

de Morais, Lauro Iane. “UMA BREVE INTRODUÇÃO AO PARADOXO DE RUSSELL: o que ele é, como ele afetou o sistema fregeano e sua possível solução.” O Manguezal—Revista de Filosofia 1.2 (2018). (Portuguese)

Aaronson, Scott. Quantum computing since Democritus. Cambridge University Press, 2013.

Ben-Ya’acov, Uri. “Gödel’s incompleteness theorem and Universal physical theories.” Journal of Physics: Conference Series. Vol. 1391. No. 1. IOP Publishing, 2019.

Beklemishev, Lev D. “Gödel incompleteness theorems and the limits of their applicability. I.” Russian Mathematical Surveys 65.5 (2010): 857.

Peregrin, Jaroslav. “Gödel, truth & proof.” Journal of Physics: Conference Series. Vol. 82. No. 1. IOP Publishing, 2007.

Yan, Yutong. “Gödel’s Incompleteness Theorem and Problems Outside Quantum Mechanics.” Journal of Physics: Conference Series. Vol. 2012. No. 1. IOP Publishing, 2021.

Penrose, Roger. The Emperor’s New Mind: Concerning Computers, Minds and The Laws of Physics. 1989. 

Links:

What Is Russell’s Paradox?

Kurt Gödel: O Filósofo Paranoico Que Provou a Incompletude Da Matemática. (Portuguese)

O Logicismo, O Formalismo E O Intuicionismo E Seus Diferentes Modos de Pensar a Matemática. (Portuguese)

Formal Computational Models and Computability.

How Gödel’s Proof Works. Quantamagazine

Godel and the End of Physics 

Cantor’s diagonal proof

O programa do palíndromo (Portuguese)

---

8 – Apêndices:

1. O Argumento de Diagonalização

Para entender o Argumento de Diagonalização, Cantor propôs o seguinte exercício:

Pegue uma folha de papel, e escreva de um lado todos os números naturais. Trace uma linha, e do outro lado, escreva um número real qualquer que esteja entre 0 e 1. Suponha que você tenha terminado essa lista, e ela seja completa e infinita. Agora, vamos escrever um novo número real entre 0 e 1. Pegue o primeiro dígito do primeiro número e adicione 1, então vá para o segundo dígito do segundo número, adicione 1 e continue repetindo esse processo até chegar ao último dígito do último natural. Você pode mudar a concepção deste número, escolhendo adicionar 2 ao invés de 1, ou até mesmo seu número favorito, o importante é que mude todos os dígitos. No fim deste processo, você terá um novo real que não apareceu em nenhum lugar desta lista, pois ele difere do n-ésimo real pelo seu  n-ésimo dígito. Este argumento é conhecido como o Argumento da Diagonalização de Cantor, e basicamente implica que devem existir mais números reais entre 0 e 1, do que números inteiros não negativos, e portanto, existem infinitos que são maiores do que outros. 

---

2. O Paradoxo do Barbeiro

O Paradoxo do Barbeiro se baseia na ideia de que existe um barbeiro em uma cidade que barbeia todos os homens que não se barbeiam a si mesmos. Se o barbeiro não se barbeia, então ele não deve barbear os homens que não se barbeiam a si mesmos, mas ele deve barbear os homens que não se barbeiam a si mesmos.
O paradoxo pode ser expresso da seguinte forma:

Hipótese: Existe um barbeiro em uma cidade que barbeia todos os homens que não se barbeiam a si mesmos.

Conclusão: O barbeiro deve barbear a si mesmo.

Se o barbeiro se barbeia, então ele se enquadra na definição de homem que não se barbeia a si mesmo. Portanto, ele deve ser barbeado pelo próprio barbeiro. No entanto, se o barbeiro se barbeia, então ele se enquadra na definição de homem que se barbeia a si mesmo. Portanto, ele não deve ser barbeado pelo próprio barbeiro.

A conclusão do paradoxo é que a hipótese é falsa, ou seja, não existe um barbeiro que barbeie todos os homens que não se barbeiam a si mesmos.

Outros exemplos de paradoxos dialéticos incluem:

O paradoxo do mentiroso: Um homem afirma que ele é um mentiroso. Se ele está dizendo a verdade, então ele está mentindo. Se ele está mentindo, então ele está dizendo a verdade. O paradoxo do mentiroso é um paradoxo de auto-referência. Ele se baseia na ideia de que uma afirmação pode ser falsa se ela se referir a si mesma. No caso do paradoxo do mentiroso, a afirmação é “Estou mentindo”. Se a afirmação é verdadeira, então ela é falsa. Se a afirmação é falsa, então ela é verdadeira.

O paradoxo de Epiménides: Epiménides, um cretense, afirma que todos os cretenses são mentirosos. Se ele está dizendo a verdade, então ele é um mentiroso. Se ele está mentindo, então ele está dizendo a verdade. O paradoxo de Epiménides é semelhante ao paradoxo do mentiroso. Ele também se baseia na ideia de que uma afirmação pode ser falsa se ela se referir a si mesma. No caso do paradoxo de Epiménides, a afirmação é “Todos os cretenses são mentirosos”. Se Epiménides é um cretense, então a afirmação é verdadeira se ele estiver mentindo, e falsa se ele estiver dizendo a verdade.

O paradoxo do navio de Teseu: Um navio está sendo restaurado, e cada peça original é substituída por uma peça nova. Quando o navio estiver completamente restaurado, será o mesmo navio original? O paradoxo do navio de Teseu é um paradoxo de identidade. Ele se baseia na ideia de que a identidade de um objeto não é determinada apenas por suas partes. No caso do paradoxo do navio de Teseu, o navio é identificado como um conjunto de peças que estão conectadas de uma certa maneira. Se todas as peças do navio forem substituídas por peças novas, o navio ainda será o mesmo navio original? Não há uma resposta fácil para esse paradoxo. Algumas pessoas acreditam que o navio ainda será o mesmo navio original, enquanto outras acreditam que ele será um navio novo.

Esses paradoxos são importantes para a lógica, pois eles demonstram que nem todas as proposições aparentemente verdadeiras são realmente verdadeiras. Eles também nos forçam a questionar nossas suposições sobre a natureza da verdade e da realidade.

---

3. Demonstração do Problema da Parada

Imaginemos que tenhamos um procedimento chamado Halts(P,D), que recebe como entrada um programa P e um dado D, e responde “sim” se P pára com D. No entanto, não podemos simplesmente simular o programa P no input D porque não sabemos se P vai parar ou entrar em um loop infinito. Uma solução seria considerar que o input D também pode ser um programa. Sob essa perspectiva, podemos criar um novo programa mais limitado chamado NewHalts(P), que testa se o programa P pára quando o input é uma cópia de P (assumindo que D é igual a P).

Além disso, podemos construir outro programa chamado Oposto(P) que faz o oposto do NewHalts(P).

Agora, vejamos o que acontece quando aplicamos o conceito de auto-referência, ou seja, as possibilidades para Oposto(Oposto(P)):

1. Se o programa Oposto(P) pára quando o input é ele mesmo, então Oposto(Oposto(P)) continua rodando indefinidamente.
2. Se o programa Oposto(P) não pára quando o input é ele mesmo, então Oposto(Oposto(P)) para.

Essas são situações mutuamente exclusivas – Oposto(Oposto(P)) pode apenas parar ou entrar em um loop eterno. Isso nos leva a uma contradição! Ao examinar os procedimentos usados pelo Oposto(P), percebemos que ele recorre ao programa NewHalts(P), que, por sua vez, depende do programa Halts(P,D). Considerando que nossa única suposição foi a existência do programa Halts(P,D), concluímos que, na realidade, esse procedimento algorítmico não pode existir! c.q.d (Obs: Optamos por utilizar a grafia ‘pára’ nesta demonstração, conforme a antiga ortografia da língua portuguesa antes do Acordo Ortográfico de 1990. Essa escolha visa destacar a forma verbal, indicando a ação de parar, em contraste com ‘para’, empregado em outras construções linguísticas, como preposição ou conjunção.)

---

4. Exemplo Prático de um Problema de Parada: Números Palíndromos

Para ilustrar com um exemplo prático o Problema da Parada de Turing solução deste problema, vamos considerar o código em Python abaixo que gera números palíndromos, ou seja, iguais a ele mesmo de trás-para-frente (e.g 123321): 

Nesse exemplo, a entrada é um número n. Se n for um número palíndromo (stdin = 121), ele é retornado (stdout=121). Se não for (e.g. stdin =13), desse número n=13, é produzido um número m=31 que é n de trás-para-frente, e então os dois são somados produzindo c=13+31=44 que é usado recursivamente como um novo n até que um palíndromo seja produzido e o programa parar. Para ficar claro o que o programa está fazendo, ele imprime na saída todos esses números que ele gera. 

A função lychrel termina quando a entrada é o número 196. Esse é outro problema matemático em aberto. A conjectura de Lychrel afirma que isso sempre ocorre. Um número de Lychrel é um número natural que não pode formar um palíndromo por meio do processo iterativo repetitivo de inverter seus dígitos e somar os números resultantes. Acredita-se que essa conjectura é falsa e que 196 seria o primeiro contra-exemplo dela, e portanto, o primeiro número de Lychrel. Como esse é um problema matemático em aberto, ninguém sabe a resposta, e após algumas bilhões de iterações que produzem números com bilhões de dígitos, um palíndromo insiste em não se formar. Porém, não se sabe se eventualmente um se formaria com um trilhão, um quadrilhão, um zilhão, quem sabe um googolplex de iterações, ou talvez, se de fato um nunca se formaria (um googolplex é dez elevado a um googol, que por sua vez é o dez elevado a cem). 

Se um programa termina – que é um programa capaz de inspecionar o código de outro programa para determinar se ele entra ou não em um laço infinito quando lhe entregue uma entrada qualquer, dando como saída Sim ou Não em um tempo finito – fosse examinar o programa lychrel para determinar se ele termina com a entrada 196, ele precisaria ser capaz de ou determinar quando ele terminaria ou então descobrir uma razão pela qual nunca terminaria, e com isso solucionar o Problema da Parada. Para fazer isso, esse programa termina não seria algo simples, e de acordo com Turing, ele não existe. 

---

Copyright 2024 AI-Talks.org