Edición de «Final del 11/12/14 (Lógica y Computabilidad)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
=Ejercicio 1= | =Ejercicio 1= | ||
Enunciar el halting problem y demostrar que HALT(x, y) no es computable | Enunciar el halting problem y demostrar que HALT(x, y) no es computable | ||
=Ejercicio 2= | =Ejercicio 2= | ||
Enunciar y demostrar el teorema de Rice | Enunciar y demostrar el teorema de Rice | ||
=Ejercicio 3= | =Ejercicio 3= | ||
Definir consistente, maximal consistente y demostrar el Lema de Lindenbaum | Definir consistente, maximal consistente y demostrar el Lema de Lindenbaum | ||
=Ejercicio 4= | =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. | 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 | ¿Existe una formula <math>\varphi</math> tal que <math>\varphi</math> es valida sii el modelo que la satisface es finito? ¿Por que ? |