Fundamentos Teóricos da Computação

Linguagens e M´aquinas:
Uma Introdu¸c˜ao aos Fundamentos da Computa¸c˜ao
Newton Jos´e Vieira
Departamento de Ciˆencia da Computa¸c˜ao
Instituto de Ciˆencias Exatas
Universidade Federal de Minas Gerais
Belo Horizonte, 04/05/2004

Pref´ acio For me, the first challenge for computing science is to discover how to maintain order in a finite, but very large, discrete universe that is intricately intertwined. And a second, but not less important challenge is how to mould what you have achieved in solving the first problem, into a teachable discipline: it does not suffice to hone your own intellect (that will join you in your grave), you must teach others how to hone theirs. The more you concentrate on these two challenges, the clearer you will see that they are only two sides of the same coin: teaching yourself is discovering what is teachable.
E.W. Dijkstra.

Este livro foi escrito para ser utilizado principalmente por alunos de cursos de gradua¸c˜ao na ´area de Computa¸c˜ao, como Ciˆencia da Computa¸c˜ao, Matem´atica Computacional, Engenharia de Computa¸c˜ao, Sistemas de Informa¸c˜ao, e outros. Ele pode tamb´em ser utilizado por alunos de p´os-gradua¸c˜ao, eventualmente complementado com outras referˆencias que abordem alguns assuntos com maior profundidade ou que apresentem alguns t´opicos n˜ao cobertos aqui. Al´em disso, ele pode ser u
´til para profissionais da ´area de Computa¸c˜ao em geral, tanto para aqueles que desejem fazer uma revis˜ao, quanto para aqueles que queiram ter um primeiro contato com a ´area.
Os textos que abordam os assuntos aqui apresentados podem ser divididos em trˆes grupos. H´a aqueles com uma abordagem bastante abstrata e formal, orientados para leitores com uma base matem´atica forte. Alguns deles se preocupam em apontar ou desenvolver algumas aplica¸c˜oes, mas o foco ´e a explora¸c˜ao das estruturas matem´aticas em si. Em um segundo grupo, h´a aqueles com uma abordagem menos abstrata, com uma preocupa¸c˜ao em