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

De Cuba-Wiki
La versión para imprimir ya no se admite y puede contener errores de representación. Actualiza los marcadores del navegador y utiliza en su lugar la función de impresión predeterminada del navegador.

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é?

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_del_11/12/14_(Lógica_y_Computabilidad)&oldid=9578»