| ICP370-Lógica e Computabilidade | Linguagens e sintaxe da Lógica de Primeira Ordem (LPO). Formalização e modelagem de problemas usando LPO. Semântica da LPO. Sistemas de prova para a LPO. Noções da equivalência entre consequência semântica e sintática. Noções de provadores automáticos. O Problema da Decisão de Hilbert-Ackermann. Máquina de Turing. Programação em Máquinas de Turing. Máquina de Turing universal. Problema da Parada. Reduções entre problemas; problemas indecidíveis. Noções da equivalência entre Máquinas de Turing e outros modelos de computação.
___BIBLIOGRAFIA BÁSICA___
1) M. D. Davis, R. Sigal e E. J. Weyuker, Computability, complexity, and languages, segunda edição, Academic Press (1994).
___BIBLIOGRAFIA COMPLEMENTAR___
1) Boolos, G. S., Burgess,J. P. , Jeffrey, R. C., Computabilidade e Lógica. Editora Unesp, 2012.
2) Carnielli, W., Epstein,R. L., Computabilidade, funções computáveis, lógica e os fundamentos da matemática. Editora Unesp, 2005. |
|
|