"Models Abstractes de Càlcul", D. Riaño, 182 pp., ISBN 84-8424-006-1, 2000.
david.riano@urv.net

Contingut
Prefaci
1 Introducció
1.1 Teoria de conjunts
1.2 Teoria de funcions matemàtiques
1.3 Teoria de llenguatges
1.3.1 Llenguatges regulars
1.3.2 Llenguatges incontextuals
1.3.3 Llenguatges contextuals
1.4 Teoria de la lògica matemàtica
1.5 Algorísmica
Exercicis
2 Màquina de Turing
2.1 Descripció i representació de la màquina de Turing
2.1.1 Representació formal
2.1.2 Representació tabular
2.1.3 Representació gràfica
2.1.4 Representació estructural
2.1.5 Representació algorísmica
2.2 Màquina de Turing per reconèixer llenguatges
2.3 Màquina de Turing per computar funcions
2.4 Cicle d'avaluació
2.5 Màquina de Turing determinista (MTD)
2.5.1 Reconeixement de llenguatges
2.5.2 Computació d'una funció
2.6 Màquina de Turing indeterminista (MTI)
2.6.1 Reconeixement de llenguatges
2.6.2 Computació d'una funció
2.7 Extensions de la màquina de Turing
2.7.1 Variacions
2.7.2 Combinació
2.8 La màquina de Turing universal
2.9 Altres models de computació
2.9.1 l-càlcul
2.9.2 Funcions recursives
2.9.3 Algorismes de Markov
2.9.4 Sistemes de Post
2.9.5 Màquines de registres
Exercicis
3 Calculabilitat
3.1 Limitacions de les màquines de Turing
3.1.1 Punt de vista de la teoria de conjunts
3.1.2 Punt de vista de la teoria de funcions matemàtiques
3.1.3 Punt de vista de la teoria de llenguatges formals
3.1.4 Punt de vista de la lògica matemàtica
3.1.5 Punt de vista de la teoria d'algorismes
3.1.6 Equivalència de terminologies
3.2 Calculabilitat
3.3 Teoria de la calculabilitat
3.3.1 Classificació dels conjunts
3.3.2 Jerarquia aritmètica o jerarquia de Kleene-Mostowski
Exercicis
4 Complexitat
4.1 Complexitat computacional
4.2 Classes de complexitat fonamentals
4.3 Les classes de complexitat L i NL
4.4 Les classes de complexitat P, NP i CoNP
4.5 Les classes de complexitat EXP i NEXP
4.6 Complexitat
4.7 Teoria de la complexitat
4.7.1 Classificació dels llenguatges
4.7.2 Oracles
4.7.3 Jerarquia polinòmica o jerarquia de Grzegorczyk
4.7.4 Jerarquia exponencial
Exercicis
Bibliografia
Índex