Unscrambling the cube

Discussion in 'General Science & Technology' started by noodler, Nov 11, 2009.

Not open for further replies.
1. noodlerBannedBanned

Messages:
751
I think the claim that computation is part of the cube dynamics can go untested, fairly obviously you process something, MIT's cubing community and Singmaster's algorithmic basis pretty much sum up the details.

Of course, it depends on what category you apply, is it a virtual-register kind of device? Is it strictly monotonic (i.e. there is a linear progression of contexts and switches)?

Well never mind all that, Prolog to the rescue. This is strictly a symbolic language. there are only lists with elements in them which can be other lists, or atomic tokens. The most atomic element is the empty list.

Constructing a Prolog program means defining a list structure, and in general some list traversing functions that are recursive, so a list is partially traversed in any case by first traversing the list at the head (or parsing an atom), then the tail is traversed recursively so that list traversal is ordered by the list itself.

The Singmaster labelling scheme uses 6 Roman letters (you could use Chinese or French versions however, the symbols are merely convenient or heuristic), which are: BDFLRU in alphabetic order.

You need to create lists that order these pairwise so they correspond to opposite faces of a cube.
Then you need to create an ordered list of inverted symbols to represent the "reverse" operator set of symbols: U',D' etc.
Then you will need functions that traverse these lists and compose at least the 2-generator set of operations on adjacent pairs, the cross and anticross subgroups. These correspond to the antitwist and twist groups respectively.

You can twist a single corner cubie and return it to where it started (you transport it in two directions, i.e. it gets pitch + roll), with an anticross move like FR. The cross moves F'R or FR' "eliminate" twist.
In that case, you can use twist parity as a symbol which is written in a read-erase-write cycle.
The other function, which is ancillary, is the copy function.

Solutions to a scrambled code use these subgroups, to eliminate twists from the corner cubies and flips from the edge cubies. Twist and flip essentially close the parity function(al).

If you generate a 6x6 matrix from the ordered list (URFDLB) you get a diagonal of square moves (the squares group UU,RR, ...,BB), this is the "identity function" because it has the parity identity (P,-P) where the cross and anticross groups generate {+1,0,-1} in the corners group. Parity is {0,-1} in the edges group.

Suppose you have a job as an analyst at some company whose details, naturally, need not concern us (or you, for that matter). So your boss hands you the series listed (from the Wikipedia entry for the Pocket Cube, iteration #1, N = 2). He says he wants you to find out what you can about the two lists, the company has no idea what it actually is, it could be in Klingon, or it could be just the output and input response curves of some chemical or other kind of reaction.
The boss wants you to eliminate, if possible, all categories that the two lists can't be in.

You surmise initially that the shorter length curve (parameterized by f in the series) is an exhaust output of some kind from the system (generally speaking), and the longer length curve (parameterized by q in the series) is possibly an input response, since in general a system can have an exhaust cycle that leads an intake--in fact this is how heat engines deliver useful work.
If there is a work function, and if both cycles are 'exhaustive' and the longer one is a system response, so the extra length is some kind of relaxation (a rise time), so the system can input again, maybe, maybe not....

Or maybe the series is a code of some kind, amenable to algorithmic analysis and code-breaking. Alan Turing claimed that, in order to write any number in a finite number of places (numbers have numbers too, called places or digits), an integer for example, writing it as a decimal in a finite number of places is proving the number is real, and also computable.

So, the totals for both sequences are equal, but the subtotals aren't. Writing 3,674,160 as a decimal means writing it as 0.367416. You can do this "in base 10" on paper, but a binary logic computer has to use, well, binary. Number representation in binary electronic computers becomes part of a potential solution.

CS/IS has various methods for encoding integer and real numbers, in binary form. Complements are standard, fixed and floating point reps are often generated with machine instructions (it saves time). Turing's formula has two terms, the left one writes a preamble (the number of digits, n) and the right one is an infinite sum of terms: $(2C_r\; -\; 1)(\frac {2} {3})^r,\; r = [1,\infty)$.

You know that, for a symmetric code, there is a |G| for the generators, which is both the totals, or |G| = Tf = Tq = 3,674,160, for totals T. Perhaps the sequences have this symmetry. You assume that if this is true, there will be a set of rotors (like the Enigma design) that rewrite-after-read, with shifting (pitch, roll, yaw is available in 3-space), this is actually the encoding process).

So, suppose Cr is also related to T, the total, then 2Cr is = (Tf + Tq), under some function that generates the subtotals. Write a Prolog program that orders the subtotals, and finds the recurrence that does this according to Turing's formula (assume the preamble is the program itself, or rather n is the list length).

The program will need to declare functions that traverse, reverse, etc the sublist elements and these will become part of the functional list--the tail of the Prolog listing, usually).

Last edited: Feb 4, 2010

3. BlindmanValued Senior Member

Messages:
1,425
You do know that real numbers can not be accurately encoded into Binary, Decimal, or any base that allows manipulation without error. ie 1/3

And once again your posting formula without definitions..
Prolog would be that last language to use to solve such a problem (if i can work out what you actually want). You dont have a clue what your typing?

I am willing to discuss Cube problems but please be consistent.

The only reason i am posting to this thread is that you touched apon the problem of, can a computer compute the possible combinations of a cube via simulation of the mechanical properties.

5. noodlerBannedBanned

Messages:
751
If Prolog is the last language you would use for a solution, would you consider using GAP, or a similar language instead? Would Mathematica be a good or a useful choice?

If you had no choice, but were forced to write a program in machine code, which processor would you choose, or which instruction set?

P.S. I suppose someone who has programmed for as long as you have, must be aware that binary can't represent real numbers except approximately.
Perhaps you've also managed to work out that this "problem" has something to do with the way digital circuitry only deals with fixed voltages and currents, and so it's physically impossible to store analog values.
This conclusion is fairly inescapable, you have to make it if you also study electronics and digital circuitry - with fixed values of charge it is physically impossible to store analog values, because there are only so many number places and they can only be 0 or 1.

This is gob-smackingly obvious to anyone who does even a cursory analysis of digital computers.

But thanks for all the fish, eh...

7. BlindmanValued Senior Member

Messages:
1,425
Guess you did not read my post correctly.
Or 0,1,2 or 0-3, or base 10, hex, octal
C#
CMOS T800 parallel transputers.. Loved them in the early 1990's had and array of 16 T800's

8. noodlerBannedBanned

Messages:
751
I guess if I didn't read your post correctly, I should try again then.

Yes, actually I do know that real numbers can't be represented in base2, there will always be some numbers that have an approximate binary representation
And yet you have stated that C# is a language you would use in preference to Prolog.
I'd like to know what motivated this decision, why is C# a better choice, is list-based programming not really a good approach to analyzing the puzzles? Would you not use the list-based features of C# at all, in that case?

Which features of the C# language do you think are the most useful, regarding the problem of finding a recurrence?

I'm also curious about how you store a 3 or a 10 in a single bit which can physically only be 0 or 1?? Don't you need more than one bit, and isn't there a limit to the number of bits, which logically means you can't represent every number, only a subset?

Can't you prove, fairly easily, that because the number of bits is finite, then real numbers will be represented as approximations - to plus or minus 1 bit?
I have this vague recollection of doing something like that, but it was a while ago, maybe things have changed since 1 + 1 = 2.

9. BlindmanValued Senior Member

Messages:
1,425
Most modern versions of Prolog are implemented in C, or C++. C# a higher level language then the afore mentioned, but provides a lower level implementation of any Prolog solutions.

C# compiles into non CPU specific opp code, yet as with C and C++ after just in time compilation can represent very tight machine code.
eg
Code:
for(int i=0;i<10;i++){}
"i" will use a register, "10" will be a immediate value, i++ will encode into a single instruction and "i<10" will encode into two.

Prolog will run at least 10 times slower at best.

impossible.

10. BlindmanValued Senior Member

Messages:
1,425
opps if only 3 and 10 easy, 0 = 3 and 1 = 10, hard to do math with but still possible as long as its only 3 and 10 (base 10)

11. noodlerBannedBanned

Messages:
751
I'm sorry, I'm having difficulty with the relevance of anything you have posted.
Other than establish a few things that are basic computer science, you have contributed nothing that I can say is remotely interesting.

The problem is this: I want to find a recurrence. You want to talk about C#, but this is just one of dozens of computer languages that could be used - as I state, you can also use machine instructions. In fact the choice of a language is irrelevant to the problem except for providing a higher level of abstraction.

Please either address the problem, or think of something else to do.

12. BlindmanValued Senior Member

Messages:
1,425
Well then present the problem
After a full turn of any face.

13. noodlerBannedBanned

Messages:
751
When you state: "Well then present the problem", do you mean "present the problem you have already presented over again, for my benefit because I can't be bothered going back over this thread", or do you mean "you haven't presented any problem"?

If you mean either of these, then I have a problem with that.
This problem: "find the recurrence relation for the Pocket Cube", is the one I want a solution for, Whatever your problem is, I can't really help you with it.

14. BlindmanValued Senior Member

Messages:
1,425
I have presented the symmetry (recurrence) of the 2by2 cube.

Are you after a mechanical solution???

15. noodlerBannedBanned

Messages:
751
You have the recurrence relation for the 2x2x2?
Why don't you post it for us then, so we can all relax?

Do you KNOW what a recurrence relation is, or are you guessing?

16. BlindmanValued Senior Member

Messages:
1,425
You mean after X iterations that the state of a system is the same?

17. noodlerBannedBanned

Messages:
751
'yawn'....

'skritch'..., 'skritch'.

18. BlindmanValued Senior Member

Messages:
1,425
Or "recurrence relation" which has no relevance to the cube problem???

19. noodlerBannedBanned

Messages:
751
That's right. The cube is just a cube, don't let it bother you or anything.

Obviously you don't know what the problem is, by which I mean 1) the problem I am trying to address, bit by bit, in which there is no deadline, no contract waiting to be finished so I get paid, no penalty clauses, or anything.

I do this because I know it's been done already, and so it can be done, and so I can work it out (actually I'm a fair way down the track, there is a shitload of stuff I haven't posted here, or anywhere else and none of it is my intellectual property).

And 2):
I guarantee you can't prove that a Rubik's cube has a recurrence relation which is irrelevant to "the cube problem", which might be the problem.

20. BlindmanValued Senior Member

Messages:
1,425
But there are so many different sequences of moves, each with its on set of values (encoded in cube configurations).

Simplest 0,1,2,3: single face rotation. Id have to code an alternative 8, right and front 1/4 turns for a sequence. Short of the full set. There is no single recurrence relation.

21. noodlerBannedBanned

Messages:
751
Rubbish. There are three formulas for the 3x3x3 that, given n a number of full moves, return the number of positions that can be reached. These formulas are accurate up to some value for n, say.

If these recurrences are "working models" apart from the limits, there must be formulas for the smaller puzzle, this should be obvious because the smaller puzzle is part of the larger one.

(Now for some more coffee)

22. noodlerBannedBanned

Messages:
751
The key to this exercise appears to be the 2-ary functionality of the 2-generator group. This is characterized by selecting any two adjacent faces (which are pivots), or XY. Then assume a general swapping algorithm "swap(XY)" that changes the order of any 2-ary word, as long as the word is in the 2-generator set.

So the swap() function just determines the sense any word is read, and we select operators from the full set that correspond to two faces of a cube (which is blocked, or not sliced).

Then swap: XY -> YX is just exchanging the MSD for the LSD of the word "XY", by reading it right-to-left. If the word is "10" the swap function exchanges this for "01", etc.
In fact any dyad has its order changed, including the abstract functions/values "black" and "white", since black can be "0" and white "1", if the cube is all black, swapping white makes it all white, etc.

The other function needed as well as swap(), is one that inverts the direction any monad acts. That is if X is a monad, -X is its inverse. This is characterized in a standard (algorithmic) basis as X'.

With inversion and swapping (changing the order of a word, starting with dyads), you can now form higher functions that use the first two, to generate flip() and twist() functions of operators. These can be generalized to any two words A and B, where A is a word of length a, B a word of length b, etc.
A.B is a pivotal word, the pivot is the "dot", which acts like a decimal point in a real fraction.

Start with U, the "up face", and select a second face, which is one of the out-degrees (any face of a cube has degree-four), say L. Then with the swap() and invert() functions, you get the following algebra: swap(UL), swap(U(invert(L))) = swap(UL'), ... for a total of 8 dyads. Add the square() function that copies a monad s.t. square(U) = UU, etc.

The squares and swaps with inversion can now be used to investigate the 2-generator set of operations. This has order 29160, and it includes (by way of the swap(), square(), flip(), and twist() functors/algorithms), the cross and anticross subgroups. Twist is a function that acts on two elements, you can twist a single element in-place, in two moves. It takes three moves to flip an edge, and the flip() is not available (except as an abstract function) in the Pocket Cube configuration.

We note that square(U) = UU, and invert(UU) = (UU)', are symmetric, in that: square(invert(U)) = square(U') = invert(square(U)) = invert(UU). This is the intersection of the identity with the mechanical inversion [, the function apply(UU) = apply(U'U')] of a face group of elements wrt the face-degree.
square(U) is a function that proves UU is its own inverse, since UU = -(UU), or $U^2\; =\; -U^2\; =\; U^{-2}$

Last edited: Feb 8, 2010
23. noodlerBannedBanned

Messages:
751
Now, of course, if we swap the notion of "stickering" with the notion of coordinatizing, or synchronizing the algebra, we have a natural way to tensor the 2-generator subset as all 2x2 matrices that correspond to squares of XY with diagonals that correspond to the above identity--which is the pivot for all functions composed of the "fundamentals" swap(XY), and invert(X).

Then the matrix algebra that corresponds to such valid compositions should include the functions: flip(XY), and twist(XY), that change the parity of individual elements without changing their position.
"Naturally" the postions are changed, but also restored (positions, as variables are involuted, but homological to parity functions, since they transport elements in two directions around B(r) the ball which is closed under all rotations in 3-space, but not [closed to] swap(black,white), swap(XY), ...).

H_color is the algebraic identity, rotations are the geometric "functionality" of H. G is the set of closed rotations that yields |G| under H.

A and B are "simply" words, composed of extensions of the swap, invert, twist and flip [functorials] to the full group. The full group includes all algorithms that construct, slice, rotate, color, along with inversions, all elements, and there is an H_0 -> H_1 homology.

When (r) the radius of B transitions from r = 0, it cannot "go backwards" except arithmetically, and only if the swap function has exchanged "b" for "c", each [are] elements of H_color.

Conjecture: the functional space is logarithmic, with a spiral form which has a polar equation, this is what such a space looks like when color is used to plot an infinitely recursive function: