Diferencia entre revisiones de «Final del 11/12/14 (Lógica y Computabilidad)»

De Cuba-Wiki
Sin resumen de edición
mSin resumen de edición
 
(No se muestran 2 ediciones intermedias del mismo usuario)
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 que ?
¿Existe una formula <math>\varphi</math> tal que <math>\varphi</math> es valida sii el modelo que la satisface es finito? ¿Por qué?

Revisión actual - 12:51 12 dic 2014

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