Abrir menú principal

Cuba-Wiki β

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

Ejercicio 1Editar

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 2Editar

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 3Editar

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 4Editar

Demostrar que halt(x,y) no es computable