Reversible Turing tarpits?

Question

This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of Axelsen and Glück, and "tarpit" is a much more informal concept (and might not be a very good choice of word), but I'll do my best to explain what I mean by it.

What I mean by "tarpit"

Some models of computation are designed to be useful in some way. Others just happen to be Turing complete and don't really have any particularly useful properties; these are known as "Turing tarpits". Examples include the language Brainfuck, the Rule 110 cellular automaton, and the language Bitwise Cyclic Tag (which I like because it's very easy to implement and any binary string is a valid program).

There is no formal definition of "Turing tarpit", but for this question I'm using it to mean a fairly simple system (in terms of having a small number of "rules") that "just happens" to be Turing complete, without its internal state having any obvious semantic meaning. The most important aspect for my purposes is the simplicity of the rules, rather than the lack of obvious semantics. Basically we're talking about the sort of things that Stephen Wolfram once wrote a very large book about, although he didn't use the word "tarpit".

What I mean by "reversible"

I'm interested in reversible computation. In particular, I'm interested in languages that are r-Turing complete, in the sense of Axelsen and Glück, which means that they can calculate every computable injective function, and can only calculate injective functions. Now, there are many models of computation that are reversible in this sense, such as Axelsen's reversible universal Turing machine, or the high-level reversible language Janus. (There are many other examples in the literature; it's an active area of research.)

It should be noted that Axelsen and Glück's definition of r-Turing completeness is a different approach to reversible computing than the usual approach due to Bennett. In Bennett's approach a system is allowed to produce "garbage data" that is thrown away at the end of the computation; under such conditions a reversible system can be Turing complete. However, in Axelsen and Glück's approach, the system is not allowed to produce such "junk data", which restricts the class of problems it can compute. (Hence, "r-Turing complete" rather than "Turing complete".)

_{Note: the Axelsen and Glück paper is behind a paywall. This is unfortunate - to my knowledge there is not currently any non-paywalled resource on the subject of r-Turing completeness. I'll try to start a Wikipedia page if I have time, but no promises.}

What I'm looking for

The examples of reversible computing mentioned above are all rather "semantically laden". This is a good thing in most contexts, but it means that the rules required to update their state at each time step are fairly complex. I'm looking for the "tarpits" of reversible computing. That is, more-or-less arbitrary systems with quite simple rules that "just happen" to be r-Turing complete languages. I reiterate that there is no formal definition of what I'm looking for, but I'll know it when I see it, and I think it's a reasonable thing to ask about.

There are a number of things I know of that almost fit the bill, but not quite. There are several reversible cellular automata that have been shown to be Turing complete. Langton's ant (a kind of two-dimensional Turing machine with a fairly arbitrary and quite simple reversible state transition function) is also Turing complete, as long as its initial conditions are allowed to contain infinite repeating patterns. However, with these systems it's not trivial to define a mapping from their state to an "output" in such a way that no junk data gets thrown away. I'm interested specifically in systems that can be thought of as taking an input, performing some sequence of (reversible) transformations on it, and then (if they terminate) returning some output.

(I'm hoping this question will be easier to answer than my previous related one about a reversible equivalent to the lambda calculus.)

Answer 1

Does Reversible Bitfuck qualify? It manipulates a tape of 1-bit cells, and its commands are

Command	Description
>	Move right
<	Move left
+	Toggle current bit
[	If current bit is 0, jump to after matching ]
]	If current bit is 0, jump to after matching [

The inverse of any program can be obtained by applying the following rules: \begin{align} (a b)^{-1} &= b^{-1} a^{-1} \\ {>}^{-1} &= {<} \\ {<}^{-1} &= {>} \\ {+}^{-1} &= {+} \\ [a]^{-1} &= [a^{-1}] \end{align}

Then $a a^{-1} = \varepsilon$, provided that $a$ halts on the given tape configuration.

Answer 2

Many years ago I created a language called Kayak (language spec, esolangs.org entry) that was meant to be a reversible-computing tarpit. It's slightly less primitive than Reversible Brainfuck, since it has callable functions and named variables, but it still has a very simple syntax and semantics.

Kayak programs can dump garbage into a bit bucket that is passed as an optional second argument to the main function. Programs that don't take that argument (or a language subset that doesn't support it) satisfy your no-garbage criterion.

---

Also, Turing machines themselves are the original tarpit. The name comes from one of Alan Perlis's epigrams: "Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy." Therefore I think that reversible Turing machines count as a reversible tarpit. Their output is the entire state of the tape when they enter the halting state, so there is no concept of garbage in the model.

---

r-Turing completeness (the ability to compute any injective computable function without garbage) seems to be equivalent to the ability to compute any computable function with garbage. If you can do the former, then you can do the latter because $x\mapsto (f(x),\text{execution trace})$ is computable and injective. If you can do the latter, then given any injective computable $f$, you can compute $y=f(x)$ as the composition of

1. $x\mapsto (\text{garbage},y)$
2. $(\text{garbage},y) \mapsto (\text{garbage},y,y)$
3. $(\text{garbage},y,y) \mapsto (x,y)$ (the inverse of step 1)
4. $(x,y) \mapsto (x,f^{-1}(y),\text{garbage}') = (x,x,\text{garbage}')$
5. $(x,x,\text{garbage}') \mapsto (x,\text{garbage}')$
6. $(x,\text{garbage}') \mapsto y$ (the inverse of step 4)

That construction is implicit in the various results mentioned in A&G's paper (mostly attributed to Bennett) which they use to justify their definition of r-Turing completeness. Their preference for r-TC over TC-with-garbage seems to be esthetic: they think that the reversible-computing version of TC shouldn't mention garbage, and thanks to this equivalence it doesn't have to.

Answer 3

"r-complete" seems to be a relatively new concept invented by Axelsen and Glück ~2011, possibly not considered much by other authors, and wonder if there is a proof its different than Turing complete.

am taking this verbose & circuitous question to ask for basically:

• a simple Turing complete system
• reversible

try Turing-complete reversible cellular automata eg:

• Two-state, Reversible, Universal Cellular Automata In Three Dimensions Miller/Fredkin

  A novel two-state, Reversible Cellular Automata (RCA) is described. This three-dimensional RCA is shown to be capable of universal computation. Additionally, evidence is offered that this RCA Is capable of universal construction.

• K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton, Theoretical Computer Science 231 (2000), no. 2, 181–191.

  Abstract: A reversible cellular automaton (RCA) is a cellular automaton (CA) whose global function is injective and every configuration has at most one predecessor. Margolus showed that there is a computation-universal two-dimensional 2-state RCA. But his RCA has a non-uniform neighbor, so Morita and Ueno proposed 16-state computation-universal RCA using partitioned cellular automata (PCA). Because PCA can be regarded as a subclass of standard CA, their models have a standard neighbor. In this paper, we show that the number of states of Morita and Ueno's models can be reduced. To decrease the number of states from their models with preserving isotropic and bit-preserving properties, we used a triangular 3-neighbor, and thus an 8-state RCA can be possible. This is the smallest state two-dimensional RCA under the condition of isotropic property in the framework of PCA. We show that our model can simulate basic circuit elements such as unit wires, delay elements, crossing wires, switch gates and inverse switch gates, and it is possible to construct a Fredkin gate by combining these elements. Since Fredkin gate is known to be a universal logic gate, our model has computation-universality.

it was found as a ref in this survey of CAs which might have other helpful leads on the inquiry (eg see sec 7, Reversibility and Universality). (at 17 pgs & 86 refs the title is verging on ironic.)

UNIVERSALITIES IN CELLULAR AUTOMATA A (SHORT) SURVEY Ollinger