TY - JOUR

T1 - Time-symmetric Turing machines for computable involutions

AU - Nakano, Keisuke

N1 - Funding Information:
I am grateful to Robert Glück who has kindly lectured to me about reversible Turing machines and their expressive power. I also thank Kanae Tsushima for her observation on the involutoriness of bidirectional transformation and Mirai Ikebuchi for carefully proofreading the manuscript. Furthermore, I want to appreciate anonymous reviewers' fruitful comments on a close connection with time-symmetric machines. This work was partially supported by JSPS KAKENHI Grant Numbers JP17H06099 , JP18H04093 , and JP21K11744 .
Publisher Copyright:
© 2021 The Author

PY - 2022/3/1

Y1 - 2022/3/1

N2 - 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.

AB - 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.

KW - Bidirectional transformation language

KW - Computable involution

KW - Reversible Turing machine

KW - Self-inverse function

KW - Time-symmetric machine

UR - http://www.scopus.com/inward/record.url?scp=85119695502&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85119695502&partnerID=8YFLogxK

U2 - 10.1016/j.scico.2021.102748

DO - 10.1016/j.scico.2021.102748

M3 - Article

AN - SCOPUS:85119695502

SN - 0167-6423

VL - 215

JO - Science of Computer Programming

JF - Science of Computer Programming

M1 - 102748

ER -