RISC variant of the Turing machines

This text is about an extremely simple computation model, based on the classical method of Alan Turing.


Let's consider a class of Turing machines working under the following limitation: every time when the head reads a value V from the tape, the head, without considering the present condition, writes back the value (1-V). I call this class RTM (Reversal Turing Machines).

The alphabet of all machines is set [0,1] and V->(1-V) means that 1->0 and 0->1.

If you implement such a Turing machine in hardware, you would notice that on every cycle is performed excange of 3 bits between the controlling part and the tape (read, write, addressing left/right). But in RTM itself, only exchange of 2 bits is performed (read, addressing left/right), because the process of writing is reduced to simple reversing of the present cell value.

On the other hand, RTM class is sufficient for random computation. The transformation TM -> RTM is comparatively simple and efficient. The compilation scheme for TM -> RTM increases the number of states up to 8 times and the performing time up to 3 times.


These results can help simplify the making of DNA or other kinds of chemical computers.

I have a remark concerning the terminology of DNA computation and DNA computers. All living beings consist of many bodily DNA computers, designed by chaos 3.5x10^9 years ago. When we speak of DNA computers, we think about a kind of a machine, a human artifact. A more appropriate name for the latter is DNACDH (DNA Computers, Designed by Humans).


This page is maintained by Georgi Georgiev (Skelet).