Primer Examen Parcial de Teoría de la Computación Primera parte: Resolver los siguientes problemas sobre computabilidad. I. Demostrar que las siguientes funciones son computables. 1. ������(������) =5, ������ ������ ℕ 2. ������(������) = 2������, ������ ������ ℤ 3. ������(������� , ������� , … , ������� ) = ������� + ������� + … + ������� , ������� ������ ℕ Opción A: Implementar las siguientesmacros 1. if x < y then task A else task B 2. while x < y do task A. Opción B: Dado el siguiente lenguaje mínimo: clear, incr, y repeat n times: task A, implementar las macros: assign (x,y), decr,while, repeat, if-then-else. III. Desarrollar máquinas de Turing (diagrama de estado, tabla de transiciones y ejemplos) para efectuar las siguientes tareas. 3. x := 0 4. x := y IV. Utilizar el modelo URMpara resolver los siguientes problemas 5. Opción A: Sequencia de Fibonacci Opción B: Demostrar que la instrucción T(m,n) es redundante. V. Demostrar que los siguientes predicados son decibles 6. “x esmenor que y.” 7. “x es divisible entre 3.” 8. “Si ������ � + ������ � = ������ � ; ������, ������, ������, ������ ������ ℕ; entonces n < 3.” (Ejemplos: n=1, 21 +31 = 51; n=2, 32 +42 = 52.) Segundaparte: Desarrollar una máquina virtual que simule alguno de los modelos estudiados en clase. Opción A: URM • • • La aplicación debe mostrar al usuario cada paso de la ejecución de un programa URM(instrucción actual y estado de los registros). Las condiciones iniciales y el programa fuente deben ser leídos desde un archivo de texto. El intérprete debe funcionar correctamente para los ejemplosmostrados en clase y permitir un mínimo de 15 registros.
II. Utilizar el lenguaje “simple” (incr, decr, y while) como modelo de computabilidad.
Opción B: CARDIAC • • • • El lenguaje debe serformalizado (demostrar que es un modelo válido para el estudio de las funciones computables). La aplicación debe mostrar al usuario cada paso de la ejecución de un programa CARDIAC (instrucción actual,...
Leer documento completo
Regístrate para leer el documento completo.