Time-symmetric Turing machines for computable involutions

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Article number102748
JournalScience of Computer Programming
Publication statusPublished - 2022 Mar 1


  • Bidirectional transformation language
  • Computable involution
  • Reversible Turing machine
  • Self-inverse function
  • Time-symmetric machine

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Time-symmetric Turing machines for computable involutions'. Together they form a unique fingerprint.

Cite this