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 resumen de edición |
||
| Línea 1: | Línea 1: | ||
{{Back|Lógica y Computabilidad}} | |||
=Ejercicio 1= | =Ejercicio 1= | ||
Revisión actual - 17:03 7 abr 2015
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
