Zigzags in Turing machines - Computer Science > Formal Languages and Automata TheoryReportar como inadecuado




Zigzags in Turing machines - Computer Science > Formal Languages and Automata Theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We study one-head machines through symbolic and topological dynamics. Inparticular, a subshift is associated to the subshift, and we are interested inits complexity in terms of realtime recognition. We emphasize the class ofone-head machines whose subshift can be recognized by a deterministic pushdownautomaton. We prove that this class corresponds to particular restrictions onthe head movement, and to equicontinuity in associated dynamical systems.



Autor: Anahi Gajardo, Pierre Guillon

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados