Diferencia entre revisiones de «Parcial de computabilidad Verano 2017 (LyC)»

De Cuba-Wiki
(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 36: Línea 36:
Ayuda: Piense cuáles son los elementos de <math>\mathcal{S}</math>.
Ayuda: Piense cuáles son los elementos de <math>\mathcal{S}</math>.


Aclaración: Para todo <math>y</math>, <math>\operatorname{STP}(y, x, 0) = 1</math> sii <math>x = 0</math>.
Aclaración: Para todo <math>y</math>, <math>\operatorname{STP}(y, x, 0) = 0</math>.


== Ejercicio 4 ==
== Ejercicio 4 ==

Revisión del 22:55 22 feb 2017

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.

Ejercicio 1

Sea la función que calcula el producto de Kronecker entre dos listas. Es decir, devuelve una lista de listas tal que . Por ejemplo:

Decida si es p. r. y justifique su respuesta.

Ejercicio 2

Diga si las siguientes afirmaciones son verdaderas o falsas. Justifique sus respuestas.

a. La siguiente función es computable:

Error al representar (función desconocida «\begin{cases}»): {\displaystyle f(x) = \begin{cases} 1 & \text{si existe $z$ tal que $\Phi^{(1)}_z (y) = \Phi^{(1)}_x(y) + 1$ para todo $y$} \\ 0 & \text{otro caso.} \end{cases} }

Aclaración: quiere decir que el programa con número se indefine cuando el programa con número se indefine, y que devuelve el siguiente de lo que devolvió el programa con número cuando este último termina.

b. Existe un programa tal que:

Ejercicio 3

a. Demuestre que si un programa de número termina con entrada entonces vale que , para todo tal que .

b. Decida si el siguiente conjunto es c.e., co-c.e. y/o computable:

Ayuda: Piense cuáles son los elementos de .

Aclaración: Para todo , .

Ejercicio 4

Decida si el siguiente conjunto es c.e., co-c.e. y/o computable: