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

  • 2
    $\begingroup$ I've no idea how to tag this question. It would be neat if there were a reversible-computing tag, but I don't have the rep to create one. $\endgroup$ – Nathaniel Apr 15 '14 at 9:58
  • 2
    $\begingroup$ $x \mapsto (x,f(x))$ is an invertible function. If your model contain all invertible computable functions it will contain these for all computable $f$, so it has to be essentially Turing-complete. For total invertible ones, an artificial model is to combine TMs with post-processing to make sure they never output any value for more than one input, but it will not give you all partial computable 1-1 functions. $\endgroup$ – Kaveh Apr 15 '14 at 10:22
  • 2
    $\begingroup$ there is maybe a decent question struggling to break free here. the question sentence you state in the last comment appears nowhere in the posted question. the question can only be answered via some attempted defn of "turing tarpit" not in comments but in the post... (can you link to a defn of "r-Turing complete" somewhere? ideally wikipedia?) $\endgroup$ – vzn Apr 16 '14 at 15:52
  • 1
    $\begingroup$ I agree with vzn that it is a bit hard to get the crux of your question from your post. It seems to be the sentence "I'm looking for the 'tarpits' of reversible computing", but it's not very clear; some formatting (even just bolding this sentence) would probably help! $\endgroup$ – usul Apr 16 '14 at 16:33
  • 2
    $\begingroup$ @vzn honestly, I urge you to read the question properly before continuing to criticise it. The topic of cellular automata is already discussed in the text. $\endgroup$ – Nathaniel Apr 17 '14 at 0:01

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.

  • $\begingroup$ I like this a lot. I guess the output would be considered to be whatever's left on the tape when it halts? It's not obvious whether it has the property of r-Turing completeness - that seems a subtle issue and would need a proof different from the proof of Turing completeness given at the link - but I'd give it decent odds. (This question was related to a project that I stopped working on some time ago, so I no longer really need an answer, but it's nice to see one that has some potential!) $\endgroup$ – Nathaniel Jan 20 at 9:05

"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.)


  • 2
    $\begingroup$ I'm aware of work on reversible CAs dating back to the 70s, but, from the question: "There are several reversible cellular automata that have been shown to be Turing complete ... 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." $\endgroup$ – Nathaniel Apr 17 '14 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.