Plano departamental

1-Linguagens e Máquinas de Turing
Máquina de Turing padrão. Reconhecimento de linguagens com a máquina de Turing. Variações da máquina de Turing: com múltiplas trilhas, com duas vias, com múltiplas vias, não deterministas. Enumeração de linguagens com a máquina de Turing.
2-A hierarquia de Chomsky
Gramáticas irrestritas e linguagens recursivamente enumeráveis. Gramáticas sensíveis ao contexto. Autômatos linearmente limitados. A hierarquia de Chomsky.
3-Decidabilidade e computabilidade
Problemas de decisão. A tese de Church-Turing. O Problema da Parada para máquinas de Turing. A máquina de Turing Universal. Redutibilidade, o teorema de Rice. Problemas insolucionáveis: sistemas semi-Thue, pós-correspondência. Problemas indecidíveis em gramáticas livres de contexto.
4-Computação com máquinas de Turing
Cálculo de funções. Computação número-teórica e indexação. Operação seqüencial de máquinas de Turing: macros. Composição de funções. Funções não computáveis.
5-Equivalência de programas
Programas e máquinas. Computação e função computada. Verificação da equivalência forte de programas.

DIVÉRIO, T. A. Teoria da computação - máquinas universais e computabilidade. Porto Alegre: Bookman. 2011. 3a ed. 288p. (Livros didáticos informática UFRGS)
HOPCROFT, J. E. Introdução a teoria de autômatos, linguagens e computação. Rio de Janeiro: Elsevier. 560 p
SIPSER, M. Introdução à teoria da computação: Thomson Learning. 2007. 488 p.

Não informado

CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos - teoria e prática. Rio de Janeiro: Campus. 2012. 944 p.
GURARI, E. An Introduction to the Theory of Computation. Computer Science Press. 1989
LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de teoria da computação. Porto Alegre: Bookman. 2008. 2a ed. 344 p.
modelagem e implementação. Porto Alegre: Bookman. 2009. 656 p.
RAMOS, M. V. M.; NETO, J. J.; VEGA, Í. S. Linguagens formais: Teoria,
ROSA, J. L. G. Linguagens Formais e Autômatos. Rio de Janeiro: LTC Editora. 2010.