¿Existen cintas circulares en las máquinas de Turing?

Question

He estado buscando información sobre este tema sin éxito. ¿Alguien ha descrito las máquinas de Turing sobre cintas circulares en lugar de lineales e infinitas? Como si la cinta pudiera ser descrita con aritmética modular. Si es así (lo que me parece muy probable), ¿quiénes son los autores/documentos que debería leer?

Gracias y perdón si la pregunta es demasiado elemental o ingenua.

Answer 1

Sí. Estas máquinas han sido estudiadas bajo el nombre de máquinas de Turing en el sentido de las agujas del reloj por Neary y Woods [3], quienes demostraron que

Máquina de Turing → máquina de Turing en el sentido de las agujas del reloj → sistema de etiquetas cíclicas →. Regla 110

Neary también indica que estas máquinas se acercan a las máquinas Post de Kudlek y Rogozhin [1, 2].

[1] M. Kudlek e Y. Rogozhin, New small universal circular Post machines. En Rusins Freivalds, editor, Fundamentals of Computation Theory (FCT), volumen 2138 de LNCS, páginas 217-227, Riga, Letonia, agosto de 2001. Springer.

[2] M. Kudlek e Y. Rogozhin, Small universal circular Post machines. Computer Science Journal of Moldova, 9(1):34-52, 2001.

[1] T. Neary y D. Woods, Completitud P del autómata celular Regla 110 , Autómatas, lenguajes y programación. Parte I, 132--143, LNCS 4051 , Springer, Berlín, 2006.