Histórico e contextualização da Computação. Máquinas de Turing. Formalização do conceito de algoritmo. Problema da Parada. A Tese de Church-Turing. Indecidibilidade. Noções de Redutibilidade. Algoritmo/Máquina de Post. Algoritmo/Máquina de Markov. Máquina de Registradores. Lambda Calculus. Teoria das funções recursivas. Relações entre os modelos de computabilidade e suas equivalências.