Talk:Revaver2pi

Not just a group, but an abelian group?

It does look like, on first blush, that Revaver2pi does constitute a "group language" in the style of Burro. If I were to go about writing a proof for this, I'd start by ignoring expressions, under the assumption that an expression will always evaluate to the same thing in two successive executions of the same operation. (That's not hard to see, but writing out all the cases would be tedious.) The main thing I don't understand is the abstained teleport groups, but it looks like those might be safely ignorable too.

However, one thing that worries me is this. From what I understand, a group where every element is its own inverse is necessarily abelian. Being an abelian group would imply that all Revaver2pi operations commute with each other. That would in turn imply that it doesn't matter what order they come in. I doubt that there is even a remote possibility this is true: will an arbitrary permutation of a Revaver2pi program always compute the very same function as the original program? I have not worked it out, but that sounds extremely unlikely. So this is quite worrisome, but there might also be a particular way of looking at it, that escapes the problem, that I'm just not seeing. Chris Pressey (talk) 12:14, 1 December 2012 (UTC)

Some definitions to help talk about this: a group where every element is its own inverse is the same as one where every element has order 2. (i.e. you only need to put together 2 copies of an element to get back to the identity element.) Such groups are sometimes called "Boolean groups" (though this nomenclature is apparently not so ubiquitous as to make it onto Wikipedia.) We can also say that the [infinite] group of Revaver2pi programs is finitely generated from the [finite] group of Revaver2pi operations.

So, a question. If a generating group is Boolean, is the group generated from it necessarily Boolean as well? This may be what I'm missing: Just because every Revaver2pi operation is its own inverse might not mean that every Revaver2pi program is its own inverse. Chris Pressey (talk) 16:17, 1 December 2012 (UTC)

OK, that was pretty sloppy. The generating set doesn't have to be a group at all, it's just a set. Just because, for each x in the generating set, the corresponding element x¹ in the group is its own inverse, doesn't mean that every element in the group has to be its own inverse. So, this setup doesn't imply abelian, ignore me. Chris Pressey (talk) 16:39, 1 December 2012 (UTC)

No, only each line is its own inverse, and a program is inverse of what it is when the order of lines is made backward. --Zzo38 (talk) 20:21, 4 December 2012 (UTC)