Antonio J. Tomeu Hardasmal (coordinador)

La asignatura plantea el estudio de lo que se podrían denominar fundamentos de
la computación, en el sentido de que determinan por qué existen, por qué son
programables, y cuáles son los límites de las computadoras modernas. Los
conocimientos adquiridos por el alumno deberán permitirle:

1. Conocer el concepto de funciones parcial y totalmente computables. En
particular, ser capaz de escribir L-programas que calculen a funciones
propuestas concretas.
2. Saber aplicar los conceptos de configuración y configuración sucesora. En
particular, dado un L-programa y sus datos de entrada, ser capaz de calcular la
computación completa inducida por ellos.
3. Saber expandir macros a efectos de lograr L-programas básicos
4.  Conocer el concepto de predicado. Utilizarlos para diseñar sentencias de
bifurcación condicional.
5.  Saber obtener nuevas funciones computables mediante composición funcional
y recursión primitiva.
6. Conocer el concepto de clase PRC. Saber determinar si una clase de
funciones es o no PRC.
7. Saber demostrar si una función es o no recursiva primitiva.
8. Conocer y utilizar las operaciones iteradas y los cuantificadores acotados
para realizar demostraciones.
9. Saber aplicar la minimización no acotada para definir nuevas funciones.
10. Conocer los Teoremas de la Forma Normal y sus implicaciones
11. Conocer y saber aplicar las técnicas de codificación y decodificación
numérica descritas mediante las funciones de emparejamiento y de Gödel.
12. Saber codificar y decodificar L-programas.
13. Ser capaz de interpretar el problema de la parada como ejemplo de problema
no computable.
14. Conocer el concepto de problema indecidible, y determinar si un problema
lo es para casos sencillos.
15. Conocer el concepto de función universal. Determinar la computabilidad de
las funciones universales y su importancia como marco subyacente del concepto
de programabilidad.
16. Conocer el concepto de conjunto recursivo y recursivo enumerable. En
particular, y dado un conjunto, saber clasificarlo en una de las dos categorías
mediante una demostración
17. Conocer el concepto de máquina de Turing. Conocer el concepto de función
Turing-computable.
18. Saber escribir máquinas de Turing en sus versiones de cuadruplas, de
cuadruplas no deterministas y de quintuplas que calculen a funciones
computables.
19. Conocer la estructura y funcionamiento de una máquina universal de Turing.
20. Conocer el concepto de máquina URM. Ser capaz de probar la urm-
computilidad de funciones.
21. Conocer el concepto de autómata celular, su clases de  comportamiento y su
papel en la teoría de la Computabilidad.
22. Connocer el concepto de red de neuronal y los principios básicos de
utilización en problemas de pattern-matching.
23. Conocer la Tesis de Church-Turing, su interpretación, y el papel que juega
en el ámbito de la Teoría de la Computabilidad.

Programa Teórico

Tema 1 : Modelo de Funciones Computables. (4 horas)
1.1 Un modelo de programación.
1.1.1 Variables, etiquetas e instrucciones.
1.1.2 Construcción de programas.
1.2 Ejemplos de programas.
1.2.1 Programa para el cálculo de la función identidad.
1.2.2 Programa para el cálculo de la función suma.
1.2.3 Programa para el cálculo de la función resta.
1.2.4 Programas para calcular otras funciones.
1.3 Funciones parcial y totalmente computables.
1.3.1 Concepto de función parcialmente computable.
1.3.2 Concepto de función totalmente computable.
1.4 Predicados.
1.4.1 Predicados como funciones bivaluadas en el dominio {0,1}.
1.4.2 Computabilidad de predicados.
1.5 Macros.
1.5.1 Concepto de macro.
1.5.2 Renombrado de variables y etiquetas.
1.5.3 Utilización de macros.

Tema 2 : La Jerarquía de Funciones. (12 horas)
2.1 Composición de funciones.
2.1.1 Definición.
2.1.2 Teorema de composición.
2.1.3 Ejemplos.
2.2 Funciones definidas recursivamente.
2.2.1 Definición.
2.2.2 Teorema de recursión.
2.2.3 Ejemplos.
2.3 Funciones iniciales.
2.3.1 Definición de las funciones  .
2.3.2 Computabilidad de las funciones iniciales.
2.4 Clases PRC.
2.4.1 Definición de clase PRC.
2.4.2 Definición de funciones recursivas-primitivas.
2.4.3 Computabilidad de las funciones recursivas primitivas.
2.5 Algunas funciones recursivas primitivas.
2.5.1 Función suma.
2.5.2 Función producto.
2.5.3 Función factorial.
2.5.4 Función potencia.
2.5.5 Función predecesor.
2.5.6 Función resta restringida.
2.5.7 Función valor absoluto.
2.5.8 Función de negación.
2.6 Predicados recursivos primitivos.
2.6.1 Negación de predicados recursivos primitivos.
2.6.2 Disyunción de predicados recursivos primitivos.
2.6.3 Conjunción de predicados recursivos primitivos.
2.6.4 Teorema de definición por casos.
2.7 Operaciones Iteradas y cuantificadores acotados.
2.7.1 Definición de las operaciones iteradas.
2.7.2 Los predicados para todo y existe en versión acotada.
2.7.3 Ejemplos definidos en términos de los elementos anteriores.
2.8 Minimización.
2.8.1 Definición de la función mínimo acotado.
2.8.2 Ejemplos de funciones definidas sobre el mínimo acotado.
2.8.3 Minimización no acotada.
2.8.4 Teorema de la Forma Normal.
2.9 Funciones de apareamiento y números de Gödel.
2.9.1 Definición de la función de apareamiento.
2.9.2 Teorema de la función de apareamiento.
2.9.3 Definición de la función de codificación de Gödel.
2.9.4 Teorema de la secuencia de números.

Tema 3 : Universalidad. (6 horas)
3.1 Codificación de programas mediante números.
3.1.1 Codificación de etiquetas, variables e instrucciones.
3.1.2 Codificación de programas.
3.2 El problema de la parada.
3.2.1 Problemas no computables.
3.2.2 Problema de la parada.
3.2.3 Conjetura de Goldbach.
3.3 Teorema de Universalidad.
3.3.1 Funciones universales.
3.3.2 Teorema de Universalidad.
3.3.3 Teorema contador de pasos.
3.4 Conjuntos recursivamente enumerables.
3.4.1 Definición.
3.4.2 Operaciones de conjuntos sobre conjuntos r.e.
3.5 Conjuntos recursivos.
3.5.1 Definición.
3.5.2 Relación entre los conjuntos r.e. y los conjuntos recursivos.
3.5.3 Teorema de enumeración.
3.5.4 Existencia de conjuntos r.e. pero no recursivos.
3.6 Teorema del parámetro.
3.6.1 Proposición del teorema.
3.6.2 Utilidad práctica.
3.7 Teorema de recursión.
3.7.1 Proposición del teorema.
3.7.2 Utilidad práctica.
3.7.3 Consecuencias: el teorema del punto fijo.
3.8 Teorema de Rice.
3.8.1 Familias de funciones.
3.8.2 Conjuntos índice.
3.8.3 Teorema de Rice.
3.8.4 Utilidad práctica.

Tema 4 : Máquinas de Turing. (4 horas)
4.1 Definición y modelo.
4.1.1 Alfabeto, estados internos y funciones de transición. Cuadruplas.
4.1.2 Relación funciones computables-máquinas de Turing.
4.1.3 Ejemplos de máquinas de Turing.
4.2 Técnicas de diseño.
4.2.1 Necesidad de las técnicas.
4.2.2 Almacenamiento en el control finito.
4.2.3 Shifting-over.
4.2.4 Speed-Up.
4.3 Modelos alternativos.
4.3.1 Máquinas de varias pistas.
4.3.2 Máquinas de varias cintas.
4.3.2 Máquinas de quintuplas.
4.3.4 Equivalencia de modelos.
4.3.5 Equivalencia formal entre los distintos modelos.
4.4 Máquinas universales.
4.4.1 Proposición de un modelo de máquina de Turing universal.
4.4.2 Consecuencias teóricas.
4.5 Tesis de Church.

Tema 5 : Otros Modelos de Computacion. (4 horas)
5.1 Lenguajes de Post.
5.2 Computación con Modelos de ADN.
5.3 Computación con Autómatas Celulares.
5.4 Computación URM.
5.5 Modelos de Computación en los Números Reales.
5.6 Redes Neuronales.

Programa de Prácticas

Dado el carácter netamente teórico de la asignatura, las prácticas se
centrarán en la resolución de problemas graduados en dificultad que ilustren,
amplíen y afiancen los conceptos principales del temario teórico. En
particular, incluirán aspectos como: resolución de problemas de
Computabilidad, y uso de simuladores de máquinas URM, de máquinas de Turing y
del simulador ILC. La planificación -tentativa- prevista establece la siguiente
distribución temporal:

Problemas: 5 horas.
Simulación: ILC, máquinas de Turing, máquinas URM y Autómatas Celulares: 10
horas

1. Trabajando con ILC
2. Macros con ILC
3. Trazando Computaciones con ILC
4. Composición Funcional con ILC
5. Recursión Primitiva con ILC
6. Computación Universal
7. Máquinas de Turing con JFLAP
8. Applet Simulador de Máquinas URM
9. Applet Simulador de Autómatas Celulares
10. Applet Simulador de Neurona Artificial

-Clases teóricas.
-Clases de problemas.
-Clases de laboratorio.

En los contenidos teóricos se insistirá en el uso de una metodología orientada
al razonamiento formalizado y simbólico con el objeto de desarrollar en el
alumno sus capacidades deductivas y de abstracción. Dichos contenidos se
cubrirán por tanto mediante clases teóricas basadas en un esquema expositivo
formal. Los contenidos prácticos, en cambio, recibirán un enfoque totalmente
diferente, y estarán orientados hacia la resolución de relaciones de
problemas, visitas a páginas web afines a la disciplina, y a la utilización de
simuladores de los modelos explicados durante el curso.

El alumno dispondrá de cronogramas de teoría y prácticas orientativos, donde se
recogerá, al menos, la siguiente información:
a) Fecha prevista para impartir cada tópico concreto del programa.
b) Material de lectura mínimo recomendado para preparar la clase.
c) Conjunto de lecturas y ejercicios para consolidar el tópico de que se trate
d) Fechas de interés: entrega de asignaciones, exámenes, etc.

La evaluación tendrá en cuenta los siguientes componentes:

a)Examen Final de la Asignatura: conteniendo preguntas teóricas cortas y
problemas, con un tiempo de duración nunca superior a las 3 horas, y durante
el cual se permite al alumno el uso de apuntes de clase y bibliografía
libremente. La Convocatoria Oficial se hará pública en el tablón del
Departamento y en el Campus Virtual de la asignatura.

b)Asignaciones de Prácticas: se plantearán asignaciones de prácticas que
el alumno resolverá mediante los simuladores adecuados o los programas que deban
desarrollarse, remitiendo los ficheros solución junto con los documentos que se
especifiquen en los enunciados al profesor en la fecha y forma que este
determine. Su realización y entrega es obligatoria, y tendrán siempre carácter
individual. Su calificación, consideradas individualmente, será de APTO o NO
APTO. Se obtiene APTO globalmente en prácticas cuando al menos el 70% de las
mismas han sido calificadas con APTO.

c)La calificación final de la asignatura vendrá determinada por la calificación
obtenida en el examen final,siempre que se haya obtenido APTO en prácticas.

El alumno debe conocer además que la evaluación se regirá por las siguientes
normas adicionales:

1)La entrega de TODAS las asignaciones de prácticas propuestas en la fecha, hora
y formato de entrega determinados por el profesor ES REQUISITO DE PARTICIPACIÓN
de obligado cumplimiento para superar la asignatura, según establece el art. 2.1
del Reglamento de Evaluación de la UCA. Se admitirá un retraso de hasta 24 horas
sobre la fecha prevista de entrega, pero minorando la calificación en un 20%.
Entregas fuera de este plazo no se admitirán, dándose la práctica por no
presentada. En caso de enfermedad o fuerza mayor documentalmente justificadas, el
profesor indicará al alumno nueva fecha de entrega.

2)Es necesario tener entregada y superadas las prácticas para poder aprobar la
asignatura.

3)La calificación de las prácticas será de APTO o NO APTO. En este
último caso, y SIEMPRE QUE SE HAYAN ENTREGADO TODAS LAS PRÁCTICAS, el alumno
podrá concurrir a un examen práctico de acuerdo a convocatoria hecha pública
por el Centro, de duración no mayor de 90 minutos en el que se permitirá el uso
de apuntes y material bibliográfico. El resultado del citado examen será
igualmente de APTO o NO APTO. Para aquellos alumnos que tengan prácticas sin
entregar, se considerará que no han cumplido con los requisitos de participación
fijados en este instrumento de programación, a los efectos previstos en el art.
2.1 del Reglamento de Evaluación del Alumnado.

4)Los exámenes finales de Febrero, Junio y Septiembre se regirán por los
Estatutos de la Universidad de Cádiz y normativa derivada en cuanto a número de
convocatorias y días de revisión de calificaciones se refiere.

5)A toda convocatoria se acude con el temario completo (tanto teórico como
práctico). No se reservarán calificaciones de partes de la asignatura para
convocatorias sucesivas.

6)Para lo no contemplado en estas notas se estará a lo dispuesto en el
Reglamento de Régimen Académico y Evaluación del Alumnado de la Universidad de
Cádiz.

BIBLIOGRAFÍA BÁSICA

[Alf07] Alfonseca, A., Alfonseca, M. y Moriyón, R. Teoría de Autómatas y
Lenguajes Formales. McGraw-Hill, 2007.

[Bro93] Brookshear, J. Teoría de la Computación: lenguajes formales, autómatas
y complejidad. Addison-Wesley Iberoamericana, 1993.

[Cut94] Cutland, N.J. Computability: An Introduction to Recursive Function
Theory . Cambridge University Press, 1994.

[Dav94] Davis, M., Sigal, R. and Weyuker, E. Computability, Complexity and
Languages. Academic Press, 1994.

[Dav02] Davis, M. La Computadora Universal. Ed. Debate, 2002.

[Hop79] Hopcroft, J. and Ullman, J. Introduction to Automata Theory, Languages
and Computation. Addison-Wesley, 1979.

[Hop02] Hopcroft, J.;  Ullman, J. & Motwani, R. Introducción a la Teoría de
Autómatas, Lenguajes y Computación. (2ª ed.). Addison-Wesley, 2002.

[Gar79] Garey, M and Johnson, D. Computers and Intractability: a guide to the
theory of NP-completness. New York, Freeman, 1979.

[Lee90] Leeuwen, J. V. (ed.) Handbook of Theoretical Computer Science.
Elsevier, 1990.

[Pen90] Penrose, R.. La Nueva Mente del Emperador. Ed. Mondadori, 1990.

[San90] Sancho, J. Lógica Matemática y Computabilidad. Díaz de Santos, S.A.,
1990.

BIBLIOGRAFÍA DE CONSULTA

[Aho92] Aho, A. and Ullman, J.D. Foundations of Computer Science. W. H.
Freeman and Company. New York, 1992

[Cal88] Calude, C. Theories of Computational Complexity. North-Holland, 1988.

[Car89] Carroll, J. and Darrell, L. Theory of Finite Automata with an
Introduction to Formal Languages. Englewood Cliffs, NJ. Prentice Hall, 1989.

[Coh91] Cohen, D. Introduction to Computer Theory. John Wiley and Sons, Inc.
1991.

[Deh93] Dehornoy, P. Complexite et decidabilite. Springer-Verlag, 1993.


[Fer95] Fernández, G. y Sáez, F. Fundamentos de Informática: lógica,
autómatas, algoritmos y lenguajes.  Anaya Multimedia, 1995.

[Jon97] Jones, N. D. Computability and Complexity. The MIT Press, 1997.

[Lew91] Lewis, H and Papadimitriou, C. Elements of the Theory of Computation.
Englewood Cliffs, NH. Prentice Hall, 1991.

[Mar91] Martin, J. Introduction to Languages and the Theory of Computation.
New York, McGraw-Hill, 1991.

[Mcn82] McNaughton, R. Elementary Computability, Formal Languages and
Automata. Prentice Hall, 1982.

[Rev83] Revesz, G. Introduction to Formal Languages. McGraw-Hill, 1983.

[Som88] Sommerhalder, R. and Van Westerhenen S. C. The Theory of
Computability : Programs, Machines, Effectiveness and Feasibility. Addison-
Wesley, 1988.

[Sud88] Sudkamp, T. Languages and Machines, An Introduction to the Theory of
Computer Science. Addison-Wesley Series in Computer Science. Readin, MA.
Addison-Wesley Inc 1988.

[Wil86] Wilf, H.S. Algorithms and Complexity. Prentice-Hall, 1986.

[Woo87] Wood, D. Theory of Computation, New York, John Wiley & Sons, 1987.