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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Gamma} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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é?