Turing machines with bijective transition functions are [[Thermodynamics of computation#Logical reversibility|logically reversible]]. A Turing machine is defined by a set of transition rules, which each have five elements: - The current state $a$ - The symbol on the tape at the current head position $x$ - The new symbol to write on the tape $y$ - The direction to move, $d \in \{ -1, 0, 1 \}$ - The new state $b$ If the first two elements match the current configuration of the machine, then the new symbol is written, the machine head moves in the specified direction, and the new state is entered. In order for the machine to work deterministically, only one rule can match at a time; concretely, no two rules can share the same $a$ and the same $x$. Reversibility asks for the same property in the reverse direction: it should be possible to figure out which rule was applied last, and undo it. Here's a quick proof explaining when that happens. Suppose the machine is in state $Q_1$, and the machine head is at a position $n_1 \in \mathbb{Z}$. We would like to find the predecessor state $Q_0$, the previous position of the head $n_0$, and the symbol $x$ previously on the tape at location $n_0$. This is equivalent to "undoing" a rule that leads to the current configuration, and is possible if and only if there is exactly one such rule. Rules are tuples of the form $(a, x, y, d, b)$. First, ignore all rules except the ones where $b = Q_1$. Pick two rules $R_1 = (a_1, x_1, y_1, d_1, Q_1)$ and $R_2 = (a_2, x_2, y_2, d_2, Q_1)$ from the remaining set (if there is only one such rule, we are done, and if there are zero, the machine halts). Suppose for the sake of contradiction that $d_1 \neq d_2$. Then, remembering that $n_1$ is the current position of the head, let the symbol at position $n_1 - d_1$ be $y_1$, and $n_1 - d_2$ be $y_2$. Then, it is clear that either $R_1$ or $R_2$ could yield the current configuration, and the machine is not reversible. So, it must be the case that for any rules $R_1, R_2$ that share a terminal state, $d_1 = d_2$. This is the first condition. The second condition is simply: for $R_1, R_2$ as above, $y_1 \neq y_2$, because this is the only way to differentiate between the terminal conditions of rules that have the same direction $d$ and yield state $Q_1$. To summarize: for every set of rules that share a terminal state $b$, all rules in that set must have the same direction $d$, and no two rules can have the same terminal symbol $y$. In symbols: $ b_1 = b_2 \implies (d_1 = d_2 \, \land y_1 \neq y_2) $