Publicación:
A SMALL MINIMAL APERIODIC REVERSIBLE TURING MACHINE

dc.creatorRODRIGO ARIEL TORRES AVILÉS
dc.date2017
dc.date.accessioned2025-01-10T14:54:54Z
dc.date.available2025-01-10T14:54:54Z
dc.date.issued2017
dc.description.abstractA 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.
dc.formatapplication/pdf
dc.identifier.doi10.1016/j.jcss.2016.10.004
dc.identifier.issn1090-2724
dc.identifier.issn0022-0000
dc.identifier.urihttps://repositorio.ubiobio.cl/handle/123456789/9533
dc.languagespa
dc.publisherJOURNAL OF COMPUTER AND SYSTEM SCIENCES
dc.relation.uri10.1016/j.jcss.2016.10.004
dc.rightsPUBLICADA
dc.titleA SMALL MINIMAL APERIODIC REVERSIBLE TURING MACHINE
dc.title.alternativeUNA PEQUEÑA MÁQUINA DE TURING REVERSIBLE APERIÓDICA MÍNIMA
dc.typeARTÍCULO
dspace.entity.typePublication
ubb.EstadoPUBLICADA
ubb.Otra ReparticionDEPARTAMENTO DE CIENCIAS DE LA COMPUTACION Y TECNOLOGIA DE LA INFORMACION.
ubb.SedeCHILLÁN
Archivos