Ejecicios Unidad 1
Fecha de entrega: del 20 al 22 de octubre.
- Sea C el lenguaje de las capicuas sobre el vocabulario {0, 1}. Definir una maquina de Turing que decida C (con 2 cintas). Escribir las configuraciones succeibas de esa máquina con la entrada 01010.
- Escribir las configuraciones succesivas de la "máquina sin estado" mencionada en el teórico, corriendo con palabra inicial AaabbbB.
- Libro de Sipser, ejercicio 3.1.
- Demostrar:
- Si L es decidible entonces su complemento L̄ lo es.
- Todo lenguaje regular L es decidible.
- El conjunto de lenguajes decidibles es cerrado bajo unión, interseccion y complemento.
- Demostrar la substitución de MT con cinta infinita en las dos direcciones, por una cinta infinita en una sola dirección.
- Describir los pasos principales de ejecución de una máquina que decide el lenguaje de los pares < a, p > con a un automatas, p una palabra, tales que a reconoce p.
- Leer "Who Can Name The Biggest Number?" de Scott Aaronson, y el artículo wikipedia de Busy Beaver.
- Describir en castellano las funciones Busy Beaver.
- ¿Esas funciones son computables? ¿Porqué?