math is hard, let’s go shopping!

Leituras sobre Teoria da Computação, Parte 1

· by Andrei Formiga · Read in about 7 min · (1473 Words)
teoria da computação livros

Ensinar teoria da computação às vezes é difícil pelo grau de rigor matemático e o nível de abstração necessários, mas o assunto em si é fascinante. As características essenciais dos processos computacionais são uma parte inerente da realidade, independente de tecnologias específicas. Daqui a mil anos os computadores atuais serão curiosidades na história da tecnologia, mas quem lidar com computação provavelmente ainda estará falando sobre decidibilidade e classes de complexidade.

Apesar das dificuldades, de vez em quando alguns alunos se interessam pelo assunto além do que vemos em sala de aula. Talvez pela teoria ser universal e atemporal, talvez pela beleza matemática envolvida, ou talvez pelo valor prático de estudar sobre complexidade ou linguagens formais. De qualquer forma, existe um bom número de livros e outros materiais que podem servir para quem quer explorar um pouco mais do terreno da teoria, e cheguei à conclusão que seria melhor juntar todas as indicações e escrever sobre isso.

As indicações estão divididas em duas (ou talvez mais) partes. Neste post eu indico materiais sobre teoria da computação para um público geral; indicações sobre materiais mais técnicos sobre o assunto serão tópico de um post futuro.

Os livros (e a história em quadrinhos) mostrados aqui são escritos para um público geral, que não necessariamente tem formação matemática ou exposição anterior à teoria da computação. Em geral, são mais sobre a história do tópico ou outros aspectos relacionados, com poucos detalhes sobre a teoria em si. Mesmo para quem quer aprender sobre os detalhes teóricos, entender o contexto em que a teoria foi estabelecida e as motivações das pessoas envolvidas dá uma visão mais ampla do tópico. Além disso, esses livros tendem a ser de leitura mais fácil e rápida que os livros teóricos.

Logicomix

Este quadrinho não é propriamente sobre teoria da computação, mas uma história do início da lógica matemática entre os Séculos XIX e XX, contada do ponto de vista de Bertrand Russell. Mas os fundadores do que hoje é chamado de teoria da computação eram matemáticos e lógicos, então as coisas acabam se relacionando. Não por acaso, um dos autores do quadrinho (Papadimitriou) é um importante autor na área da teoria da computação. Além disso, um dos grandes objetivos de Russell na lógica, o Principia Mathematica (escrito juntamente com Whitehead) tem muito a ver com a ideia da mecanização da matemática usando computadores que hoje é um projeto de parte da comunidade de pesquisa em teoria da computação.

Independente das conexões com a teoria da computação, é uma ótima leitura para quem tem qualquer interesse nessa parte da história da matemática e do pensamento humano. Muitos dos personagens principais dessa época aparecem, de Wittgenstein a Gödel.

Existe uma versão brasileira do quadrinho, editado aqui pela Martins Fontes.

Engines of Logic

Este livro de Martin Davis conta a história do desenvolvimento das ideias por trás da computação teórica, desde o sonho de Leibniz de criar uma linguagem composta por símbolos que representam conceitos e uma álgebra capaz de manipular tais símbolos de forma a automatizar o raciocínio, até as contribuições teóricas e práticas de Alan Turing. O livro é bem escrito e muito bem pesquisado, apresentando os temas envolvidos com leveza mas sem leviandade.

Infelizmente não tem edição brasileira, mas para quem lê em inglês é possível achar cópias usadas por um preço baixo na Amazon. Para quem for procurar cópias usadas, é bom saber que a versão em capa dura do mesmo livro tem um título diferente: “The Universal Computer: The Road from Leibniz to Turing”.

O Advento do Algoritmo

Escrito por David Berlinski, este livro cobre mais ou menos o mesmo terreno que o livro de Davis, “Engines of Logic”, com algumas diferenças. Provavelmente para se diferenciar do livro de Davis, Berlinski decidiu misturar capítulos expositivos com capítulos mais puxados para a ficção, com os personagens-chave da história (como Leibniz) contando alguns episódios em primeira pessoa. Na minha opinião isso não funcionou muito bem e, no geral, este livro é inferior ao “Engines of Logic”. A única vantagem de “O Advento do Algoritmo” é que ele foi editado no Brasil há alguns anos, então é uma alternativa para quem só lê em português. Pelo que pode se ver nas livrarias virtuais, o livro está esgotado na editora, mas deve ser possível encontra-lo em sebos.

Alan Turing: The Enigma

Alan Turing foi um dos personagens-chave no desenvolvimento da computação, tanto na teoria quanto na prática, além de ser um pensador original e de grande amplitude; além disso, a história da sua vida é complexa, interessante e mesmo controversa. Esta biografia de autoria de Alan Hodges é geralmente considerada o melhor registro sobre a vida de Turing, e um caso exemplar de biografia bem feita de um grande cientista. Extremamente bem pesquisada e sem se prender a ser apenas uma apologia de uma mente brilhante, minuciosa e detalhada sem ser maçante, o livro de Hodges é de leitura recomendada mesmo para quem não é da área da computação.

Mais uma vez, este é um livro sem edição brasileira. Até recentemente o livro estava fora de catálogo nos EUA também, mas como 2012 foi o ano do centenário de Turing, saiu uma nova edição em comemoração ao centenário, incluindo versões em ebook.

O Homem que Sabia Demais

Esta é uma outra biografia de Turing, escrita por David Leavitt. Serve como introdução à vida de Turing, até por ser um livro curto, e para alguns leitores pode ser o suficiente. Existe uma versão brasileira do livro, que é o maior motivo para ele aparecer nesta lista, já que como biografia ele é inferior ao livro de Hodges. Inclusive a biografia escrita por Hodges foi claramente a fonte primária para o livro de Leavitt, que a cita frequentemente ao longo do texto. Sendo mais direto, o livro de Leavitt parece um resumo de “Alan Turing: The Enigma”. Enquanto o livro de Hodges não estava disponível, ou para quem não consegue ler textos em inglês, esta biografia pode servir como substituto, mas quem tiver condições deve preferir o original ao resumo.

Gödel, Escher, Bach

Um clássico escrito por Douglas Hofstadter, “Gödel, Escher, Bach” não é exatamente sobre teoria da computação, mas passa por vários tópicos relacionados. Boa parte do livro serve como um tutorial não-convencional sobre lógica matemática, no meio das considerações sobre o papel da recursividade nas artes visuais, na música e na matemática. É um livro longo, cheio de ideias e de desvios interessantes, mas que eventualmente revela seu fio principal: apresentar os teoremas de incompletude de Gödel (daí o tutorial sobre lógica) e as ideias do autor sobre inteligência artificial e a consciência humana. Mais especificamente, uma das ideias principais é que os teoremas da incompletude de Gödel não inviabilizam a possibilidade de uma inteligência artificial “real” com características da inteligência humana. No meio da discussão sobre inteligência surge também um dos artigos famosos de Alan Turing, “Computing Machinery and Intelligence”, pelo qual ele é considerado como um dos pais da IA. Ao todo, um livro interessantíssimo e cheio de “caminhos que se bifurcam”, mesmo que não seja especificamente sobre computação.

Houve uma boa edição brasileira há alguns anos, que atualmente parece estar esgotada, mas deve ser possível de encontrar em sebos. As várias edições em inglês são bastante fáceis de encontrar para vender.

Incompletude

Assim como o anterior, este livro está na lista mais como bônus. Kurt Gödel foi um dos matemáticos mais geniais do Século XX, e sua vida pessoal também foi atribulada. Os teoremas de incompletude chocaram a comunidade matemática quando foram divulgados, acabando com o projeto formalista de David Hilbert; Gödel não tinha mais que 23 anos quando formulou e provou os teoremas. A incompletude foi fundamental nos questionamentos que levaram ao desenvolvimento da teoria da computação, e serviu como inspiração para a prova da indecidibilidade do problema da parada, descoberta por Turing. Não é à toa que praticamente todos os livros desta lista mencionam Gödel em algum momento.

“Incompletude” é um livro curto, que se divide entre traçar um esboço biográfico de Gödel e apresentar as ideias principais dos famosos teoremas que ele provou, assim como as correntes filosóficas por trás das ideias de Gödel e do Círculo de Viena, um grupo de lógicos matemáticos do qual ele fazia parte. No geral deixa a desejar em alguns pontos, mas é de leitura interessante principalmente para quem tem algum interesse em filosofia, já que a autora tem formação em filosofia e parece estar mais interessada nas questões filosóficas envolvidas na vida e trabalho de Gödel. Além disso, é um dos poucos livros sobre Gödel que possuem edição brasileira, que ainda pode ser encontrada para vender. Sobre os teoremas da incompletude e as provas de Gödel existem fontes melhores, entre elas “Gödel, Escher, Bach” e o famoso “Gödel’s Proof” de Nagel e Newman, que será um dos livros indicados na próxima parte.

Comments