key: cord-0047283-po98mw6n
authors: Nakano, Keisuke
title: Involutory Turing Machines
date: 2020-06-17
journal: Reversible Computation
DOI: 10.1007/978-3-030-52482-1_3
sha: 3815006a0c539246337e2a4ce7c187c632552fc1
doc_id: 47283
cord_uid: po98mw6n

An involutory function, also called involution, is a function [Formula: see text] that is its own inverse, i.e., [Formula: see text] holds whenever [Formula: see text] is defined. This paper presents a computational model of involution as a variant of Turing machines, called an involutory Turing machine. The computational model is shown to be complete in the sense that not only does an involutory Turing machine always compute an involution but also every involutory computable function can be computed by an involutory Turing machine. As any involution is injective (hence reversible), any involutory Turing machine forms a standard reversible Turing machine that is backward deterministic. Furthermore, the existence of a universal involutory Turing machine is shown under an appropriate redefinition of universality given by Axelsen and Glück for reversible Turing machines. This work is motivated by characterizing bidirectional transformation languages.

An involutory function, also called involution, is a function that is its own inverse, i.e., f (f (x)) = x holds whenever f (x) is defined. In mathematics, because of their symmetric behavior, involutions have been used for solving functional equations and proving theorems, e.g., Zagier's one-sentence proof for Fermat's theorem on sums of two squares [12] . Even in computer science, involutions appear in cryptographic systems such as one-time pad and RC4.

This paper presents a computational model for involution as a variant of Turing machines with function semantics, where input and output words are specified by tapes of initial and final configurations, respectively. The idea to have such a model for involution is to impose a restriction on a standard Turing machine so that the reversed run of every valid run is valid. The restriction can be simply described by associating one transition rule with another according to a certain involution over states. We call it an involutory Turing machine. It is easy to find that an involutory Turing machine always computes an involution under the restriction. The present paper takes a further step. The involutory Turing machine is shown to be a 'complete' computational model for involution: any involutory computable function can be defined by an involutory Turing machine. That is, for a given non-involutory Turing machine that computes an involution, there exists an equivalent involutory Turing machine. This work is inspired by Axelsen and Glück's work [1, 2] where the expressiveness of reversible Turing machines is discussed. A reversible Turing machine is defined as a backward-deterministic Turing machine and hence computes only an injective function. They have shown that any injective computable function can be defined by a reversible Turing machine as we will show for involutory Turing machines. As an involutory function is a special kind of injective function, an involutory Turing machine can be regarded as a special reversible Turing machine.

Furthermore, this paper addresses the universality of involutory Turing machines as done by Axelsen and Glück [2] for reversible Turing machines. A standard Turing machine is said to be universal if it can simulate any Turing machine on arbitrary input, and it is known that there is a universal Turing machine. As for involutory Turing machines, there is no universal machine under the same definition of universality because the simulating function is not involutory. Therefore, we adopt an alternative definition of universality which has been introduced by Axelsen and Glück for reversible Turing machines. In their definition, the universal machine is allowed to preserve a given machine description as part of the output. We will show the existence of a universal involutory Turing machine under this redefinition.

In summary, the main contributions of this paper are as follows.

-An involutory Turing machine is proposed as a multi-tape Turing machine with restrictive transition rules and tape permutation. An involutory Turing machine always computes an involution. -An involutory Turing machine is shown to be complete, i.e., every computable involution is defined by an involutory Turing machine. -It is shown that for every k-tape involutory Turing machine, there exists a 2-tape involutory Turing machine that computes an isomorphic function. -It is shown that there exists a universal involutory Turing machine in terms of an appropriate definition of universality.

In addition to the above, our design choice, limitations, and applications of involutory Turing machines will be discussed in Sect. 6. In particular, an application to bidirectional transformation will shed a light on a practical aspect of our computational model for involution. The restriction imposed on Turing machines to be involutory coincides with time symmetry introduced by Gajardo et al. [5] for cellular automata to describe a corresponding physical notion. One might call our model a time-symmetric Turing machine in this sense. More detail is discussed as one of the related work in Sect. 7.

The set of non-negative integers is denoted by N. For n ∈ N, the set {1, . . . , n} is denoted by [n] , in particular, [0] = ∅. The set of all words over an alphabet (that is a finite set of symbols) Σ is denoted by Σ * . For convenience, we assume that a nested tuple of words can be regarded as a flattened one, e.g., ((w 1 , w 2 ), w 3 ) and (w 1 , (w 2 , w 3 )) may be identified with (w 1 , w 2 , w 3 ) for

A permutation on [k] is a bijective function over [k] for a fixed integer k ∈ N. A permutation can be expressed as the product of disjoint cycles, e.g., (1 5 4)(3 7) denotes a permutation π such that π(1) = 5, π(5) = 4, π(4) = 1, π(3) = 7, π(7) = 3, and π(i) = i for any other i. The inversion of a permutation is obtained by reversing every cycle, e.g., ((1 5 4)(3 7)) −1 = (4 5 1)(7 3).

The Turing machine is one of the best-known computational models which can implement any computable function. A Turing machine manipulates symbols on a doubly-infinite tape of cells according to an internal state and a fixed transition relation. We use a triplet format [2] to represent the transition relation without loss of generality. Although it is well known that they are equivalent to singletape Turing machines in power [10] , we consider multi-tape Turing machines to make it easy to investigate various properties of involutory Turing machines. Moreover, our model of multi-tape Turing machines has a single instruction for permuting the order of tapes. This feature does not change the expressive power of Turing machines. As its byproduct, we can limit any other instruction only to the first tape. To apply an instruction to the other tape, we permute tapes so as for the tape to be the first before the instruction (and permute them back if needed).

A k-tape Turing machine T is a tuple (Q, Σ, q ini , q fin , Δ) where Q is a finite set of states, Σ is a tape alphabet not containing the special blank symbol , q ini ∈ Q is the initial state, q fin ∈ Q is the final state, and Δ = Δ rw Δ ↔ Δ is a ternary relation defining a set of transition rules where:

where Σ stands for Σ { } and Π k is the set of all permutations over [k] . For q, q ∈ Q, a symbol rule in Δ rw has the form (q, s⇒s , q ) with s, s ∈ Σ ; a move rule in Δ ↔ has the form (q, d, q ) with d ∈ { , , }; a permutation rule in Δ has the form (q, π, q ) with permutation π ∈ Π k . A permutation rule is said to be involutory if π is involutory.

As presented in [2] , symbol rules and move rules are independently given for the convenience of further discussion. Although these two kinds of actions are caused by a single rule in standard Turing machines [10] , the separation of rules does not change the expressiveness of functions. It is easy to simulate a transition rule in a standard Turing machine by two transition rules and extra states in the present model. Moreover, the present model introduces permutation rules (q, π, q ), which permute k tapes without moving their heads in the order given by a permutation π. Again, they do not change the expressiveness because the operation can be simulated by a standard Turing machine with maintaining the left and right ends at the used cells for every tape to copy them to each other.

The configuration of a k-tape Turing machine is specified by the current internal state and k tapes with their tape head. The status of a tape with its head is represented by l, s, r ∈ Σ ω × Σ × Σ ω where s is the symbol at its head position and l and r are the left and right tapes of the head. Note that Σ ω is the set of infinite words going infinitely to the right. Accordingly, l is 'mirrored' where its first symbol is the immediate left one of the head.

The configuration of a k-tape Turing machine T = (Q, Σ, q ini , q fin , Δ) is a tuple (q, ( l 1 , s 1 , r 1 , . . . , l k , s k , r k )) where q ∈ Q is an internal state, l i , r i ∈ Σ ω for each i ∈ [k] are the left and right of the i-th tape head and include only finite non-blank symbols, and s i ∈ Σ for each i ∈ [k] is the symbol at the i-th tape head. The set of all configurations of T is written by C T .

Let T = (Q, Σ, q ini , q fin , Δ) be a k-tape Turing machine. Then a single computation step is defined as a relation T over C T such that (q, ( l, s, r , . . . )) T (q , ( l, s , r , . . . )) when (q, s⇒s , q ) ∈ Δ (q, ( s l, s, r , . . . )) T (q , ( l, s , sr , . . . )) when (q, , q ) ∈ Δ (q, ( l, s, r , . . . )) T (q , ( l, s, r , . . . )) when (q, , q ) ∈ Δ (q, ( l, s, s r , . . . )) T (q , ( sl, s , r , . . . )) when (q, , q ) ∈ Δ (q, (t 1 , . . . , t k )) T (q , (t π(1) , . . . , t π(k) )) when (q, π, q ) ∈ Δ.

The reflexive transitive closure of T is denoted by * T .

The semantics of a k-tape Turing machine T is given by a relation over k words based on * T as below. We follow the style of Axelsen and Glück called a function semantics where an input and an output word are in the tape at the initial and the final configuration of a run, respectively, rather than the usual style with input and output tapes. This view makes it easier to capture the functional behavior of Turing machines. In the rest of the paper, a finite word w ∈ Σ * is used to represent an infinite word w ω ∈ Σ ω ; thereby ε denotes ω .

Let T = (Q, Σ, q ini , q fin , Δ) be a k-tape Turing machine. The semantics of T , denoted by T , is given by the relation

Recall that we may write T (w 1 , . . . , w k ) = (w 1 , . . . , w k ) if T is functional.

In the rest of the paper, for every Turing machine T it is assumed that for any sequence (q ini , ( l 1 , s 1 , r 1 , . . . , l k , s k , r k )) * T (q fin , ( l 1 , s 1 , r 1 , . . . , l k , s k , r k )) of computation steps, we have (l 1 , s 1 ) = · · · = (l k , s k ) = (ε, ) if and only if (l 1 , s 1 ) = · · · = (l k , s k ) = (ε, ). We call it the tidiness assumption.

Here are two examples of Turing machines. It is easy to see that they naturally conform to the tidiness assumption. Moreover, both examples are reversible as seen later.

Example 3.5. Let π be a permutation on [k] . The k-tape Turing machine Perm(π) = ({q ini , q fin }, Σ, q ini , q fin , {(q ini , π, q fin )}) computes a function which permutes its arguments in accordance with π.

(q next , , q bnot ), (q bnot , 0⇒1, q next ), (q bnot , 1⇒0, q next ), (q bnot , ⇒ , q back ), (q back , , q done ), (q done , 0⇒0, q back ), (q done , 1⇒1, q back ), (q done , ⇒ , q fin )} computes a bitwise negation.

Definition 3.4 implies that the semantics of a Turing machine returns a tuple that consists of the same number of words as a given input. However, when the function either accepts (returns) only empty word for some specific arguments, we may regard it as a function whose input (output) tuple consists of fewer words. The next example Dup (1) illustrates the case where a 2-tape Turing machine computes a function that takes a single word and returns a pair of words.

Let T = (Q, Σ, q ini , q fin , Δ) be a k-tape Turing machine. Then T is forward deterministic if, for any distinct pair (q, a 1 , q 1 ), (q, a 2 , q 2 ) ∈ Δ of transition rules, we have a 1 = s 1 ⇒s 1 and a 2 = s 2 ⇒s 2 with some s 1 , s 1 , s 2 , s 2 ∈ Σ and s 1 = s 2 . The Turing machine T is backward deterministic if, for any distinct pair (q 1 , a 1 , q), (q 2 , a 2 , q) ∈ Δ of transition rules, we have a 1 = s 1 ⇒s 1 and a 2 = s 2 ⇒s 2 with some s 1 , s 1 , s 2 , s 2 ∈ Σ and s 1 = s 2 .

The forward (backward) deterministic Turing machine has no pair of move rules which have the same source (target) state. With regard to a configuration step C 1 T C 2 , C 1 uniquely determines C 2 if T is forward deterministic while C 2 uniquely determines C 1 if T is backward deterministic. The definition of forward and backward determinism is exactly the same as local forward and backward determinism in [2] .

Given an involutory function ϕ over a set Q of states such ϕ(q ini ) = q fin (hence, ϕ(q fin ) = q ini ), let us define a function ϕ which 'flips' transition rules in terms of ϕ. This function plays important roles to recognize properties of reversible and involutory Turing machines. The function ϕ is defined as a bijective function over transition rules by ϕ ((q, (a 1 , a 2 , . . . , a k ) , q )) = (ϕ(q ), (a −1

. The function ϕ is naturally extended for a set of transition rules and a Turing machine. For a set Δ of transition rules, ϕ(Δ) represents { ϕ(r) | r ∈ Δ}. For a k-tape Turing machine T = (Q, Σ, q ini , q fin , Δ), ϕ(T ) represents (Q, Σ, q fin , q ini , ϕ(Δ)). For a k-tape Turing machine T , ϕ(T ) is forward (backward) deterministic if T is backward (forward) deterministic. It is easy to see that the function ϕ is involutory for any involutory function ϕ, that is, ϕ( ϕ(x)) = x for any transition rule, any set of transition rules, and any Turing machine x as long as ϕ(x) is defined.

Let the function ϕ be extended for a configuration of a Turing machine as well so that ϕ((q, (t 1 , . . . , t k ))) = (ϕ(q), (t 1 , . . . , t k )). Then the following proposition holds straightforwardly. Proposition 3.10. Let T be a k-tape Turing machine and ϕ be an involution over a set of states in T . Then, for any a computation step

The simplest function ι as such ϕ is given as ι(q ini ) = q fin , ι(q fin ) = q ini , and ι(q) = q for q ∈ Q \ {q ini , q fin }. Let us write T −1 for ι(T ). Then, for a given reversible Turing machine T , T −1 gives an inversion of T as shown by Bennett [3] and reformulated by Axelsen and Glück [2] .

Proof. For simplicity of the proof, only the case of k = 1 is shown. The proof can be easily generalized to the other cases. Let T = (Q, Σ, q ini , q fin , Δ) be a 1-tape reversible Turing machine. The equation

A reversible Turing machine is a complete model in the sense that every injective computable function can be defined by a reversible Turing machine, which has been proved by Axelsen and Glück. Even though our computational model slightly differs from their one in that it has tape permutation rules, their proof of the statement works in our setting because our k-tape Turing machine can simulate theirs with k tapes and vice versa. [2] ). The reversible Turing machines can compute exactly all injective computable functions. That is, given a k-tape Turing machine T such that T is injective, there is a k-tape reversible Turing machine T such that T = T .

The Turing machines Perm(π) given in Example 3.5, T bnot given in Example 3.6, and Dup(k) given in Example 3.7 are all reversible. In particular, the inverse Dup(k) −1 computes a partial function that checks equivalence between the first k words and the last k words and returns the k words if the check succeeds.

Let T 1 = (Q 1 , Σ, q ini,1 , q fin,1 , Δ 1 ) and T 2 = (Q 2 , Σ, q ini,2 , q fin,2 , Δ 2 ) be k-tape Turing machines where Q 1 ∩ Q 2 = ∅ without loss of generality. The concatenation of T 1 and T 2 , denoted by T 2 • T 1 , is a k-tape Turing machine (Q 1 Q 2 , Σ, q ini,1 , q fin,2 , Δ 1 Δ 2 {(q fin,1 , , q ini,2 )}).

In the case where Q 1 and Q 2 are not disjoint, every state in either should be renamed before the concatenation. The reversibility of Turing machines is closed under concatenation as stated below. The proof is straightforward. Proposition 3.14 (Concatenation of reversible Turing machines). If T 1 and T 2 are reversible Turing machines, so is T 2 • T 1 .

The semantics of concatenation of two reversible Turing machines is equivalent to the function composition of their semantics as shown in the following theorem. Note that Turing machines to be concatenated are assumed tidy. The Turing machine obtained by the concatenation is also tidy.

For two k-tape reversible Turing machines T 1 and T 2 , we have

Proof. For simplicity of the proof, only the case of k = 1 is shown. The proof can be easily generalized to the other cases. Let T 1 = (Q 1 , Σ, q ini,1 , q fin,1 , Δ 1 ) and T 2 = (Q 2 , Σ, q ini,2 , q fin,2 , Δ 2 ) be k-tape Turing machines. When T (w 1 ) = w 2 , we show that there exists w such that T 1 (w 1 ) = w and T 2 (w) = w 2 . By the construction of T = T 2 • T 1 , there exists a sequence of computation steps (q ini,1 , ε, , w ) * T (q fin,2 , ε, , v ). Because of the construction of transition rules of T , the sequence contains exactly one computation step induced by the rule (q fin,1 , , q ini,2 ) which bridges Q 1 and Q 2 . Hence, the sequence has the form (q ini,1 , ε, , w ) * T (q fin,1 , l, s, w ) T (q ini,2 , l, s, w ) * T (q fin,2 , ε, , v ). The tidiness assumption and determinism (coming from reversibility) of T 1 and T 2 result in l = ε, s = , T 1 (w 1 ) = w , and T 2 (w ) = w 2 .

The k-tape Turing machine T can be seen as the m-tape Turing machine when k ≤ m by leaving all (k + 1)-th through m-th tapes and their heads unchanged. We write Ext k m (T ) for the extended Turing machine. w 1 , . . . , w k , w k+1 , . . . , w m ) = ( T (w 1 , . . . , w k ), w k+1 , . . . , w m ) for any words w 1 , . . . , w k , w k+1 , . . . , w m whenever the right-hand side is defined. If T is reversible, so is Ext k m (T ). Furthermore, (Ext k m (T )) −1 = Ext k m (T −1 ) holds.

Involutory Turing machines are introduced and investigated in this section. As reversible Turing machines exactly characterize all injective computable functions, involutory Turing machines exactly characterize all involutory computable functions. As every involutory function is injective, an involutory Turing machine is defined as a special kind of reversible Turing machine. The tape reduction on the involutory Turing machines is also addressed in this section.

Let T = (Q, Σ, q ini , q fin , Δ) be a k-tape Turing machine and ϕ be an involutory function over Q such that ϕ(q ini ) = q fin (hence ϕ(q fin ) = q ini ). Then T is involutory if T is reversible, ϕ(T ) = T holds, and every permutation rule is involutory. The function ϕ is called a state involution of T .

Proof. Let T = (Q, Σ, q ini , q fin , Δ) be an involutory Turing machine with state involution ϕ. We show that

By definition, we have (q ini , ε, , w ) * T (q fin , ε, , v ). Since T is involutory, that is, ϕ(T ) = T , we have (q ini , ε, , v ) * T (q fin , ε, , w ) by Proposition 3.10.

The Turing machine T bnot in Example 3.6 is not involutory, although its semantics is involutory. We will see later that there exists an involutory Turing machine equivalent to a given Turing machine whenever its semantics is involutory.

The class of involutory Turing machines have one of the typical and trivial properties of involution, that is closed under conjugation, i.e., for any injective function g, g −1 •f •g is involutory whenever so is f . In terms of Turing machines, the property is described by the following statement.

Let T be a k-tape involutory Turing machine. For any k-tape reversible Turing machine T r , the k-tape reversible Turing machine T −1 r • T • T r is involutory.

Proof. Let T = (Q, Σ, q ini , q fin , Δ) be a k-tape involutory Turing machine with state involution ϕ, and T r = (Q r , Σ r , q ini,r , q fin,r , Δ r ) be a k-tape reversible Turing machine. We assume that every state q r of T −1 r is renamed toq r and let Q r = {q r | q r ∈ Q r }. Since the k-tape Turing machine T c = T −1 r • T • T r is reversible from Proposition 3.14, it suffices to show the existence of a state involution of T c . The state involution ϕ c : Q c → Q c with Q c =Q r Q Q r can be defined by ϕ c (q r ) = q r forq r ∈Q r , ϕ c (q) = ϕ(q) for q ∈ Q, and ϕ c (q r ) =q r for q r ∈ Q r .

For an injective function f , a function g(x, y) = (f (y), f −1 (x)) is involutory because g(g(x, y)) = (f (f −1 (x)), f −1 (f (y))) = (x, y) holds as long as g(x, y) is defined. Similarly, a 2-tape involutory Turing machine can be constructed from a 1-tape reversible Turing machine. The following lemma shows a more general statement.

Given a k-tape reversible Turing machine T , there exists a 2k-tape involutory Turing machine T such that T (w 1 , . . . , w k , v 1 , . . . , v k ) = ( T −1 (v 1 , . . . , v k ) , T (w 1 , . . . , w k )) for any input words w 1 , . . . , w k , v 1 , . . . , v k of T .

Proof. Let T = (Q, Σ, q ini , q fin , Δ) be a k-tape reversible Turing machine. The corresponding 2k-tape Turing machine T is constructed as

where π is an involutory permutation on [2k] such that π(i) = k + i and π(k + i) = i hold for any i ∈ [k]. The Turing machine T is involutory by Lemma 4.4 since Perm(π) in the middle is involutory.

As for the semantics of T , we can check the present statement by . . . , w k ) ).

Now we show one of the main theorems which states any involutory computable function can be implemented by an involutory Turing machine. For any non-involutory Turing machine, an equivalent involutory Turing machine can be constructed whenever its semantics is involutory. Recall that in our function semantics of Turing machines a function some of whose arguments and results are always empty words is regarded as that with fewer arguments and results as mentioned in the previous section. In the following statement, for a given k-tape non-involutory Turing machine, a 2k-tape involutory Turing machine is constructed whose semantics function has k arguments and k outputs that are always empty.

The involutory Turing machines can compute any involutory computable function. More specifically, given a k-tape Turing machine T such that T is involutory, there is a 2k-tape involutory Turing machine T such that T = T .

Proof. Let T be a k-tape Turing machine which computes an involution. Since an involution is injective, there exists a k-tape reversible Turing machine T r such that T r = T by Theorem 3.12. Thus we have a 2k-tape involutory Turing machine T i such that T i (w 1 , . . . , w k , v 1 , . . . , v k ) = ( T r −1 (w 1 , . . . , w k ), . . . , v k ) ) by Lemma 4.5. Consider a 2k-tape Turing machine given by

which is involutory by Lemma 4.4. Then, (w 1 , . . . , w k , w 1 , . . . , w k 

holds where Theorem 3.11 and Theorem 3.15 are used. Since T r = T is involutory, two k-tuples of the argument of Dup(k) −1 are equal. By the definition of Dup(k) −1 , we have T (w 1 , . . . , w k ) = T (w 1 , . . . , w k ).

How expressive are multi-tape involutory Turing machines compared to those equipped with fewer tapes? It is well known that a multi-tape Turing machine can be simulated by a single-tape Turing machine with an injective encoding from a tuple of words to a single word. The simulation is called a tape reduction, which is also possible for reversible Turing machines [1, 2] . Concerning involutory Turing machines, any multi-tape involutory Turing machine can be simulated by a 2-tape involutory Turing machine whose semantics is a function over words that encode a tuple of words (where one of the tapes is always the empty word in the initial and final configuration). . . . , v k , w 1 , . . . , w k ∈ Σ * . The function f is obviously computable. Since f is injective, there exists a 1-tape reversible Turing machine T r whose semantics is equivalent to f . Furthermore, since T is involutory from Theorem 4.2, f is also involutory. By Theorem 4.6, there exists a 2-tape involutory Turing machine which concludes the statement of this theorem.

A tape reduction to a single-tape involutory Turing machine will be discussed in Sect. 6.

A standard Turing machine is said to be universal if it simulates an arbitrary Turing machine. More exactly, a universal Turing machine takes a pair of words: one is a Gödel number T (as a word) representing a Turing machine T and another is an input word of T . It returns the output word T (x). The Gödel numbering − is an injective computable function that generates a word representation for a Turing machine. The notion of universality is called classical universality here to distinguish with another universality introduced later. For simplicity, only 1-tape Turing machines are considered which are to be simulated by a universal Turing machine. The results can be easily generalized to multi-tape Turing machines.

A Turing machine U is said to be classically universal if U ( T , x) = T (x) holds for any Turing machine T and its input word x of T .

No involutory Turing machine is classically universal since the function U in the definition above is obviously not involutory. Because the function is not even injective, no universal reversible Turing machine exists. Axelsen and Glück relaxed the definition of universality in a natural way; they showed that there exists a universal reversible Turing machine under the definition. We follow their definition for the universality of involutory Turing machines.

) holds for any involutory Turing machine T and its input word x of T .

The existence of an ITM-universal involutory Turing machine is easily obtained by the completeness of involutory Turing machines shown in Theorem 4.6. Proof. Let f be a function equivalent to the semantics of an involutory Turing machine to be ITM-universal given in Definition 5.2, i.e., f ( T , x) = ( T , T (x)) for any involutory Turing machine T and its input words of T . What we must show is that there exists an involutory Turing machine whose semantics is equivalent to f . Note that f is computable. By Theorem 4.6, it suffices to show that f is involutory. This is verified by f (f ( T , x)) = f ( T , T (x)) = ( T , T ( T (x))) = ( T , x) where the last equality comes from Theorem 4.2.

Theorem 5.3 only shows the existence of an ITM-universal involutory Turing machine. The proof of the theorem relies on Theorem 3.12 (via Theorem 4.6) which requires an impractical generate-and-test inversion method [2, Lemma 3] . This kind of problem has already been recognized in proving the existence of universal reversible Turing machines by Axelsen and Glück [2] . They gave a solution to that by constructing a universal reversible Turing machine from a classically universal Turing machine. We employ their idea for the direct construction of an ITM-universal involutory Turing machine. Since their construction gives a noninvolutory Turing machine, we shall show a different construction using Landauer embedding and Bennett's trick for a classically universal Turing machine. [2, 8] ). Let T = (Q, Σ, q ini , q fin , Δ) be a k-tape Turing machine. Then, there exists a (k + 1)-tape reversible Turing machine Lan(T ) such that Lan(T ) (w 1 , . . . , w k , ε) = ( T (w 1 , . . . , w k ), trace(T, w 1 , . . . , w k )) where trace is a function encoding a history of applied rules on the corresponding run into Σ * .

As mentioned in [2] , Bennett's trick gives an input-preserving reversible Turing machine for an arbitrary Turing machine. [3] ). Let T be a k-tape Turing machine. Then, there exists a (2k + 1)-tape reversible Turing machine Ben(T ) such that Ben(T ) (w 1 , . . . , w k ) = (w 1 , . . . , w k , T (w 1 , . . . , w k )).

For the proposition above, a similar proof to that of [2, Lemma 6] does work by 

This section describes the design choice of permutation rules and the limitation of tape reduction for our involutory Turing machines. The applications of our computational model will also be discussed.

Design Choice. One may feel it unusual for the definition of a multi-tape Turing machine to have tape permutation rules. A k-tape Turing machine is typically defined by specifying a set of transition rules as

The typical definition forces one to rewrite or move at all tapes simultaneously 1 . An involutory Turing machine could be defined on this model with the same restriction ϕ(Δ) = Δ as ours. It is easy to see that the model always computes an involution by a similar proof to that of Theorem 4.2. However, it is not easy to show the expressiveness like Theorem 4.6 for the model without permutation rules. Although the author believes but cannot prove that the expressiveness does not hold without permutation rules, the readers may surmise it intuitively by trying to define a 2-tape Turing machine Perm ((1 2) ) that swaps an input pair. The simplest way to do this is first to swap each from left to right and then return the head back to the left end. Note that it does not conform to the restriction above to be involutory. The reversed run is no longer valid for any renaming states. There might exist a tricky way to implement the swap function without permutation rules. The author speculates that it is impossible, though.

Limitation of Tape Reduction. Theorem 4.7 states that any k-tape involutory Turing machine can be simulated by a 2-tape involutory Turing machine. A natural question is whether it is possible by a 1-tape involutory Turing machine. Again, the author believes it is impossible. Consider a 1-tape Turing machine T bnot in Example 3.6, which is not involutory but whose semantics is involutory. By Theorem 4.6, there exists a 2-tape involutory Turing machine equivalent to T bnot . It is found hard to define a 1-tape involutory Turing machine for a similar reason to the observation above on defining the swap function without permutation rules. The author speculates the reduction to a single tape is impossible in general but leaves the proof for future work as well.

Application to Bidirectional Transformation. This work is originally motivated by characterizing programming languages for bidirectional transformation, which enables us to synchronize multiple data and maintain their consistency. A typical bidirectional transformation is specified by a pair of forward (get : S → V ) and backward (put : S × V → S) transformations over sources S and views V where two functions are required to be consistent in some sense. More specifically, the following three laws are to be satisfied for the consistency (called very-wellbehavedness in [4] ):

for any s ∈ S and v, v ∈ V . Some bidirectional programming languages impose a syntactic restriction to programmers so that it conforms to the consistency. However, due to the restriction, it is hard to characterize how powerful each programming language is. As expressiveness of general programming languages can be characterized by Turing machines, we need a computational model to characterize all pairs of computable functions get and put that satisfy consistency. An involutory Turing machine gives a partial solution to this problem because of its expressiveness. Consistency implies that a function f :

holds. Thereby any correct bidirectional program can be computed by a 2tape involutory Turing machine under some encoding. Conversely, a 2-tape involutory Turing machine does not always specify a correct bidirectional program. The author believes that there exists a computational model given by an appropriately-restricted involutory Turing machine, which exactly covers all consistent bidirectional transformations. The present work will be a good starting point to characterize bidirectional programming languages.

Program Inversion. A program inverter pinv is a function that takes the Gödel number of a Turing machine T and returns that of a Turing machine whose semantics is the inverse of T . i.e., pinv ( T ) = T −1 holds. Axelsen and Glück have shown that there exists a 2-tape reversible Turing machine that computes pinv . They employ the result as a lemma to construct a universal reversible Turing machine from a classically universal Turing machine. Although we do not need such a lemma for the construction of a universal involutory Turing machine, the same statement also holds for the involutory Turing machine.

There exists a 2-tape involutory Turing machine T which computes a program inverter for reversible Turing machines, that is, T ( R ) = R −1 holds for any reversible Turing machine R.

Proof. There exists a 1-tape reversible Turing machine T r such that T r ( R ) = R −1 by [2, Lemma 15]. Since T r is involutory, there exists a 2-tape involutory Turing machine whose semantics is equivalent to T r by Theorem 4.6.

This work is strongly inspired by Axelsen and Glück's [2] . They showed that (1) any injective computable function can be implemented by a reversible Turing machine, (2) the number of tapes of a reversible Turing machine can be reduced with preserving its semantics, (3) there exists a universal reversible Turing machine, and (4) a universal reversible Turing machine can be constructed from a universal Turing machine. In the present paper, we have addressed these properties for involutory Turing machines instead of reversible Turing machines. Regarding (1), (3), and (4), similar results have been obtained. Interestingly, their proofs are rather different from those of the corresponding theorems for reversible Turing machines. Regarding (2), we failed to find an equivalent singletape involutory Turing machine for an arbitrary multi-tape involutory Turing machine. This might be an inherent limitation of involutory Turing machines as we have discussed in Sect. 6.

An involutory Turing machine may remind some readers of a symmetric Turing machine introduced by Lewis and Papadimitriou [9] , where its computation step is symmetric. A symmetric Turing machine can be considered as a variant of an involutory Turing machine whose state involution is the identity function by ignoring the requirement of ϕ(q ini ) = q fin and ϕ(q fin ) = q ini 2 . However, symmetric Turing machines give a computational model completely different from involutory Turing machines. A symmetric Turing machine defines an undirected graph specified by its configurations and computation steps; its run is a path from the initial one to the final one. This model has been introduced to specify the computational complexity of the undirected st-connectivity (USTCON) problem and is known to be at least as powerful as a deterministic Turing machine.

Gajardo, Kari, and Moreira [5] introduced time symmetry for cellular automata to import a notion in physical theories where forward and backward time directions cannot be distinguished. The time symmetry is specified by an involution which connects the corresponding states and transitions as involutory Turing machines do. Kutrib and Worsch [7] later ported the notion of time symmetry into finite automata and pushdown automata. Involutory Turing machines may be called time-symmetric Turing machines along this line. Nevertheless, our computational model should be called an involutory Turing machine in the present paper owing to our purpose to characterize all computable involutions unlike the previous time-symmetric machines: Gajardo et al.'s time-symmetric cellular automata compute a composition of two involutions but not a single involution. Although it would be worthwhile to investigate the time symmetry and other related properties of involutory Turing machines, they are left for future work.

A computational model for involution has been presented. The model is a variant of a multi-tape Turing machine, called an involutory Turing machine, which imposes a restriction on state transition rules so that the reversed run of every valid run should be valid. The model has been shown to be expressive enough in the sense that not only does an involutory Turing machine always compute an involution but also any involution can be computed by an involutory Turing machine. It has also been shown that there exists a universal involutory Turing machine that can simulate an arbitrary involutory Turing machine.

This work naturally introduces a notion of i-Turing completeness, i.e., a programming language L is said to be i-Turing complete if every program in L defines an involution and every involutory Turing machine can be simulated by a program in L. A similar notion called r-Turing completeness [1, 2] has been employed for characterizing reversible programming languages [6, 11] . As dis-cussed in Sect. 6, i-Turing completeness or its variant will be used to characterize bidirectional programming languages in the future.

What do reversible programs compute?

On reversible turing machines and their function universality

Logical reversibility of computation

Three complementary approaches to bidirectional programming

On time-symmetry in cellular automata

A linear-time self-interpreter of a reversible imperative language

Time-symmetric machines

Irreversibility and heat generation in the computing process

Symmetric space-bounded computation

Introduction to the theory of computation

Principles of a reversible programming language

A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares

Acknowledment. I am grateful to Robert Glück who has kindly lectured to me about reversible Turing machines and their expressiveness. 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 JP17K00007, JP18H03204, and JP18H04093.