Publicación: A SMALL MINIMAL APERIODIC REVERSIBLE TURING MACHINE
dc.creator | RODRIGO ARIEL TORRES AVILÉS | |
dc.date | 2017 | |
dc.date.accessioned | 2025-01-10T14:54:54Z | |
dc.date.available | 2025-01-10T14:54:54Z | |
dc.date.issued | 2017 | |
dc.description.abstract | 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. | |
dc.format | application/pdf | |
dc.identifier.doi | 10.1016/j.jcss.2016.10.004 | |
dc.identifier.issn | 1090-2724 | |
dc.identifier.issn | 0022-0000 | |
dc.identifier.uri | https://repositorio.ubiobio.cl/handle/123456789/9533 | |
dc.language | spa | |
dc.publisher | JOURNAL OF COMPUTER AND SYSTEM SCIENCES | |
dc.relation.uri | 10.1016/j.jcss.2016.10.004 | |
dc.rights | PUBLICADA | |
dc.title | A SMALL MINIMAL APERIODIC REVERSIBLE TURING MACHINE | |
dc.title.alternative | UNA PEQUEÑA MÁQUINA DE TURING REVERSIBLE APERIÓDICA MÍNIMA | |
dc.type | ARTÍCULO | |
dspace.entity.type | Publication | |
ubb.Estado | PUBLICADA | |
ubb.Otra Reparticion | DEPARTAMENTO DE CIENCIAS DE LA COMPUTACION Y TECNOLOGIA DE LA INFORMACION. | |
ubb.Sede | CHILLÁN |