Theoretical Computing Models
DOI link for Theoretical Computing Models
Theoretical Computing Models book
According to the widely accepted Church-Turing thesis, every computable function (or algorithm) can be expressed as a Turing Machine program [BenAmram, 2005]. Hence, to theoretically examine the reversibility of any computation in general, it is sufficient to focus on the reversibility of computations realized by Turing Machine programs. If there were a way to execute any Turing Machine program reversibly, then any computable function can be executed reversibly. With these considerations, the classical Turing Machine model is examined here and shown to be irreversible. Next, the construction of a Reversible Turing Machine model is described such that the machine is not only reversible by design, but also capable of reversibly simulating any or-
dinary Turing Machine program, thus proving that any computable function can be reversibly executed.