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

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

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