Parcial de Computabilidad Verano 2016 (LyC)

De Cuba-Wiki

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[editar]

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[editar]

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[editar]

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

a.

b.

Ejercicio 4[editar]

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.