A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines
We construct a 1-tape 98-state 10-symbol universal reversible Turing machine (URTM(98,10)) that directly simulates reversible counter machines (RCMs). The objective of this construction is not to minimize the numbers of states and tape symbols, but to give a URTM a reasonable size whose simula...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2024-11-01
|
| Series: | Computer Science Journal of Moldova |
| Subjects: | |
| Online Access: | https://www.math.md/files/csjm/v32-n3/v32-n3-(pp425-445).pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846161019608498176 |
|---|---|
| author | Kenichi Morita |
| author_facet | Kenichi Morita |
| author_sort | Kenichi Morita |
| collection | DOAJ |
| description | We construct a 1-tape 98-state 10-symbol universal reversible Turing machine
(URTM(98,10)) that directly simulates reversible counter machines (RCMs).
The objective of this construction is not to minimize the numbers of states
and tape symbols, but to give a URTM a reasonable size whose simulating
processes of RCMs are easily understood.
Here, we choose RCMs as the target machines of simulation, since the class
of RCMs is known to be Turing universal, and their operations are very simple.
Furthermore, using the framework of RCMs in the program form (rather
than the quadruple form), construction of a URTM is simplified.
We also created a computer simulator for the URTM(98,10), by which
simulation processes of RCMs are visualized. |
| format | Article |
| id | doaj-art-2b19c8a536d542fa996c9b9aeb9e17a3 |
| institution | Kabale University |
| issn | 1561-4042 2587-4330 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
| record_format | Article |
| series | Computer Science Journal of Moldova |
| spelling | doaj-art-2b19c8a536d542fa996c9b9aeb9e17a32024-11-21T11:36:40ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422587-43302024-11-01323(96)425445https://doi.org/10.56415/csjm.v32.22A Universal Reversible Turing Machine that Directly Simulates Reversible Counter MachinesKenichi Morita0https://orcid.org/0000-0002-9833-0539Hiroshima University, Higashi-Hiroshima, JapanWe construct a 1-tape 98-state 10-symbol universal reversible Turing machine (URTM(98,10)) that directly simulates reversible counter machines (RCMs). The objective of this construction is not to minimize the numbers of states and tape symbols, but to give a URTM a reasonable size whose simulating processes of RCMs are easily understood. Here, we choose RCMs as the target machines of simulation, since the class of RCMs is known to be Turing universal, and their operations are very simple. Furthermore, using the framework of RCMs in the program form (rather than the quadruple form), construction of a URTM is simplified. We also created a computer simulator for the URTM(98,10), by which simulation processes of RCMs are visualized. https://www.math.md/files/csjm/v32-n3/v32-n3-(pp425-445).pdfreversible computingreversible turing machineuniversal turing machinereversible counter machine |
| spellingShingle | Kenichi Morita A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines Computer Science Journal of Moldova reversible computing reversible turing machine universal turing machine reversible counter machine |
| title | A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines |
| title_full | A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines |
| title_fullStr | A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines |
| title_full_unstemmed | A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines |
| title_short | A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines |
| title_sort | universal reversible turing machine that directly simulates reversible counter machines |
| topic | reversible computing reversible turing machine universal turing machine reversible counter machine |
| url | https://www.math.md/files/csjm/v32-n3/v32-n3-(pp425-445).pdf |
| work_keys_str_mv | AT kenichimorita auniversalreversibleturingmachinethatdirectlysimulatesreversiblecountermachines AT kenichimorita universalreversibleturingmachinethatdirectlysimulatesreversiblecountermachines |