Diferencia entre revisiones de «Final del 16/07/13 (Lógica y Computabilidad)»
De Cuba-Wiki
(Página creada con «=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 d...») |
(Sin diferencias)
|
Revisión del 15:00 12 sep 2014
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