Autómatas de Pila y Máquinas de Turing Estructurados

Abstract

Presentamos una sintaxis simple para definir máquinas de Turing y autómatas de pila indeterministas que evita el uso de estados y, en su lugar, usa listas de instrucciones y bucles. De esta manera, una máquina de Turing es un programa con instrucciones y bucles estructurados, y un autómata de pila es un programa con una pila. Se persiguen dos objetivos: el primero, acercar los resultados de autómatas a la práctica diaria de programación estructurada y, el segundo, simplificar las demostraciones apelando a la intuición del estudiante conocedor del potencial de la programación moderna. El resultado es un mayor interés y confianza de los estudiantes en el estudio de estos temas.