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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1561-4042 2587-4330 |