UniversidaddeCádiz

El discente sabrá determinar cuando una función es computable en sentido parcial o total mediante la construcción de una instancia de algún modelo de cálculo que así lo demuestre. Igualmente determinará la computabilidad de predicados.

El discente será capaz de definir nuevas funciones computables mediante aplicación de las técnicas de composición y recursión primitiva (simple y generalizada). Igualmente conocerá la jerarquía de funciones computables, y será capaz de determinar si una función es recursiva primitiva, una clase de funciones es PRC, y de construir predicados recursivos primitivos aplicando operaciones iteradas y cuantificación acotada.

El discente sabrá codificar pares de números mediante la función de emparejamiento y la numeración de Gdel, y conocerá la interpretación de los Teoremas de las Formas Normales y su consecuencias.

El discente conocerá algunos resultados notables de interés como el problema de la parada o el Teorema de Universalidad, y sabrá determinar cuándo conjuntos básicos son recursivos enumerables y recursivos.

El discente conocerá diferentes versiones de la máquina de Turing como modelo de computación estándar, y conocerá otros modelos de computación alternativos.

Exposición de los contenidos de la materia con ayuda ocasional de diapositivas, junto con la propuesta de ejemplos de afianzamiento desarrollados en aula, bajo un esquema constructivo incremental teorema-demostración. Se emplearán simuladores de apoyo de algunos de los modelos de computación estudiados en el curso: Davis, URM, Loop, While, Máquinas de Turing.

Las clases de problemas se dedicarán a desarrollar las soluciones a un subconjunto de ejercicios propuestos en las relaciones de problemas de la asignatura, que ampliarán en profundidad y complejidad a los ejemplos desarrollados en las clases teóricas. Metodológicamente, los alumnos se organizarán en grupos de trabajo.

El discente desarrollará las prácticas de la asignatura bajo dos vertientes de trabajo posibles, que no son mutuamente excluyentes entre sí:

a) Utilizará simuladores de diversos modelos de computación para verificar la computabilidad de distintas funciones y predicados bajo cada uno de los modelos.

b) Desarrollará, utilizando algún lenguaje de programación, programas que utilice algún modelo de computación aplicado a diferentes ámbitos del conocimiento.

La metodología será de resolución de casos y trabajo individual.

a) Lectura cuidadosa y razonada de las referencias bibliográficas y textos que sobre la materia indiquen los docentes.

b) Resolución de los ejercicios y/o problemas de afianzamiento de contenidos propuestos por docentes, y de las prácticas de la asignatura. 

c) Estudio intenso y continuado con aplicación e interés.

Tema 1: Modelos de Funciones Computables.
Preliminares matemáticos. Concepto de Modelo. Modelos de Computación vs. lenguajes de programación. En qué se parecen y en qué se diferencian, y por qué son necesarios. El modelo de Davis: memoria, instrucciones e instancias. Estados, espacio de estados, y configuraciones. Trayectorias en el espacio de estados: computaciones. Funciones computables en sentido parcial y total. Ejemplos de funciones computables. Haciendo la vida más fácil: macros y su expansión. Predicados computables. El modelo URM de Sheperdson y Sturgis: análisis y definición de computabilidad. El modelo Loop de Meyer y Ritchie: análisis y definición de computabilidad. Alcance de los modelos estudiados y relaciones entre modelos: reducciones; cuándo y cómo.

Tema 2: Aproximaciones Funcionales a la Computabilidad.
El lambda-cálculo de Church. La jerarquía de funciones: operadores de combinación de funciones computables: composición y recursión primitiva simple y generalizada. Teoremas de composición y recursión. Ejemplos. La teoría de funciones recursivas de Kleene: funciones iniciales y clases PRC. Computabilidad de las funciones iniciales. La clase PRC más simple: funciones recursivas primitivas. Un teorema de caracterización. Ejemplos de funciones recursivas primitivas. ¿Es posible expresar la computabilidad únicamente en base a la recursividad primitiva? Por qué no es posible: la jerarquía de Grzegorczyk y la función de Ackermann. Límites de los operadores de combinación y necesidad de uno nuevo: operaciones iteradas, cuantificadores acotados y funciones de minimización acotada y no acotada. Cómo la minimización no acotada produce fácilmente funciones computables en sentido parcial. Por qué en Informática todo cálculo se reduce a reescritura: Teoremas de las Formas Normales. Técnicas de codificación: función de emparejamiento y numeración de Gödel.

Tema 3: Universalidad
Codificación numérica en el modelo de Davis. Razonar sobre instancias del modelo de Davis y sobre números es lo mismo. Problemas de decisión; propiedades. Límites de la computabilidad: el problema de la parada y resultados similares. Por qué los computadores son programables: definición de las funciones universales y prueba del Teorema de Universalidad. Predicados contadores de pasos. Computabilidad en conjuntos: conjuntos recursivos enumerables y recursivos. Relaciones. Un teorema de caracterización. ¿Existen conjuntos recursivos enumerables pero no recursivos? Teorema de Enumeración. Otros resultados de interés: teoremas s-m-n, de recursion y de Rice; quines y autorreplicación. Aplicaciones del Teorema de Rice.

PROGRAMA DE PRÁCTICAS DE LA ASIGNATURA: computabilidad en autómatas celulares 1D, implementación, medidas de orden, aplicación en cifrados de flujo; computabilidad en auctómatas celulares 2D, implementación, aplicación en dinámica de poblaciones, reacciones químicas oscilantes y dinámica tisular neoplásica; computabilidad con URM  (unlimited register machine), implementación; computabilidad con máquinas de Turing, implementación.