skipper

Member • Feb 14, 2010

## Hypercubic computers

You may have heard of the

The design was apparently motivated by the structural properties of Rubik's cubes, since these also have a hypercubical property. To see this, you need to understand a little abstract algebra and to assume that the permutation puzzles are all examples of computational devices--you either scramble some kind of codeword and then unscramble it, or you spend a lot of time looping around, trying to find the algorithm that will get closer to a "resolved word". The encoding properties are fairly obvious.

Anyway, it comes down to characterizing what an operator is. An operator is an action on a subgroup of the elements in the configured puzzle (it has been constructed, say from a kitset of black plastic components and colored stickers so it has a symmetry, which is the algebra of "color" per face--you want to arrange these colors so that any face is congruent mod colors).

Anyways, obviously a single operator isn't very interesting--it can only rotate around in a circle (actually it quarters the surface of an open disk), so more than two of these in an algorithm presumably is "more interesting". Actually you generally use the set of operators two at a time, because you constantly think ahead to the next move, the current move is a "preparation" that you want, for the second operator to act on.

So the 2-generator (2g) subgroup which includes all algorithms composed of two operators is the successor of the subgroup of singletons, acting one-at-a-time, and not alternating (boring as).

With two "letters" from the full set {URFDLB} you can compose the following symmetric "forms" that are in fact, functional lists which traverse the positions/orientations of the cube (a Cayley graph), hopefully in a deterministic way that leads to "understanding", and the development of a set of personal algorithms--these don't even need a name, you store them away without "thinking" about what they are, only what they do in terms of shifting colors around, what contrasts with what, etc.

The symmetric forms of sets of two letters are, selecting say, the U and R operators from the full set: UR, and U'R. The first is equivalent to RU, and the second to UR' (up to isomorphism). That is to say, the first and second "rewrite" of each algorithm will have the same cycle order--it will repeat the same number of times to return to where it started. All algorithms have a finite cycle length (unless they are an infinite string of randomly selected elements). All algorithms with a finite length, and a sequence of operations (with inverses and double-moves) which doesn't change during an iteration, will have a finite number of cycles "built-in".

(Note that selecting a pair of operators that act on opposite faces, for the Pocket Cube means the same thing as only using one operator, because there is no middle-layer in between, and opposites commute fully).

The order of the algorithm UR, is 105 cycles; the order of U'R, is 63 cycles.

THe difference is 42, divide this in half and distribute it: 7(12 + 3), 7(12 -3) gives the symmetry. In fact cycling either of these (I use Cube Explorer, which is a bit faster than manually cycling a physical cube) using iteration counts like 7, 5, and multiples, investigates the inner structure of both. If you combine them, you have several ways to do this: URU'R, U'R'UR' (which has the same order), URUR', etc. In fact futzing with the inverses of each letter in various combinations also reveals something about the group's action (this is a subgroup, and so not all of the elements are permuted, there are two of these the 2-generator subgroup leaves alone, in the Pocket Cube).

You discover that the order of URU'R is 5, and this changes when you change the location of the prime symbol around (or add extra primes to signify to the program that you want it to execute an inverse operation). If you iterate URU'R 5 times, it leaves the cube unchanged (but each step individually permutes elements). If you change the 5 to a 4 or a 6, the iteration has order 5.

In other words, an algorithm with the general form: XYX'Y has order 5, even if you iterate it a different number of times. This means the algorithms corresponding to the above formulation (a class) will always divide any number of iterations by 5--even a very large number. So if you type a large iteration count into Cube Explorer, it will cycle 5 times, unless the number is a multiple of 5, in which case it will have order 1.

You also get cycles of order 2,3, and 7, by alternating the primes through the word (braiding or weaving something through the letters--this is actually known as a

So playing around with plastic puzzles, thinking about what "black" actually is, in reference to color, and investigating the cycle order of various personally tuned algorithms, is definitely doing computational science. Now you have an excuse...

The trick with characterizing the numbers of permutations, cycle order, and so on, is formulating a general recurrence relation. Here the domain of linear fractional transformations, the Mobius group, Dirichlet and Cauchy integrals over integer groups and ring modules, yada yada... is quite helpful, and if you are going on to do computer science, graphics or just general combinatorial stuff, these are quite helpful formulas.

But regardless of the established formalisms, you do all this abstract math anyway--you don't call it a Mobius function, or a transformation of elements of a G-module or G-structure, but all the same you develop a set of computational theories and algorithms, as you learn more about solving, and/or preparing patterns on, the Rubik's group of symmetric objects.

And yes, they are also in the same domain as OO, because you can abstract them into an OO-language basis, like GAP or Mathematica. In these the elements of the cube are in a list which is permuted, traversed, reversed, reduced, etc, and uses pivoting relations (as the actual puzzles pivot elements around fixed centers).

Eliminating pivots is a good way to get to a solution, which means using fewer characters from the full set {URBDFL}, and restricting operations, so you can preserve the part you have solved already (the

So don't be a slouch, get into permuting, people!

*Connection Machine*. This was/is a massively parallel system in which the processors communicate with each other via a comms net, which has a hypercube structure.The design was apparently motivated by the structural properties of Rubik's cubes, since these also have a hypercubical property. To see this, you need to understand a little abstract algebra and to assume that the permutation puzzles are all examples of computational devices--you either scramble some kind of codeword and then unscramble it, or you spend a lot of time looping around, trying to find the algorithm that will get closer to a "resolved word". The encoding properties are fairly obvious.

Anyway, it comes down to characterizing what an operator is. An operator is an action on a subgroup of the elements in the configured puzzle (it has been constructed, say from a kitset of black plastic components and colored stickers so it has a symmetry, which is the algebra of "color" per face--you want to arrange these colors so that any face is congruent mod colors).

Anyways, obviously a single operator isn't very interesting--it can only rotate around in a circle (actually it quarters the surface of an open disk), so more than two of these in an algorithm presumably is "more interesting". Actually you generally use the set of operators two at a time, because you constantly think ahead to the next move, the current move is a "preparation" that you want, for the second operator to act on.

So the 2-generator (2g) subgroup which includes all algorithms composed of two operators is the successor of the subgroup of singletons, acting one-at-a-time, and not alternating (boring as).

With two "letters" from the full set {URFDLB} you can compose the following symmetric "forms" that are in fact, functional lists which traverse the positions/orientations of the cube (a Cayley graph), hopefully in a deterministic way that leads to "understanding", and the development of a set of personal algorithms--these don't even need a name, you store them away without "thinking" about what they are, only what they do in terms of shifting colors around, what contrasts with what, etc.

The symmetric forms of sets of two letters are, selecting say, the U and R operators from the full set: UR, and U'R. The first is equivalent to RU, and the second to UR' (up to isomorphism). That is to say, the first and second "rewrite" of each algorithm will have the same cycle order--it will repeat the same number of times to return to where it started. All algorithms have a finite cycle length (unless they are an infinite string of randomly selected elements). All algorithms with a finite length, and a sequence of operations (with inverses and double-moves) which doesn't change during an iteration, will have a finite number of cycles "built-in".

(Note that selecting a pair of operators that act on opposite faces, for the Pocket Cube means the same thing as only using one operator, because there is no middle-layer in between, and opposites commute fully).

The order of the algorithm UR, is 105 cycles; the order of U'R, is 63 cycles.

THe difference is 42, divide this in half and distribute it: 7(12 + 3), 7(12 -3) gives the symmetry. In fact cycling either of these (I use Cube Explorer, which is a bit faster than manually cycling a physical cube) using iteration counts like 7, 5, and multiples, investigates the inner structure of both. If you combine them, you have several ways to do this: URU'R, U'R'UR' (which has the same order), URUR', etc. In fact futzing with the inverses of each letter in various combinations also reveals something about the group's action (this is a subgroup, and so not all of the elements are permuted, there are two of these the 2-generator subgroup leaves alone, in the Pocket Cube).

You discover that the order of URU'R is 5, and this changes when you change the location of the prime symbol around (or add extra primes to signify to the program that you want it to execute an inverse operation). If you iterate URU'R 5 times, it leaves the cube unchanged (but each step individually permutes elements). If you change the 5 to a 4 or a 6, the iteration has order 5.

In other words, an algorithm with the general form: XYX'Y has order 5, even if you iterate it a different number of times. This means the algorithms corresponding to the above formulation (a class) will always divide any number of iterations by 5--even a very large number. So if you type a large iteration count into Cube Explorer, it will cycle 5 times, unless the number is a multiple of 5, in which case it will have order 1.

You also get cycles of order 2,3, and 7, by alternating the primes through the word (braiding or weaving something through the letters--this is actually known as a

*braid group*, all the algorithms you can put together have this property).So playing around with plastic puzzles, thinking about what "black" actually is, in reference to color, and investigating the cycle order of various personally tuned algorithms, is definitely doing computational science. Now you have an excuse...

The trick with characterizing the numbers of permutations, cycle order, and so on, is formulating a general recurrence relation. Here the domain of linear fractional transformations, the Mobius group, Dirichlet and Cauchy integrals over integer groups and ring modules, yada yada... is quite helpful, and if you are going on to do computer science, graphics or just general combinatorial stuff, these are quite helpful formulas.

But regardless of the established formalisms, you do all this abstract math anyway--you don't call it a Mobius function, or a transformation of elements of a G-module or G-structure, but all the same you develop a set of computational theories and algorithms, as you learn more about solving, and/or preparing patterns on, the Rubik's group of symmetric objects.

And yes, they are also in the same domain as OO, because you can abstract them into an OO-language basis, like GAP or Mathematica. In these the elements of the cube are in a list which is permuted, traversed, reversed, reduced, etc, and uses pivoting relations (as the actual puzzles pivot elements around fixed centers).

Eliminating pivots is a good way to get to a solution, which means using fewer characters from the full set {URBDFL}, and restricting operations, so you can preserve the part you have solved already (the

*initial segment problem*).So don't be a slouch, get into permuting, people!