Time-symmetric Turing machines for computable involutions
Keisuke Nakano · Science of Computer Programming · 2021
A reversible Turing machine is a forward and backward deterministic Turing machine, which has been an expressive model of reversible computation. It is obvious that every reversible Turing machine computes an injective function under a function semantics in which the initial and the final configuration of a run corresponds to an input and an output of the function. Axelsen and Glück showed the opposite direction that every injective computable function can be computed by a reversible Turing machine. This paper provides a similar result on involutions instead of injective functions. An involution, also called a self-inverse function, is a function f that is its own inverse, i.e., f(f(x))=x holds whenever f(x) is defined. The paper presents a computational model of involution as a variant of Turing machines, called a time-symmetric Turing machine. The computational model is shown to be expressive in the sense that not only does a time-symmetric Turing machine always compute an involution but also every computable involution can be computed by a time-symmetric Turing machine. As any involution is injective (hence reversible), any time-symmetric Turing machine is a reversible Turing machine. Furthermore, the existence of a universal time-symmetric Turing machine is shown under an appropriate redefinition of universality introduced by Axelsen and Glück for reversible Turing machines.