Final del 16/07/13 (Lógica y Computabilidad)
De Cuba-Wiki
Ejercicio 1[editar]
a) Dar el concepto de subfórmula. b) Si B es subfórmula de A, demostrar que pertenece a toda cadena de formación de A.
Ejercicio 2[editar]
Dar la noción de interpretación de un lenguaje. Mostrar que todo lenguaje puede tener una interpretación con universo en los Naturales
Ejercicio 3[editar]
a) Mostrar que la clase de funciones computables es cerrada por recursión y composición. b) a partir de esto mostrar que las primitivas recursivas son computables.
Ejercicio 4[editar]
Demostrar que halt(x,y) no es computable