Final del 16/07/13 (Lógica y Computabilidad)

Ejercicio 1

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

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

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

Demostrar que halt(x,y) no es computable