PublicaciĂłn:
UNDECIDABILITY OF THE SPEED POSITIVENESS PROBLEM IN REVERSIBLE AND COMPLETE TURING MACHINES

Vista sencilla de Ă­tem
dc.creatorRODRIGO ARIEL TORRES AVILÉS
dc.date2021
dc.date.accessioned2025-01-10T15:18:36Z
dc.date.available2025-01-10T15:18:36Z
dc.date.issued2021
dc.description.abstractIN 2014, JEANDEL PROVED THAT TWO DYNAMICAL PROPERTIES REGARDING TURING MACHINES CAN BE COMPUTABLE WITH ANY DESIRED ERROR , THE TURING MACHINE MAXIMUM SPEED AND TOPOLOGICAL ENTROPY. BOTH PROBLEMS WERE PROVED IN PARALLEL, USING EQUIVALENT PROPERTIES. THOSE RESULTS WERE UNEXPECTED, AS MOST (IF NOT ALL) DYNAMICAL PROPERTIES ARE UNDECIDABLE. NEVERTHELESS, TOPOLOGICAL ENTROPY POSITIVENESS FOR REVERSIBLE AND COMPLETE TURING MACHINES WAS SHORTLY PROVED TO BE UNDECIDABLE, WITH A REDUCTION OF THE HALTING PROBLEM WITH EMPTY COUNTERS IN 2-REVERSIBLE COUNTER MACHINES. UNFORTUNATELY, THE SAME PROOF COULD NOT BE USED TO PROVE UNDECIDABILITY OF SPEED POSITIVENESS. IN THIS RESEARCH, WE PROVE THE UNDECIDABILITY OF HOMOGENEOUS TAPE REACHABILITY PROBLEM FOR APERIODIC AND REVERSIBLE TURING MACHINES, IN ORDER TO USE IT TO PROVE THE UNDECIDABILITY OF THE SPEED POSITIVENESS PROBLEM FOR COMPLETE AND REVERSIBLE TURING MACHINES.
dc.formatapplication/pdf
dc.identifier.doi10.1016/j.jcss.2021.04.007
dc.identifier.issn1090-2724
dc.identifier.issn0022-0000
dc.identifier.urihttps://repositorio.ubiobio.cl/handle/123456789/11403
dc.languagespa
dc.publisherJOURNAL OF COMPUTER AND SYSTEM SCIENCES
dc.relation.uri10.1016/j.jcss.2021.04.007
dc.rightsPUBLICADA
dc.titleUNDECIDABILITY OF THE SPEED POSITIVENESS PROBLEM IN REVERSIBLE AND COMPLETE TURING MACHINES
dc.typeARTĂŤCULO
dspace.entity.typePublication
ubb.EstadoPUBLICADA
ubb.Otra ReparticionDEPARTAMENTO DE SISTEMAS DE INFORMACION
ubb.SedeCONCEPCIĂ“N
Archivos
Colecciones
ArtĂ­culos cientĂ­ficos