Sobreyectividad en subshifts asociados a máquinas de Turing

Abstract

Esta Investigación se presenta para dar conformidad a los requisitos exigidos por la Universidad de Bío-Bío en el proceso de titulación para la carrera de Ingeniería Civil en Informática. Una máquina de Turing es un modelo matemático computacional que simboliza a una máquina abstracta, la cual manipula símbolos en una cinta siguiendo una serie de instrucciones definidas para esta. La importancia de las máquinas de Turing radica en que la computación actual se basa en estos modelos, es decir, los limites de lo que un computador puede y no puede hacer pueden ser estudiados con ellas. Por otro lado, la teoría de sistemas dinámicos permite estudiar la evolución en el tiempo de un sistema. Aplicando esta teoría a máquinas de Turing se han definido en la literatura los sistemas dinámicos conocidos como “máquina de Turing con cinta móvil”, “máquina de Turing con cabezal móvil” y “t-shift”. En la literatura se han estudiado diversas propiedades sobre estos sistemas dinámicos, entre las cuales la sobreyectividad y la decibilidad de dicha propiedad son de interés en este trabajo. Puntualmente, en este trabajo se propone un nuevo sistema dinámico denominado “h-shift” y se aborda la decibilidad de la propiedad de sobreyectividad en los sistemas dinámicos derivados de máquinas de Turing “h-shift” y “t-shift de radio 1”. El aporte de este trabajo es concluir sobre la decibilidad del problema de la sobreyectividad en el t-shift de radio 1, que resulta ser decidible, y del problema de sobreyectividad en el h-shift, que resulta ser indecidible mediante una reducción al problema de alcanzabilidad.