Final del 11/12/14 (Lógica y Computabilidad)

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 $\Gamma$ tal que $\Gamma$ es valida sii el modelo que la satisface es infinito. ¿Existe una formula $\varphi$ tal que $\varphi$ es valida sii el modelo que la satisface es finito? ¿Por qué?