Complejidad Computacional 2018

Clases invitadas en la optativa “Complejidad Computacional” de la Licenciatura en Ciencias de la Computación, Universidad Nacional de Córdoba, viernes 1 y 8 de junio del 2018.

Contacto: Guillaume Hoffmann guillaumh@gmail.com

Referencias

• T. Rado. On non-computable functions. 1962: introduce Busy Beaver
• J. Cocke and M. Minsky. Universality of Tag Systems With P=2. 1964: simulación de Máquinas de Turing por 2-tag systems en tiempo exponencial.
• M. Minsky. Computation: finite and infinite machines. 1967: MT no borrantes universales, repetición del artículo anterior, MT universal de 4 símbolos y 7 estados simulando 2-tag systems.
• M. Kudlek and Y. Rogozhin. A Universal Turing Machine with 3 states and 9 symbols. 2002: MT universal simulaindo 2-tag systems.
• D. Woods and T. Neary. On the time complexity of 2-tag systems and small universal Turing machines. 2006: simulación de MT por 2-tag systems en tiempo polinomial.
• T. Neary. Small universal Turing machines. PhD thesis. 2008: MT universales pequeñas por simulación directa (cap. 3) o via bi-tag systems. (cap. 6). Simulación eficiente de Máquinas de Turing por cyclic tag systems (cap. 4) y por 2-tag systems (cap. 5).
• M. Margenstern. Non erasing Turing machines: a frontier between a decidable halting problem and universality: MT universal no borrante con 125 estados y 2 símbolos, simulando 2-tag systems.