Resumen de la Tesis:

Un Autómata con cabezal se mueve en un espacio discreto a tiempo discreto y esta compuesto por un conjunto finito de estados internos, un cabezal capaz de leer la información almacenada en la posición en la que este se encuentra y escribir en ella, y una función de transición; la que en cada iteración, dependiendo del estado interno en el que se encuentre el autómata y la información de la casilla visitada, dictará el nuevo estado interno, la información que dejara en la casilla y la dirección en la que se moverá el cabezal en dicha iteración. Las máquinas con piedras son similares a un autómata de un cabezal solo que la única forma que tienen de marcar su entorno consiste en el uso de un cierto numero de piedras. Estas piedras pueden ser depositadas en la grilla y recogidas de esta, y además están enumeradas o coloreadas, es decir, son piedras diferenciables una de otra. Estas maquinas fueron introducidos por Blum y Hewitt con la motivación del reconocimiento de guras. El posterior trabajo de Delorme y Mazoyer demuestra que 3 piedras le otorgan tanto poder como el de una máquina de Turing, pero que con 2 piedras su comportamiento limitado. En esta memoria abordamos un concepto introducido por Gajardo y Mazoyer llamado t-shift, que consiste en seguir la trayectoria de una máquina registrando la secuencia de estados internos y símbolos leídos en cada iteración. El t-shift asociado a alguna máquina con cabezal, define un lenguaje, y la complejidad de este está estrechamente relacionada con la complejidad de la dinámica exhibida por la máquina con cabezal. Mediante una construcción explícita, nosotros demostramos que el t-shift de una máquina con 2 piedras y 0 símbolos puede ser reconocido por un autómata determinista con 2 pilas, además probamos que un autómata determinista con 1 pila no es capaz de reconocer el t-shift asociado a ciertas máquinas con 2 piedras, probando con esto que el t-shift de una máquina de 2 piedras necesitar a de dos pilas para ser reconocido. Además, en el Capítulo 1 estudiamos 2 reglas particulares dentro de una clase especial de máquinas con cabezal que generalizan a la Hormiga de Langton llamadas abejas, demostrando que una de estas reglas es isomorfa a la inversa de la otra, y que la complejidad del t-shift asociado, excede la de lenguaje regular.