<p>I am not very familiar with the area, but there is some recent work from the programming languages community that might interest you, based on the idea of restricting to a language of type isomorphisms.  In particular, you could have a look at</p>

<ul>
<li><a href="http://www.cs.indiana.edu/~sabry/papers/fractionals.pdf" rel="nofollow">Fractional Types</a> by Roshan P. James, Zachary Sparks, Jacques Carette, and Amr Sabry</li>
</ul>

<p>as well as various related publications which you can find on <a href="http://www.cs.indiana.edu/~sabry/research.html" rel="nofollow">Amr Sabry's website</a>.</p>

CC BY-SA 3.0
2014-02-07T13:30:43.210Z
2014-02-07T13:30:43.210Z
Noam Zeilberger
<p>I'm interested in the concept of "r-Turing completeness", as defined by <a href="http://link.springer.com/chapter/10.1007/978-3-642-19805-2_4#page-1">Axelsen and Glück (2011)</a>. A system is r-Turing complete if it can compute the same set of functions as a reversible Turing machine, <em>without</em> producing any "garbage" data. This is the same as being able to compute every function that is both (a) computable, and (b) injective.</p>

<p>I would like to computationally explore the space of computable injective functions. In order to do this I'm looking for the "most minimal" reversible programming language --- something that can play the equivalent role for r-Turing computability that the lambda calculus plays for Turing computability.</p>

<p>I know that there are many reversible languages that people have developed and proven to be r-Turing complete. However, these are being developed with practical applications in mind, and so their authors concentrate on giving them expressive features rather than making them minimal. </p>

<p>Does anyone know if such a minimal invertible language has been described, or whether there is any research in such a direction? I'm fairly new to the literature on this topic, so I could easily have missed it. Alternatively, does anyone have any insight into how such a language could be created?</p>

<p>Below is a summary of what I'm looking for. I do not know whether it can be created by modifying the lambda calculus itself, or whether a completely different type of language would have to be used.</p>

<ul>
<li>r-Turing complete language - computes all computable invertible functions, and can only computes invertible functions</li>
<li>Syntax and semantics as minimal as possible. (E.g. Lambda calculus has only function definitions and applications, and nothing else.) It isn't necessary for the syntax or semantics to be related to those of the lambda calculus, although they could be.</li>
<li>Program = data. That is, the programs operate on expressions rather than any other kind of data. This guarantees that a program's output can always be interpreted as a program. This probably implies that it has to be a functional rather than an imperative style of language.</li>
<li>There is some systematic way to convert a program into its inverse, which doesn't involve substantially more computation than that involved in actually performing the inverse computation. (Not all invertible languages have this property, but some do.)</li>
</ul>

<p>I should emphasise that Axelsen and Glück's approach to reversible computing is quite different from the well-known approach due to Bennett, where an (in general non-invertible) program is made invertible by returning some information about the computation's history along with the output. r-Turing completeness is about being able to compute injective functions <em>without</em> any additional output. There are several things called variations of "reversible lambda calculus" that are reversible in Bennet's sense - those are not what I'm looking for.</p>

CC BY-SA 3.0
2014-04-16T17:24:57.493Z
r-Turing complete seems like a relatively new defn and it would be helpful to see a proof that its not the same as Turing complete & interpretations/analyses by other authors than those who introduced the concept (& non pay-per-view links if possible)
vzn
<lambda-calculus>
A Lambda calculus for invertible (r-Turing computable) functions
N. Virgo
# A Lambda calculus for invertible (r-Turing computable) functions

(Asked by: username_0 on 2014-02-01)

I'm interested in the concept of "r-Turing completeness", as defined by [Axelsen and Glück (2011)](http://link.springer.com/chapter/10.1007/978-3-642-19805-2_4#page-1). A system is r-Turing complete if it can compute the same set of functions as a reversible Turing machine, *without* producing any "garbage" data. This is the same as being able to compute every function that is both (a) computable, and (b) injective.

I would like to computationally explore the space of computable injective functions. In order to do this I'm looking for the "most minimal" reversible programming language --- something that can play the equivalent role for r-Turing computability that the lambda calculus plays for Turing computability.

I know that there are many reversible languages that people have developed and proven to be r-Turing complete. However, these are being developed with practical applications in mind, and so their authors concentrate on giving them expressive features rather than making them minimal.

Does anyone know if such a minimal invertible language has been described, or whether there is any research in such a direction? I'm fairly new to the literature on this topic, so I could easily have missed it. Alternatively, does anyone have any insight into how such a language could be created?

Below is a summary of what I'm looking for. I do not know whether it can be created by modifying the lambda calculus itself, or whether a completely different type of language would have to be used.

* r-Turing complete language - computes all computable invertible functions, and can only computes invertible functions
* Syntax and semantics as minimal as possible. (E.g. Lambda calculus has only function definitions and applications, and nothing else.) It isn't necessary for the syntax or semantics to be related to those of the lambda calculus, although they could be.
* Program = data. That is, the programs operate on expressions rather than any other kind of data. This guarantees that a program's output can always be interpreted as a program. This probably implies that it has to be a functional rather than an imperative style of language.
* There is some systematic way to convert a program into its inverse, which doesn't involve substantially more computation than that involved in actually performing the inverse computation. (Not all invertible languages have this property, but some do.)

I should emphasise that Axelsen and Glück's approach to reversible computing is quite different from the well-known approach due to Bennett, where an (in general non-invertible) program is made invertible by returning some information about the computation's history along with the output. r-Turing completeness is about being able to compute injective functions *without* any additional output. There are several things called variations of "reversible lambda calculus" that are reversible in Bennet's sense - those are not what I'm looking for.

**Tags:** lambda-calculus
> **Comments:**
> **username_1**: r-Turing complete seems like a relatively new defn and it would be helpful to see a proof that its not the same as Turing complete & interpretations/analyses by other authors than those who introduced the concept (& non pay-per-view links if possible)  

---

## 1 answers

### Answer by username_2 on 2014-02-07. Score: 4

I am not very familiar with the area, but there is some recent work from the programming languages community that might interest you, based on the idea of restricting to a language of type isomorphisms. In particular, you could have a look at

* [Fractional Types](http://www.cs.indiana.edu/~sabry/papers/fractionals.pdf) by Roshan P. James, Zachary Sparks, Jacques Carette, and Amr Sabry

as well as various related publications which you can find on [Amr Sabry's website](http://www.cs.indiana.edu/~sabry/research.html).


---

