Introdução................................................................................................................................1
O nascimento da computação parcial
Capítulo 1 A Confusão de Pitágoras..............................................................................24
Cálculo de Números..............................................................................................................24
Do sentido numérico à contagem..............................................................................................24
Cálculo em Civilizações Antigas..............................................................................28
Pitágoras..............................................................................................................30
O Mundo Ideal de Platão..............................................................................................40
Crise Matemática..............................................................................................................44
A descoberta dos números irracionais..............................................................................................44
O Paradoxo de Zenão: O Argumento do Infinito.............................................................................46
Raciocínio Dedutivo: Lógica e Geometria..............................................................................51
A Lógica de Aristóteles..............................................................................................51
Elementos de Euclides ..............................................................................................55
Paradoxo: O Lado Obscuro do Raciocínio..............................................................................59
Capítulo 2 A Arte do Cálculo..............................................................................................62
Álgebra: Computação com Caracteres..............................................................................62
Símbolos e Álgebra..............................................................................................................63
O Nascimento do Zero..............................................................................................................63
Álgebra Verbal..............................................................................................................65
Representação de grandezas desconhecidas..............................................................68
Restauração e Cancelamento..............................................................................................70
Símbolos Algébricos..............................................................................................................73
Resolução de equações polinomiais..............................................................................................77
De Soluções Numéricas para Algébricas..............................................................77
Fórmula para encontrar raízes de equações cúbicas..............................................................81
Irredutível: A descoberta dos números complexos..........................................................................84
Expansão dos sistemas numéricos..............................................................................................89
Teorema Fundamental da Álgebra..............................................................................................92
Estrutura Algébrica..............................................................................................................94
Resolução da equação quíntica..............................................................................94
Estrutura das Raízes das Equações..............................................................................95
A Pérola Perdida de Galois...................................................................................101
Ferramentas de Cálculo..............................................................................................................108
Agentes de Computação Humana..............................................................................109
Pensamento Computacional para Máquinas..............................................................................111
Capítulo 3 O Sonho de Cálculo de Leibniz..............................................................................116
A Criação da Lógica Matemática..............................................................................................117
O Alfabeto do Pensamento Humano..............................................................................................120
A Grande Evolução do Pensamento..............................................................................................121
O Sonho da Computação..............................................................................................................125
Pesquisa sobre as Leis do Pensamento..............................................................................................127
O Renascimento da Lógica Matemática no Século XIX.............................................................127
Álgebra Lógica Booleana..............................................................................................129
Parte II Bases Matemáticas da Computação
Capítulo 4 Fundamentos da Matemática..............................................................................................136
A Segunda Crise Matemática..............................................................................................................136
A invenção do cálculo..............................................................................................136
Fantasmas Desaparecidos: O Paradoxo de Berkeley..............................................................139
Análise rigorosa..............................................................................................................140
O Nascimento da Teoria dos Conjuntos..............................................................................................142
Qual é o tamanho do infinito?................................................................................................142
Método Diagonal..............................................................................................................146
Números Transfinitos de Cantor..............................................................................................148
Números cardinais transfinitos e ordinais transfinitos..............................................................148
Hipótese do Contínuo.................................................................................................152
A logicização da aritmética..............................................................................................156
“Palavras conceituais” de Frege ..............................................................................156
Definição de Números Naturais..............................................................................................159
Capítulo 5 A Terceira Crise Matemática..............................................................................................163
Crise: O Paradoxo de Russell..............................................................................................163
Paradoxo da Teoria dos Conjuntos..............................................................................................163
Auto-referência.............................................................................................................165
Solução para o Paradoxo..............................................................................................168
Abordagem Lógica..............................................................................................................169
Abordagem Intuicionista..............................................................................................173
Abordagem da Teoria dos Conjuntos Axiomáticos..............................................................................176
Teoria dos Conjuntos de Axiomas ZFC..............................................................................................177
Axioma da Escolha..............................................................................................................180
NBG Teoria dos Conjuntos Axiomáticos..............................................................................182
Parte III: A Formação de uma Teoria da Computação
Capítulo 6 Os fundamentos da teoria computacional: a abordagem de Hilbert.................................................186
A Matemática Não Coroada..............................................................................................186
Problema de Hilbert..............................................................................................................188
A questão matemática do século..............................................................................188
10º Problema de Hilbert..............................................................................................189
Fundamentos Aritméticos da Geometria..............................................................................................192
Quinto Postulado de Euclides..............................................................................................192
Abordagem de Modelagem..............................................................................................................194
Mesas, cadeiras e canecas de cerveja: pensamento sistémico formal..............................................195
O Pai do “Formalismo”...................................................................................196
Teoria da Prova Finita..............................................................................................198
Programa Hilbert..............................................................................................................201
O Problema da Decidibilidade..............................................................................................201
O Fim de...................................................................................................202
Capítulo 7 O que a computação não pode fazer: Terminator Gödel ..............................................................204
O mundo de ontem..............................................................................................................................204
Devemos saber, saberemos.................................................................204
Grande Amizade......................................................................................................205
A descoberta de Gödel..............................................................................................207
Ideias de codificação: Números de Gödel..............................................................209
Prova de Gödel.................................................................................................213
Teorema da Incompletude..............................................................................213
Teorema de Tarski................................................................................................215
O colapso do plano de Hilbert.............................................................................216
Programa de Gödel...................................................................................217
Desde Aristóteles..............................................................................................................218
Capítulo 8 O Nascimento da Teoria Computacional: Os Números Computáveis de Turing ..................................221
Acadêmicos de Turing..............................................................................................221
Máquina de Turing..............................................................................................................223
Simulando Computadores Humanos..............................................................................223
Modelo de Máquina de Turing..............................................................................................224
Números computáveis..............................................................................................226
A Tese de Church-Turing..............................................................................................................229
Prova do Problema Determinístico..............................................................................231
Prova de Turing..............................................................................................................231
Problema de parada..............................................................................................234
Castores Ocupados..............................................................................................................................235
Função de Crescimento Rápido..............................................................................235
Funções Incomputáveis..............................................................................238
O destino de Turing..............................................................................................................239
Parte IV Cálculo de Limites
Capítulo 9 Complexidade Computacional..............................................................242
Problemas Computacionais Difíceis..............................................................................243
Problema do Caixeiro Viajante..............................................................................................243
Tempo Polinomial e Tempo Exponencial..............................................................................245
Problema P/NP..............................................................................................................................249
Problemas NP..............................................................................................................249
Problemas NP..............................................................................................................251
Complexidade de Kolmogorov..............................................................................................254
Teorema de Cook-Levin..............................................................................................................255
O Princípio da Localidade da Computação..............................................257
P=NP?..................................................................................................................257
Um mundo onde P=NP.............................................................................................................258
Os limites da cognição..............................................................................................259
Alguns corolários de P≠NP..............................................................................................260
Entre dois mundos..............................................................................................................266
Perguntas não categorizadas..............................................................................................266
Problemas de fatoração..............................................................................................267
Problema de isomorfismo de grafos..............................................................................268
Cálculos aproximados..............................................................................................................268
Programação Linear de Danziger.........................................................270
Desafiando o Problema do Caixeiro Viajante..............................................................272
Teorema PCP e Inaproximabilidade..............................................................................281
Computação Paralela..............................................................................................................284
Equilíbrio Espaço-Temporal Computacional..............................................................284
Os limites da computação paralela..............................................................................285
Desafiando os Limites..............................................................................................................287
Capítulo 10 Computação Quântica..............................................................................................293
A computação é matemática e física.................................................................................293
O Iluminismo da Computação Quântica..............................................................................293
Propriedades Quânticas..............................................................................................................295
Calculando Energia Pequena..............................................................................................296
Bits quânticos..............................................................................................................................298
Do Bit Clássico ao Bit Quântico..............................................................................................298
Vantagem Quântica..............................................................................................................300
Portões Quânticos e Circuitos Quânticos..............................................................................300
Algoritmos Quânticos..............................................................................................................303
Do BPP ao BQP ..............................................................................................................303
Algoritmo de Shor..............................................................................................................305
Supremacia Quântica..............................................................................................................307
Realização de Computadores Quânticos..............................................................307
Ansiosos pela Supremacia Quântica..............................................................308
Capítulo 11 Computação Complexa..............................................................................310
O que é Complexidade..............................................................................................................310
Feedback e Controle..............................................................................................................312
Tendências modernas em pesquisa de complexidade..............................................................318
Complexidade de Algoritmos Simples..............................................................................318
Jogo da Vida..............................................................................................................321
Emergência..............................................................................................................................323
Estruturas Dissipativas..............................................................................................324
Ciência de Redes..............................................................................................................326
Computação Evolutiva..............................................................................................................330
Processamento de Informação em Sistemas Biológicos.......................................................330
Profundidade lógica..............................................................................................................334
Computação Evolutiva na Empresa..............................................................................335
Capítulo 12 As máquinas podem pensar?..............................................................................338
Simulando a estrutura do cérebro..............................................................................................338
O Grande Debate sobre Inteligência de Máquina..............................................................................340
O Jogo da Imitação e o Quarto Chinês..............................................................340
Simbolismo e Conexionismo.......................................................................344
AlphaGo e Lee Sedol..............................................................................................350
ChatGPT e Crows..............................................................................................................355
O Santo Graal da Inteligência Artificial..............................................................................355
O Princípio do ChatGPT..............................................................................................356
Mais de 350 anos de espera..............................................................................362
O Corvo Esperto..............................................................................................................365
Direções futuras..............................................................................................................366
Consciência da Máquina..............................................................................................................374
Capítulo 13 Princípios de Cálculo da Filosofia Natural.............................................................379
Limites de Cálculo..............................................................................................................379
Os grilhões do tempo e do espaço..............................................................................................................379
O Universo é um Computador?...................................................................................380
Limites de Turing..............................................................................................384
Além da Fronteira..............................................................................................................386
Cálculo do Tempo Infinito..............................................................................386
Computação no Espaço Infinito..............................................................................387
Uma visão de mundo computacionalista..............................................................................392
Posfácio..............................................................................................................................................397
Apêndice A Esboço da evolução dos paradigmas da pesquisa científica.........................................................399
Apêndice B A Arte de Questionar e Resolver.............................................................................404
Apêndice C De que tipo de sistema inteligente o mundo precisa?
Apêndice D Manifesto para Inteligência de Máquina.............................................................................423
Referências..............................................................................................................................425
......