Final del 11/12/14 (Lógica y Computabilidad)
De Cuba-Wiki
Ejercicio 1
Enunciar el halting problem y demostrar que HALT(x, y) no es computable
Ejercicio 2
Enunciar y demostrar el teorema de Rice
Ejercicio 3
Definir consistente, maximal consistente y demostrar el Lema de Lindenbaum
Ejercicio 4
Dar un conjunto de formulas tal que es valida sii el modelo que la satisface es infinito. ¿Existe una formula tal que es valida sii el modelo que la satisface es finito? ¿Por qué?
