Parcial de Computabilidad Verano 2016 (LyC)

De Cuba-Wiki
Revisión del 01:29 15 feb 2016 de Ffrizzo (discusión | contribs.) (Página creada con «{{Back|Lógica y Computabilidad}} 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 cla...»)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

Plantilla:Back

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, apellido y número de orden. El examen consta de 4 ejercicios de igual valor. Cada ejercicio sera calificado con A (aprobado), R (regular) o I (insuficiente), ocasionalmente con un signo — (menos). Para aprobar un parcial es necesario tener al menos dos ejercicios calificados con A o A—. Para promocionar es necesario tener al menos tres ejercicios calificados con A o A- en ambos parciales o sus correspondientes recuperatorios.

Ejercicio 1

Sea la función que ordena una lista de números naturales de menor a mayor. Más explícitamente, y dado un numero natural , lo interpreta como una lista de números naturales sin ceros al final y devuelve la codificación de la lista que resulta de ordenar los elementos de la original de menor a mayor. Demostrar que la función es primitiva recursiva.

Ejercicio 2

Sea un número natural fijo. Demostrar que la siguiente función es parcial computable:

donde es la función del Ejercicio 1 y puede asumirse el resultado de ese ejercicio como válido.

Ejercicio 3

Decidir si las siguientes funciones son computables o no. Justificar la respuesta.

a.

b.

Ejercicio 4

Sea una función total, y . Decidir si son verdaderas o falsas las siguientes afirmaciones. Justificar la respuesta.

a. Si es c.e. entonces es computable.

b. Si es c.e. entonces es computable.