Publicación: A SMALL MINIMAL APERIODIC REVERSIBLE TURING MACHINE
Fecha
2017
Autores
Título de la revista
ISSN de la revista
Título del volumen
Editor
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Resumen
A SIMPLE REVERSIBLE TURING MACHINE WITH FOUR STATES, THREE SYMBOLS AND NO HALTING CONFIGURATION IS CONSTRUCTED THAT HAS NO PERIODIC ORBIT, SIMPLIFYING A CONSTRUCTION BY BLONDEL, CASSAIGNE AND NICHITIU AND POSITIVELY ANSWERING A CONJECTURE BY KARI AND OLLINGER. THE CONSTRUCTED MACHINE HAS OTHER INTERESTING PROPERTIES: IT IS SYMMETRIC BOTH FOR SPACE AND TIME AND HAS A TOPOLOGICALLY MINIMAL ASSOCIATED DYNAMICAL SYSTEM WHOSE COLUMN SHIFT IS ASSOCIATED TO A SUBSTITUTION. USING A PARTICULAR EMBEDDING TECHNIQUE OF AN ARBITRARY REVERSIBLE TURING MACHINE INTO THE ONE PRESENTED, IT IS PROVEN THAT THE PROBLEM OF DETERMINING IF A GIVEN REVERSIBLE TURING MACHINE WITHOUT HALTING STATE HAS A PERIODIC ORBIT IS UNDECIDABLE.
