<p>Does <a href="https://esolangs.org/wiki/Reversible_Bitfuck" rel="nofollow noreferrer">Reversible Bitfuck</a> qualify? It manipulates a tape of 1-bit cells, and its commands are</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>Command</th>
<th>Description</th>
</tr>
</thead>
<tbody>
<tr>
<td>&gt;</td>
<td>Move right</td>
</tr>
<tr>
<td>&lt;</td>
<td>Move left</td>
</tr>
<tr>
<td>+</td>
<td>Toggle current bit</td>
</tr>
<tr>
<td>[</td>
<td>If current bit is 0, jump to after matching ]</td>
</tr>
<tr>
<td>]</td>
<td>If current bit is 0, jump to after matching [</td>
</tr>
</tbody>
</table>
</div>
<p>The inverse of any program can be obtained by applying the following rules:
<span class="math-container">\begin{align}
(a b)^{-1} &amp;= b^{-1} a^{-1} \\
{&gt;}^{-1} &amp;= {&lt;} \\
{&lt;}^{-1} &amp;= {&gt;} \\
{+}^{-1} &amp;= {+} \\
[a]^{-1} &amp;= [a^{-1}]
\end{align}</span></p>
<p>Then <span class="math-container">$a a^{-1} = \varepsilon$</span>, provided that <span class="math-container">$a$</span> halts on the given tape configuration.</p>

CC BY-SA 4.0
2021-01-20T09:05:28.657Z
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!)
N. Virgo
CC BY-SA 4.0
2021-01-20T04:17:51.600Z
2021-01-20T04:17:51.600Z
user76284
<p>Many years ago I created a language called Kayak (<a href="http://esoteric.sange.fi/essie2/download/kayak/kayak.html" rel="nofollow noreferrer">language spec</a>, <a href="https://esolangs.org/wiki/Kayak" rel="nofollow noreferrer">esolangs.org entry</a>) 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.</p>
<p>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.</p>
<hr />
<p>Also, Turing machines themselves are the original tarpit. The name comes from one of Alan Perlis's <a href="https://en.wikipedia.org/wiki/Epigrams_on_Programming" rel="nofollow noreferrer">epigrams</a>: &quot;Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.&quot; 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.</p>
<hr />
<p>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 <span class="math-container">$x\mapsto (f(x),\text{execution trace})$</span> is computable and injective. If you can do the latter, then given any injective computable <span class="math-container">$f$</span>, you can compute <span class="math-container">$y=f(x)$</span> as the composition of</p>
<ol>
<li><span class="math-container">$x\mapsto (\text{garbage},y)$</span></li>
<li><span class="math-container">$(\text{garbage},y) \mapsto (\text{garbage},y,y)$</span></li>
<li><span class="math-container">$(\text{garbage},y,y) \mapsto (x,y)$</span> (the inverse of step 1)</li>
<li><span class="math-container">$(x,y) \mapsto (x,f^{-1}(y),\text{garbage}') = (x,x,\text{garbage}')$</span></li>
<li><span class="math-container">$(x,x,\text{garbage}') \mapsto (x,\text{garbage}')$</span></li>
<li><span class="math-container">$(x,\text{garbage}') \mapsto y$</span> (the inverse of step 4)</li>
</ol>
<p>That construction is implicit in the various results mentioned in A&amp;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.</p>

CC BY-SA 4.0
2022-05-04T05:04:25.443Z
2022-05-04T05:04:25.443Z
benrg
<p>&quot;r-complete&quot; 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.</p>
<p>am taking this verbose &amp; circuitous question to ask for basically:</p>
<ul>
<li>a simple Turing complete system</li>
<li>reversible</li>
</ul>
<p>try Turing-complete <a href="http://en.wikipedia.org/wiki/Reversible_cellular_automaton" rel="nofollow noreferrer">reversible cellular automata</a> eg:</p>
<ul>
<li><p><a href="http://arxiv.org/ftp/nlin/papers/0501/0501022.pdf" rel="nofollow noreferrer">Two-state, Reversible, Universal Cellular Automata In Three Dimensions</a> Miller/Fredkin</p>
<blockquote>
<p>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.</p>
</blockquote>
</li>
<li><p>K. Imai and K. Morita, <a href="http://www.sciencedirect.com/science/article/pii/S0304397599000997" rel="nofollow noreferrer">A computation-universal two-dimensional 8-state triangular reversible cellular automaton,</a> Theoretical Computer Science 231 (2000), no. 2, 181–191.</p>
<blockquote>
<p>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.</p>
</blockquote>
</li>
</ul>
<p>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 &amp; 86 refs the title is verging on ironic.)</p>
<p><a href="http://hal.archives-ouvertes.fr/docs/00/27/45/63/PDF/102-118.pdf" rel="nofollow noreferrer">UNIVERSALITIES IN CELLULAR AUTOMATA
A (SHORT) SURVEY</a> Ollinger</p>

CC BY-SA 3.0
2014-04-17T06:53:56.557Z
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."
N. Virgo
CC BY-SA 3.0
2014-04-16T17:38:02.517Z
2014-04-16T17:59:55.827Z
2020-06-17T09:38:08.363Z
vzn
<p>This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of <a href="http://link.springer.com/chapter/10.1007/978-3-642-19805-2_4#page-1" rel="noreferrer">Axelsen and Glück</a>, 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.</p>

<p><strong>What I mean by "tarpit"</strong></p>

<p>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 <a href="http://en.wikipedia.org/wiki/Brainfuck" rel="noreferrer">Brainfuck</a>, the <a href="http://en.wikipedia.org/wiki/Rule_110" rel="noreferrer">Rule 110</a> cellular automaton, and the language <a href="http://esolangs.org/wiki/Bitwise_Cyclic_Tag" rel="noreferrer">Bitwise Cyclic Tag</a> (which I like because it's very easy to implement and any binary string is a valid program). </p>

<p>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 <a href="https://www.wolframscience.com/" rel="noreferrer">very large book</a> about, although he didn't use the word "tarpit".</p>

<p><strong>What I mean by "reversible"</strong></p>

<p>I'm interested in reversible computation. In particular, I'm interested in languages that are r-Turing complete, in the sense of <a href="http://link.springer.com/chapter/10.1007/978-3-642-19805-2_4#page-1" rel="noreferrer">Axelsen and Glück</a>, 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 <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-21254-3_8#page-1" rel="noreferrer">Axelsen's reversible universal Turing machine</a>, or the high-level reversible language <a href="http://en.wikipedia.org/wiki/Janus_%28programming_language%29" rel="noreferrer">Janus</a>. (There are many other examples in the literature; it's an active area of research.)</p>

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

<p><sub>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.</sub></p>

<p><strong>What I'm looking for</strong></p>

<p>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.</p>

<p>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.  <a href="http://en.wikipedia.org/wiki/Langton%27s_ant" rel="noreferrer">Langton's ant</a> (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.</p>

<p>(I'm hoping this question will be easier to answer than my <a href="https://cstheory.stackexchange.com/questions/20907/a-lambda-calculus-for-invertible-r-turing-computable-functions">previous related one</a> about a reversible equivalent to the lambda calculus.)</p>

CC BY-SA 3.0
2014-04-15T09:58:55.083Z
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.
N. Virgo
CC BY-SA 3.0
2014-04-15T10:22:47.690Z
$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.
Kaveh
CC BY-SA 3.0
2014-04-15T10:24:07.260Z
ps: you can tag the question with [tag:computability] and [tag:machine-models]. By the way, I don't understand the point of first paragraph and mentioning "trapits", doesn't seem needed for the question.
Kaveh
CC BY-SA 3.0
2014-04-15T15:18:48.463Z
quantum computing? indeed it appears to be possible/simple to take any irreversible computation & convert it to a reversible one... as for "Turing tarpit" it was a term used by Dijkstra(?) but afaik it has no strict formal meaning (other than Turing complete?)...
vzn
CC BY-SA 3.0
2014-04-16T05:38:25.760Z
@Kaveh I've updated the question to contain more background about reversible languages (in Axelsen and Glück's sense), and more detail about what I'm looking for - hopefully the paragraph about tarpits will seem more relevant now.
N. Virgo
CC BY-SA 3.0
2014-04-16T05:41:39.420Z
@vzn I've added more background about r-Turing completeness and more details about what I'm looking for. I agree that there's no formal definition of "tarpit", but I believe that concepts can be useful even if they're not formally defined.
N. Virgo
CC BY-SA 3.0
2014-04-16T05:47:37.637Z
@Kaveh (a brief explanation in terms of your first comment: $x \mapsto (x,f(x))$ is a reversible function, but $(x,f)\mapsto f$ is in general an irreversible one. To get from $(x,f(x))$ to $f(x)$ you have to erase data, which is an irreversible step in general. The r-Turing computable functions are those that can be computed by a reversible Turing machine *without* erasing any data, even after the computation has finished; an r-Turing complete reversible system is one that can compute every r-Turing computable function.)
N. Virgo
CC BY-SA 3.0
2014-04-16T05:59:38.487Z
There is nothing in my comments about erasing x.
Kaveh
CC BY-SA 3.0
2014-04-16T06:07:30.050Z
@Kaveh I know there isn't, and I'm not in any way disagreeing with your comments, just trying to clarify what I'm looking for in terms of the terminology you used. Axelsen and Glück don't consider computing $(x,f(x))$ to be equivalent to computing $f(x)$, precisely because computing $f(x)$ from $(x,f(x))$ involves erasing $x$. Because of this, r-Turing complete systems are a strict subset of Turing complete ones.
N. Virgo
CC BY-SA 3.0
2014-04-16T08:30:55.970Z
If you are concerned with *computatibility* rather than *complexity*, then r-Turing completeness is merely the ability to compute any bijections. Let $f:\{0,1\}^n \to \{0,1\}^n$ be a bijection. If you can compute $(x,0^w,0^n) \mapsto (x,\Gamma(x),f(x))$ for some "garbage" function $\Gamma$, you can compute $(x,0^w,0^n,0^n) \mapsto (x,0^w,0^n,f(x))$ simply by making a safe copy of $f(x)$ and then reversing your original computation. Then, you can – possibly with much more work – simulate the computation $(f(x),0^n) \mapsto (f(x), f^{-1}(f(x)))$ to allow you to erase $x$.
Niel de Beaudrap
CC BY-SA 3.0
2014-04-16T08:37:35.770Z
In any case, Bennett's framework is r-Turing complete in exactly your sense, provided that you allow the reversible computation to make use of "ancilla" bits, which both initially and finally have the value 0. (That is to say: for any bijection $f: \{0,1\}^n \to \{0,1\}^n$, there exists a $w$ such that $F:\{0,1\}^n \times \{0\}^w \to \{0,1\}^n \times \{0\}^w$ evaluating $F(x,0^w) = (f(x),0^w)$ is computable by a reversible circuit. Circuit families are used for bijective $f: \{0,1\}^\ast \to \{0,1\}^\ast$.) You have to erase data, but only by the reversible technique of uncomputation.
Niel de Beaudrap
CC BY-SA 3.0
2014-04-16T08:46:29.053Z
Anyway --- I understand your idea of a "tarpit", but what counts as a tarpit is a matter of complexity. The way that we can determine that any computational system is Turing complete is by showing that it can simulate a Turing machine: and that is by showing how its configurations can encode configurations of Turing machine. That correspondence is a relation which is itself computable, and provides semantics: one can only complain that the correspondence relation is itself "unobvious" (i.e. difficult to compute). How "unobvious" it is, is a question of computational complexity.
Niel de Beaudrap
CC BY-SA 3.0
2014-04-16T11:55:12.147Z
@NieldeBeaudrap (first two comments) r-Turing completeness isn't about bijections over a finite set, it's about injective functions over an infinite one. An example of an r-Turing computable function is $x \mapsto 2x$ over the integers, whose inverse is defined only for even inputs. (The reverse program would simply not halt if given an odd input.) r-Turing computability really is different from Bennett's approach - please take a look at the paper I linked to on the subject.
N. Virgo
CC BY-SA 3.0
2014-04-16T12:02:53.897Z
@NieldeBeaudrap (third comment) another common property of Turing tarpits is the simplicity of the rules that define them. Take the Bitwise Cyclic Tag system that I linked to in the question. I implemented that in Python in 20 minutes, whereas implementing (for example) the lambda calculus would be a much more substantial undertaking. I'm really looking for an r-Turing complete system whose rules are very simple, allowing me to treat it as a dynamical system. If those simple rules also come with nice, non-convoluted semantics then that's great, but I doubt they will - hence "tarpit".
N. Virgo
CC BY-SA 3.0
2014-04-16T15:13:17.077Z
_?!? what is the question?_ plz use ">" fmtting to highlight
vzn
CC BY-SA 3.0
2014-04-16T15:51:16.013Z
@vzn the question is "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 that I did my best to explain.
N. Virgo
CC BY-SA 3.0
2014-04-16T15:52:51.000Z
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?)
vzn
CC BY-SA 3.0
2014-04-16T16:13:24.907Z
@vzn there is a link in the post to the paper by Axelsen and Glück where r-Turing completeness is defined. Attempted definition of tarpit is in q already. Is deliberately informal. No matter how many times you say "I reiterate that there is no formal definition of what I'm looking for", someone always demands a formal definition. Guess that's just a fact if life. Will edit for clarity when at computer.
N. Virgo
CC BY-SA 3.0
2014-04-16T16:33:04.807Z
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!
usul
CC BY-SA 3.0
2014-04-16T17:17:20.500Z
Axelsen/Glück paper links are pay-per-view only. do you have any open refs? think question is unclear, too much verbiage, try [chat] or on [cs.se]. can work with an _informal_ defn of "turing tarpit," did not demand _formal one_, but need _something_, the mere _term_ is not very meaningful & seems rarely used by tcs experts... on the other hand _reversibility_ is indeed a significant TCS topic subj to recent research...
vzn
CC BY-SA 3.0
2014-04-16T17:28:41.850Z
another thought, you might look into reversible [cellular automata](http://en.wikipedia.org/wiki/Cellular_automaton) proven Turing complete...?
vzn
CC BY-SA 3.0
2014-04-17T00:01:18.760Z
@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.
N. Virgo
CC BY-SA 3.0
2014-06-18T09:38:34.013Z
I would like to see a good Wikipedia article on Turing tarpits. What are they?
reinierpost
CC BY-SA 4.0
2022-05-04T05:05:48.987Z
Axelsen and Glück's paper isn't paywalled any more. Actually, it appears it wasn't paywalled even back in 2016, which is the earliest that the Wayback Machine archived the page.
benrg
<fl.formal-languages><computability><machine-models>
Reversible Turing tarpits?
N. Virgo
# Reversible Turing tarpits?

(Asked by: username_0 on 2014-04-15)

This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of [Axelsen and Glück](http://link.springer.com/chapter/10.1007/978-3-642-19805-2_4#page-1), 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](http://en.wikipedia.org/wiki/Brainfuck), the [Rule 110](http://en.wikipedia.org/wiki/Rule_110) cellular automaton, and the language [Bitwise Cyclic Tag](http://esolangs.org/wiki/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](https://www.wolframscience.com/) 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](http://link.springer.com/chapter/10.1007/978-3-642-19805-2_4#page-1), 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](http://link.springer.com/chapter/10.1007%2F978-3-642-21254-3_8#page-1), or the high-level reversible language [Janus](http://en.wikipedia.org/wiki/Janus_%28programming_language%29). (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](http://en.wikipedia.org/wiki/Langton%27s_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](https://cstheory.stackexchange.com/questions/20907/a-lambda-calculus-for-invertible-r-turing-computable-functions) about a reversible equivalent to the lambda calculus.)

**Tags:** fl.formal-languages, computability, machine-models
> **Comments:**
> **username_0**: 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.  
> **username_1**: $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.  
> **username_1**: ps: you can tag the question with [tag:computability] and [tag:machine-models]. By the way, I don't understand the point of first paragraph and mentioning "trapits", doesn't seem needed for the question.  
> **username_2**: quantum computing? indeed it appears to be possible/simple to take any irreversible computation & convert it to a reversible one... as for "Turing tarpit" it was a term used by Dijkstra(?) but afaik it has no strict formal meaning (other than Turing complete?)...  
> **username_0**: @Kaveh I've updated the question to contain more background about reversible languages (in Axelsen and Glück's sense), and more detail about what I'm looking for - hopefully the paragraph about tarpits will seem more relevant now.  
> **username_0**: @vzn I've added more background about r-Turing completeness and more details about what I'm looking for. I agree that there's no formal definition of "tarpit", but I believe that concepts can be useful even if they're not formally defined.  
> **username_0**: @Kaveh (a brief explanation in terms of your first comment: $x \mapsto (x,f(x))$ is a reversible function, but $(x,f)\mapsto f$ is in general an irreversible one. To get from $(x,f(x))$ to $f(x)$ you have to erase data, which is an irreversible step in general. The r-Turing computable functions are those that can be computed by a reversible Turing machine *without* erasing any data, even after the computation has finished; an r-Turing complete reversible system is one that can compute every r-Turing computable function.)  
> **username_1**: There is nothing in my comments about erasing x.  
> **username_0**: @Kaveh I know there isn't, and I'm not in any way disagreeing with your comments, just trying to clarify what I'm looking for in terms of the terminology you used. Axelsen and Glück don't consider computing $(x,f(x))$ to be equivalent to computing $f(x)$, precisely because computing $f(x)$ from $(x,f(x))$ involves erasing $x$. Because of this, r-Turing complete systems are a strict subset of Turing complete ones.  
> **username_3**: If you are concerned with *computatibility* rather than *complexity*, then r-Turing completeness is merely the ability to compute any bijections. Let $f:\{0,1\}^n \to \{0,1\}^n$ be a bijection. If you can compute $(x,0^w,0^n) \mapsto (x,\Gamma(x),f(x))$ for some "garbage" function $\Gamma$, you can compute $(x,0^w,0^n,0^n) \mapsto (x,0^w,0^n,f(x))$ simply by making a safe copy of $f(x)$ and then reversing your original computation. Then, you can – possibly with much more work – simulate the computation $(f(x),0^n) \mapsto (f(x), f^{-1}(f(x)))$ to allow you to erase $x$.  
> **username_3**: In any case, Bennett's framework is r-Turing complete in exactly your sense, provided that you allow the reversible computation to make use of "ancilla" bits, which both initially and finally have the value 0. (That is to say: for any bijection $f: \{0,1\}^n \to \{0,1\}^n$, there exists a $w$ such that $F:\{0,1\}^n \times \{0\}^w \to \{0,1\}^n \times \{0\}^w$ evaluating $F(x,0^w) = (f(x),0^w)$ is computable by a reversible circuit. Circuit families are used for bijective $f: \{0,1\}^\ast \to \{0,1\}^\ast$.) You have to erase data, but only by the reversible technique of uncomputation.  
> **username_3**: Anyway --- I understand your idea of a "tarpit", but what counts as a tarpit is a matter of complexity. The way that we can determine that any computational system is Turing complete is by showing that it can simulate a Turing machine: and that is by showing how its configurations can encode configurations of Turing machine. That correspondence is a relation which is itself computable, and provides semantics: one can only complain that the correspondence relation is itself "unobvious" (i.e. difficult to compute). How "unobvious" it is, is a question of computational complexity.  
> **username_0**: @NieldeBeaudrap (first two comments) r-Turing completeness isn't about bijections over a finite set, it's about injective functions over an infinite one. An example of an r-Turing computable function is $x \mapsto 2x$ over the integers, whose inverse is defined only for even inputs. (The reverse program would simply not halt if given an odd input.) r-Turing computability really is different from Bennett's approach - please take a look at the paper I linked to on the subject.  
> **username_0**: @NieldeBeaudrap (third comment) another common property of Turing tarpits is the simplicity of the rules that define them. Take the Bitwise Cyclic Tag system that I linked to in the question. I implemented that in Python in 20 minutes, whereas implementing (for example) the lambda calculus would be a much more substantial undertaking. I'm really looking for an r-Turing complete system whose rules are very simple, allowing me to treat it as a dynamical system. If those simple rules also come with nice, non-convoluted semantics then that's great, but I doubt they will - hence "tarpit".  
> **username_2**: _?!? what is the question?_ plz use ">" fmtting to highlight  
> **username_0**: @vzn the question is "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 that I did my best to explain.  
> **username_2**: 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?)  
> **username_0**: @vzn there is a link in the post to the paper by Axelsen and Glück where r-Turing completeness is defined. Attempted definition of tarpit is in q already. Is deliberately informal. No matter how many times you say "I reiterate that there is no formal definition of what I'm looking for", someone always demands a formal definition. Guess that's just a fact if life. Will edit for clarity when at computer.  
> **username_4**: 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!  
> **username_2**: Axelsen/Glück paper links are pay-per-view only. do you have any open refs? think question is unclear, too much verbiage, try [chat] or on [cs.se]. can work with an _informal_ defn of "turing tarpit," did not demand _formal one_, but need _something_, the mere _term_ is not very meaningful & seems rarely used by tcs experts... on the other hand _reversibility_ is indeed a significant TCS topic subj to recent research...  
> **username_2**: another thought, you might look into reversible [cellular automata](http://en.wikipedia.org/wiki/Cellular_automaton) proven Turing complete...?  
> **username_0**: @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.  
> **username_5**: I would like to see a good Wikipedia article on Turing tarpits. What are they?  
> **username_6**: Axelsen and Glück's paper isn't paywalled any more. Actually, it appears it wasn't paywalled even back in 2016, which is the earliest that the Wayback Machine archived the page.  

---

## 3 answers

### Answer by username_7 on 2021-01-20. Score: 4

Does [Reversible Bitfuck](https://esolangs.org/wiki/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.

> **Comments:**
> **username_0**: 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!)  

---

### Answer by username_6 on 2022-05-04. Score: 2

Many years ago I created a language called Kayak ([language spec](http://esoteric.sange.fi/essie2/download/kayak/kayak.html), [esolangs.org entry](https://esolangs.org/wiki/Kayak)) 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](https://en.wikipedia.org/wiki/Epigrams_on_Programming): "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 by username_2 on 2014-04-16. Score: -1

"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](http://en.wikipedia.org/wiki/Reversible_cellular_automaton) eg:

* [Two-state, Reversible, Universal Cellular Automata In Three Dimensions](http://arxiv.org/ftp/nlin/papers/0501/0501022.pdf) 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,](http://www.sciencedirect.com/science/article/pii/S0304397599000997) 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](http://hal.archives-ouvertes.fr/docs/00/27/45/63/PDF/102-118.pdf) Ollinger

> **Comments:**
> **username_0**: 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."  

---

