Talk:BFFB

Palindromic programs

I am assuming you're reversing [ and ] in the palindrome, as otherwise the reverse of [-] would be ]-[ and you couldn't ever have loops.

Given that, isn't it so that all Brainfuck programs can be trivially palindromised by doing the following: Say P is a valid Brainfuck program, then

+[- P [-]] [[-] reverse(P) -]+

is a palindrome that does the same as P. --Marinus (talk) 20:43, 7 June 2012 (UTC)

I was advised that "mirror palindrome" would be a more correct term. Your method will certainly work in terms of "I/O Output".

That does not quite cover my intended definition of "equivalent".

Consider a bf program

+++-

which when it halts, leaves in a state where the first cell on the tape is 2.

However, if I translate it using your method it will execute P, reset the current cell to zero, exit the loop, skip the "mirror"

loop and increment the current cell to 1. Which means that they will not halt in the same state and therefore I wouldn't consider

them to be equivalent. -- Feuermonster (talk) 07:00, 8 June 2012 (UTC)

Hm I can see this could be tricky. If P contains a , in the right spot after its last ], we could get into the situation where we don't have any relatively positioned cell with a known value at the end of the program. And any rewriting of that would be forced to also contain a , after the last ], or otherwise it would itself have a known value. But if it's palindromic that would mean it contains a , before the first [. And if the original program is of the form ,[main loop],. with no known cell values at the end, then we force the palindromic version to have a . before its first ,, a contradiction. I think this is actually impossible in general. --Ørjan (talk) 20:08, 8 June 2012 (UTC)

Specifically, ,[[>,-]<-[<-]],. would be an example of a program impossible to convert. --Ørjan (talk) 20:18, 8 June 2012 (UTC)

Why can't we use Marinus's method, but before using it we append [>]+ to the program. That should solve the problem, unless I'm mistaken. --Tailcalled (talk) 14:33, 1 July 2012 (UTC)

+++- would be [>]+[-P[-]][[-]reverse(P)-]+[<]. The problem here is still, that [-] destroys the state of the last active cell of p which does not fulfill my intended very strict definition of 'doing the same thing' (by which I mean that the halting states of both programs are the same, if they halt). -- Feuermonster (talk) 14:55, 1 July 2012 (UTC)

Simple TC Proof.

First do this transformation

BFCODE = BF[
   "+" -> "+"
   "-" -> "-"
   ">" -> ">>"
   "<" -> "<<"
   "." -> "."
   "," -> ","
   "[" -> "["
   "]" -> "]"
]

Then use this modified palindrome.

>+[[-]< BFCODE >][< EDOCFB >[-]]+<

Obviously, you need to look at every 2nd cell (starting at zero) after the run as all the movements have been doubled. The only 'damaged' cell is at an odd offset and so not relevant. Rdebath (talk) 15:13, 25 August 2014 (UTC)