|
|
|
|
|
CÓDIGO
NOME CARGA HORÁRIA SEMANAL
N.º DE CARGA HORÁRIA
TEÓRICA PRÁTICA
CREDITOS GLOBAL
|
|
Teoria
da Recursão |
5 |
0 |
05 |
75 |
PRÉ – REQUISITOS
|
Informática Teórica |
EMENTA
|
q Recursividade e computabilidade; sistemas de equacoes; sistemas formais da aritmetica; maquinas de Turing; Tese de Church; funcoes recursivas parciais; funcionais; indices; o problema de Post; hierarquias e redutibilidades fracas; graus de Turing. |
CONTEÚDO PROGRAMÁTICO
|
q
Recursividade
e Computabilidade q
Inducao q
Sistemas
de equacoes q
Sistemas
formais para a aritmetica. q
Maquinas
de Turing q
Funcoes
como regras q
Aritmetizacao q
Tese
de Church q
Funcoes
recursivas partial q
Diagonalizacao q
Funcionais
recursivos parciais q
Operacoes
efetivas q
Indices
e enumeracoes q
Conjuntos
regressivos q
problema
de Post q
Conjuntos
simple e graus muitos-para-um q
Conjuntos
hipersimples q
Conjuntos
criativos e completude q
Tipos
de isomorfismo recursivos q
Variacoes
redutibilidade tabela-verdade q
mundo
dos conjuntos completos q
Sistemas
formais e conjuntos r.e. q
Hierarquias
e redutibilidades fracas q
A
hierarquia aritmetica q
A
hierarquia analitica q
A
hierarquia teorica de conjuntos q
A
hierarquia construtivel q
Graus
de Turing q
metodo
da extensao finita q
A
categoria de Baire q
metodo
da extensao co-infinita q
metodo
da arvore q
Segmentos
iniciais q
Graus
muitos-para-um q
Distributividade q
Comparacao de teorias de grau |
BIBLIOGRAFIA BÁSICA
|
q
P.
Oddifredi , Classical Recursion Theory, North-Holland, 1989. |
 |