Ver el código de «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 <math>\Gamma</math> tal que <math>\Gamma</math> es valida sii el modelo que la satisface es infinito. 
¿Existe una formula <math>\varphi</math> tal que <math>\varphi</math> es valida sii el modelo que la satisface es finito? ¿Por que ?