Diferencia entre revisiones de «Recuperatorio de computabilidad Verano 2017 (LyC)»
(Página creada con «El examen es a libro abierto y se puede suponer demostrado lo dado en las clases y los ejercicios de las guías colocando referencias claras. Entregar cada ejercicio en hoj...») |
Sin resumen de edición |
||
Línea 3: | Línea 3: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
Decimos que un programa | Decimos que un programa {{math|P}} es ''simple'' si todos los saltos condicionales son hacia adelante (es decir, hacia una línea de programa posterior a la del salto en cuestión). | ||
'''a.''' Decida y demuestre si la siguiente función es primitiva recursiva: | '''a.''' Decida y demuestre si la siguiente función es primitiva recursiva: |
Revisión del 12:05 24 sep 2019
El examen es a libro abierto y se puede suponer demostrado lo dado en las clases y los ejercicios de las guías colocando referencias claras. Entregar cada ejercicio en hojas separadas. En cada hoja debe figurar nombre y apellido.
Ejercicio 1
Decimos que un programa Plantilla:Math es simple si todos los saltos condicionales son hacia adelante (es decir, hacia una línea de programa posterior a la del salto en cuestión).
a. Decida y demuestre si la siguiente función es primitiva recursiva:
b. Decida y demuestre si es computable la función con la función del ítem anterior.
Ejercicio 2
Sea una función total tal que dado , si es el menor número tal que y computa la función identidad, . Decida y demuestre si es computable o no.
Ejercicio 3
Para cada uno de los siguientes conjuntos, decida y demuestre si es c.e., co-c.e. y/o computable.
a.
b.
Ejercicio 4
Considere la clase de conjuntos definida como:
a. Decida y demuestre si los conjuntos son computables, c.e. y/o co-c.e.
b. Decida y demuestre si es computable, c.e. y/o co-c.e.