Talk:Reversible Brainfuck

A suggestion for increased symmetry, similar to Kayak: Let the . command zero its cell, and let the tape be left-infinite as well. This way any program which ends with a cleared tape can easily be turned into a reversed program. --Ørjan 17:27, 30 Dec 2006 (UTC)

That would mean that . would be irreversible unless the output were taken into account (which is how Kayak does it), so there's an issue with how much of the system is looked at when considering reversibility. I do like additional symmetry, though. --ais523 11:48, 3 Jan 2007 (UTC)

It doesn't look like loops are possible. If you arrive at a [ or a ] with a nonzero cell, the interpreter will go into an infinite loop bouncing between it and its matching bracket. If it's zero, then it is a NOP. Hence, in order for a program to run successfully (without hanging the interpreter), the brackets must accomplish nothing.

I think specifying that it jumps to the instruction after the bracket solves this, so I'll assume that's what you meant.--Quintopia 07:10, 1 October 2008 (UTC)

That's what I meant, I fixed the spec accordingly. Sorry for the ambiguity! --ais523 20:33, 1 October 2008 (UTC)

I've also been tinkering with reversible Brainfuck implementations (see Nanofuck) and I noticed some special mathematical properties that such languages have. I'm not sure what your math background is, but since each program is reversible, the set of all reversible Brainfuck programs certainly forms a group under concatenation. I've figured out that the set of programs consisting only of +->< is isomorphic to SL(2, Z) if we map phi(+) = {{1, 0}, {1, 1}} and phi(>) = {{1, 1}, {0, 1}} (and also assume that each cell is signed and unbounded) [Edit: oops! this is wrong, clearly phi(+>+<) != phi(>+<+)]. SL(2, Z) is well studied and well understood. If the entire language (with the exception of I/O) is isomorphic to some other well studied group, we could certainly leverage that knowledge! Of special interest is whether or not the "Reversible BF" group can be finitely generated (I expect not). Orby (talk) 03:40, 27 March 2017 (UTC)

That SL(2,Z) thing is nifty and works as long as you only apply + and > (I doubted it for a while but then User:b_jonas reminded me of Calkin-Wilf trees), but I don't think it works when inverses are involved. I get that +>+< and >+<+ have different representations, but they are equivalent programs. I haven't yet found a case where non-equivalent programs give the same matrix, but I'm not yet convinced there isn't one.

Also, alas, the whole language cannot be a group in that way - the problem is loops giving nonterminating programs, which cannot be canceled. See Burro, which is another attempt at making a language that is a group, and which I've always found unsatisfying because its looping mechanism is sort of outside the group, by necessity. (By the way, Talk:Burro also has some discussion about finite generation.) --Ørjan (talk) 16:33, 27 March 2017 (UTC)

Oh cool, thanks for pointing that out. I'm not so convinced about the SL(2, Z) isomorphism now that I'm looking at it in the light of day. +->< definitely forms a group, but I'm not so sure about it's structure... I think this is definitely worthy of further research though, as it could yield some optimization methods. And also, can't nonterminating programs still be inverted in the limit? (e.g. program that fills the tape with ones is inverted by a program that fills the tape with zeros). There are definitely some sticky points about the final resting place of the data pointer though, which I think needs to be finite. Intellectual noodling warning: isn't the information content of the tape necessarily finite even if the program is non-terminating? Edit: obviously I'm wrong, otherwise transcendental numbers wouldn't be computable :D Is that right? I'm going to stop now I'm just confusing myself...

Lessee, if you map a +->< program to the number of >'s minus the number of <'s, that is a group homomorphism onto Z. And its kernel is the set of programs with the same number of >'s as <'s, which is isomorphic to (LaTeXish) \sum_{i\in Z} Z, since all that distinguishes a balanced program is the total increment at each cell. So it's a group extension of Z by \sum_{i\in Z} Z. My hunch is that this is too "big" to fit in SL(2,Z), but I'm not a real group theory expert. Incidentally, many brainfuck implementations do try to detect loops with "balanced" >'s and <'s, and optimize at least some of them specially.

For finite computation, I think the reverse program of [>+] is [-<]. I'm not sure how to define the effects of those such that they are inverses even when one of them can run infinitely. I expect it will get really hairy for more complicated programs. I'm reminded of attempts to define sums of divergent series, which at one extreme can involve ultrafilters, none of which can be explicitly written down and which require the axiom of choice just to exist. --Ørjan (talk) 23:49, 27 March 2017 (UTC)