Este livro destina-se às disciplinas de nível universitário que foquem a computação e/ou a complexidade. Primeiro estuda-se a própria computação, na perspectiva das máquinas de registos e das funções recursivas. São duas visões complementares da computação, com princípios muito diferentes mas desenvolvidos, neste livro, até convergirem nas suas conclusões. Estudam-se os limites teóricos da computação, ilustrando alguns problemas que não têm resolução algorítmica, bem como os limites práticos da computação através da teoria da complexidade, uma ferramenta essencial para programadores e engenheiros informáticos na análise de desempenho das suas soluções informáticas. Por fi m, num extenso anexo e de forma a autoconter esta ora dentro do razoável e possível, são apresentados os conceitos matemáticos necessários ao rigor do restante texto.