Ejecicios Unidad 1

Fecha de entrega: del 20 al 22 de octubre.

1. 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$.
2. Escribir las configuraciones succesivas de la “máquina sin estado” mencionada en el teórico, corriendo con palabra inicial AaabbbB.
3. Libro de Sipser, ejercicio 3.1.
4. Demostrar: * Si $L$ es decidible entonces su complemento $\bar{L}$ lo es. * Todo lenguaje regular $L$ es decidible. * El conjunto de lenguajes decidibles es cerrado bajo unión, interseccion y complemento.
5. Demostrar la substitución de MT con cinta infinita en las dos direcciones, por una cinta infinita en una sola dirección.
6. 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$.
7. 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é?