PublicaciĂłn: REVERSIBILITY IN TURING MACHINE TOPOLOGICAL MODELS
Fecha
2023
Autores
TĂtulo de la revista
ISSN de la revista
TĂtulo del volumen
Editor
2022 41ST INTERNATIONAL CONFERENCE OF THE CHILEAN COMPUTER SCIENCE SOCIETY (SCCC)
Resumen
REVERSIBILITY IS EQUIVALENT TO SURJECTIVITY WITHIN TURING MACHINE TOPOLOGICAL SYSTEMS. ALTHOUGH REVERSIBILITY IS A DECIDABLE PROPERTY IN TURING MACHINES, A PROPER REVERSE TURING MACHINE DOES NOT EXIST IN THE STANDARD TURING MODEL. TRADITIONAL SOLUTIONS TO THIS PROBLEM IMPLY REDUCING THE SPEED OF THE REVERSIBLE TURING MACHINE, THEREFORE AFFECTING ITS DYNAMICS. ALSO, TRACES OF TOPOLOGICAL DYNAMICAL SYSTEMS OF TURING MACHINES CAN BE SURJECTIVE WHEN THE ORIGINAL TURING MACHINE IS NOT. A SOLUTION IS A REVERSIBLE TURING MACHINE, CONSIDERING A SHIFT IN THE TAPE DEPENDING ON THE ACTUAL STATE, AND ALSO IT IS PROVEN THAT SURJECTIVITY IS UNDECIDABLE FOR TURING MACHINE SUBSHIFTS ONLY WHEN THE RADIUS IS 0.
