Programa

Computabilidade e Complexidade da Aprendizagem

Diploma de Estudos Avançados em Segurança de Informação

Programa

Conceito de cientista segundo Gold. Identificação de linguagens e funções. Cientistas computáveis e não computáveis. Cientistas de memória limitada. Identificação por cientistas computáveis. Estratégias de identificação de linguagens e funções. Cientistas popperianos. Classes: Ex, Ex*, Bc, Bc*, TxtEx, TxtEx*, TxtFex and TxtFex*. Teoremas de Blum e Blum, de Case e Smith, de Adleman, e de Harrington. Identificação de linguagens e funções por equipas de cientistas determinísticos e probabilísticos. Identificação por cientistas que consultam oráculos. Teoremas de Adleman e Blum, de Jockusch, de Fortnow et al. Complexidade da identificação.