Turing numbers and geometry

Here's some more stuff on the group of cube puzzles:

Stacking cubes together is where Erno Rubik started with his eventual design of an N[sup]3[/sup] object, which is cubical because it's a stack of smaller "cubes", assembled so that cubic symmetry is preserved.

Now restricting N to the numbers corresponding to the first two constructions - that appeared on shelves by the early '80s - so N = {2,3}, we see that N corresponds to the "stack depth" of a symmetrical stack, N high and N wide, so N deep. When the values 0 and 1 are included, by backwards induction we have a single symmetric object when N = 1, and none (the trivial step) when N = 0.

The table, up to N = 3, goes:

N | Edge sections | Face sections
0 | 0             | 0 
1 | 12            | 6
2 | 24            | 24
3 | 36            | 54

for N a sectioning number. The number of slices or divisions per edge, is N-1. There are "midsections" when N > 2, or inner slice-layers between outer slice-layers. The inner layers have fewer sections than the outer layers.

The M-number is a function of N as well. Continuing the table, up to the current real-time and real-world physical basis, and restricting N to be > 0:
[Ed: after some thought, I should correct this since the first 2 columns are "cubed" numbers, and the last column out by a factor of 3 in that case]

N | Edge sections | Face sections | Midsections
(0)| ( 0)         |( 0)           |( 0)
1 | 12            | 6             | 0
2 | 24            | 24            | 0
3 | 36            | 54            | 1x3
4 | 48            | 96            | 2x3
5 | 60            | 150           | 3x3
6 | 72            | 216           | 4x3
7 | 84            | 294           | 5x3

We see that N divides edges as N-1, and N-2 is the "M-number", when N-2 is zero or higher. The sections per-face are 6N[sup]2[/sup] numbers. These are the representative bases:
[IMG]

We know a single "unsectioned" cube is the intersection of three pairs of parallel planes, equidistant and perpendicular, pairwise. Each of six faces of a cube has a parallel face opposite. When N = 1, E the edge # is 12N and F the face # is 6N; this is the "naive algorithm".
If you have two identical cubes and want to stack them there's an asymmetry, because "stack" implies two faces are joined. The F-number for two distinct cubes is 2xF, but two faces vanish at conjunction so this becomes 2xF - 2, or 12 faces become 10 outer visible sections (faces) of the pair. Up to 3 cubes in a stack only 4 faces can be subtracted from F[sub]tot[/sub]. With 4 cubes you get a degree of freedom, because 3 cubes can be stacked two ways, so a 4th can subtract 4 faces or just 2 depending on if the 3-stack is "inline" or "angled". Stacking 4 cubes in a layer hides the most inner faces or sections.

Ok, so there's a sort-of algorithm here for constructing a stack of "cubes with hidden faces", so you get a "middle-layer" at some point, then these inner layers multiply linearly with N the section #. The inner layers correspond to edge-sections, since they are independent of any corner sections of the N-cubes. So the group of "edgies" shows up when N goes from 2 to 3. There is a permutation map for the above layouts of sections and divided edges, the Pocket Cube page on Wikipedia has this, and there's another table of the sets of permutations organized according to quarter and "full" moves, which I have (the coset table), the aim is to map the N and M numbers to this table, by finding an algorithmic correspondence.

Unfortunately this coset table is the only complete one for the cube groups. That is, it doesn't accommodate M > 0. However it is a map of the corners subgroup which all of the examples have; this group can be used as a divisor of the larger groups, with group theory and some category definitions.

Replies

skipper

What is a Turing number?
Well, Alan Turing picked up a sheet of paper one day and had a think about what it means to write a symbol down. He reasoned that the only way this made sense is if he, the writer, was also a reader.

In other words, you read symbols as you write them (or shortly afterward) to check you wrote the "right" one. He reasoned further that it is impossible to write anything meaningful (i.e containing "information") unless a finite set of symbols is used.

That is, although you can in principle build a machine that outputs an infinite series of unique symbols, you won't be able to use any of them to write a message, because messages are restricted by definition to finite alphabets. This insight lead to important developments in intelligence and code-breaking; WWII may well have had a very different outcome, in the Atlantic and North Sea in particular, if advances in the understanding of encoding and re-encoding (rewriting) messages hadn't been made at this time.
Turing's thesis and his supplementary paper on the "decision problem" essentially tell us that any formula that encodes a message leaves traces of itself behind, encoded necessarily in the syntax.

Anyways, Turing numbers are those which a machine, properly configured, can output in a finite number of places (steps). So that any encoding is also essentially the rewriting of a number that has a finite number of places, as a finite number of decimals after a "point". The equation on the last page of his supplementary paper says that no machine can "figure" any number unless there are a finite number of digits in the number.

Now the numbers in the cube groups, are numbers of slices, sections and permutations of them.

Each example (a basis of corner and edge sections) in the picture is presenting a permutation; the entire set of permutations for each N-cube is called a presentation map, notated |G|. G is the set of all "generators" in the groups. P is usually written P = , which means P is the presentation of (the space) of generators over the set of relations between subgroups and elements in G. An element of G is generally labeled X, which stands for a face (in Singmaster notn.).

Ok, so the extended set (up to N = 7) of symmetric groups of stacked cubies, starts when N goes from 1 to 2. For a cube with no slices (N = 1, M = 0) the number of permutations is the same as the number of symmetries of the cube; these correspond to the number of ways it can be rotated, or the number of possible views and color permutations per face (a fixed 6 color set). This number is 24 because:
there are 6 faces so 6 ways to view a single colored face, each face has 4 neighbor faces, so there are 6x4 ways to view 2 faces. There are 8 corners and 3 ways to view each so 8x3 views of 3 faces. Using either a face- or corner-metric is the same permutation order.

[When N = 2] there are 8! ways to permute the locations of each corner and 3[sup]7[/sup] ways to permute the corner rotations (7 corners rotate wrt a 1st corner). However, because each corner can be in any of the 24 symmetric "views", 8!3[sup]7[/sup] is divided by 24. Thus the true permutation number is 8!3[sup]7[/sup]/24 = 7!3[sup]6[/sup]. This is a "small" number which corresponds to the corner symmetry groups. When edges appear (N > 2) this number is a multiplicative term in |G|.

So 7!3[sup]6[/sup] will divide |G|. leaving a remainder which is the edge-symmetry group. Call the corners subgroup K, and the edges subgroup E; we have a K[sub]8[/sub] and a E[sub]24[/sub] when N = 2. Also |G| / |K| = 1 = I.

Ed: mistake here: When N = 3, M = 1, E = E[sub]36[/sub]. |G| is (8! x 3[sup]7[/sup] x 12! x 2[sup]12[/sup]), so |E| = (12! x 2[sup]12[/sup]) x 24 = (12! x 2[sup]15[/sup]) x 3
...
When N = 4, M = 2 and E is E[sub]48[/sub]. |G| becomes (8! x 3[sup]7[/sup] x 24![sup]2[/sup]) / (4![sup]6[/sup] x 24) = (|K| x 24![sup]2[/sup]) / 4![sup]6[/sup].

So when N = 4, |E| appears to be = 24![sup]2[/sup] / 4![sup]6[/sup].

...whew!

The rest:
N = 5, M = 3, |G| = (8! x 3[sup]7[/sup] x 24![sup]6[/sup]) / 4![sup]24[/sup] x 24 = |K|(24![sup]6[/sup]) / 4![sup]24[/sup].

When N = 6, M = 4 and |G| = (8! x 3^7 x 12! x 2[sup]10[/sup] x 24![sup]8[/sup]) / 4![sup]36[/sup]
= |K|( 24 x 12! x 2[sup]10[/sup] x 24![sup]8[/sup]) / 4![sup]36[/sup]
= |K|(3 x 12! x 2[sup]13[/sup] x 24![sup]8[/sup]) / 4![sup]36[/sup] = |K|(6 x 12! x 24![sup]8[/sup]) / 3![sup]6[/sup]4![sup]30[/sup]
then |E| = (12! x 24![sup]8[/sup]) / 3![sup]5[/sup]4![sup]30[/sup]

When N = 7, M = 5 and |G| = (8! x 3[sup]7[/sup] x 12! x 2[sup]10[/sup] x 24![sup]3[/sup]) / 4![sup]12[/sup]
= |K|(24 x 12! x 2[sup]10[/sup] x 24![sup]3[/sup]) / 4![sup]12[/sup] = |K|(12! x 24![sup]3[/sup]) / (3![sup]5[/sup] x 4![sup]6[/sup])

So when N = 7, |E| = (12! x 24![sup]3[/sup]) / (3![sup]5[/sup] x 4![sup]6[/sup])
skipper

There might be a problem or two with the above formulations; the reason 8!3[sup]7[/sup] is divided by 24 is that the 2-cube has no fixed pieces, like the 3-cube does.

K when its part of a N-cube when N > 2, can be oriented - the 3-cube has central facets which are not permuted or always have a fixed permutation. However the 3-cube is the only (odd-N) member that has oriented facets like this. If you de-sticker the centers the 3-cube's orientation is erased.
I need to modify the formulation to account for "fixed" colors, or restrict stickering somehow.

Perhaps I could de-sticker all the single-facet pieces that are "central" for any N? Then the N-cubes will have stickers on corners (K) and edges (E), but no centers: a void for the coloring function. You can also physically remove pieces, but destickering them achieves the same result algebraically and leaves the geometry unchanged.
(There's a mod for the 3-cube that removes the central frame and central facets, making it into a void-cube).
sarveshgupta

Seems very huge explanation will see it later
skipper

I'm trying to parameterize the space (of stacks of cubes).

Obviously the N[sup]3[/sup] geometric parameter, when N = 2 is the number of actual cubic volumes in the space, stacked symmetrically. This group K is a subgroup of all symmetric cubical stacks; characterize this as an interval (a,b) corresponding to a "start" and "end" value, notated: [sub]a[/sub]|G|[sub]b[/sub], for G (usually written in Gothic), the extended group of sliced symmetric cubes,

The edges group E appears when N = 3, but so do centers, so the centers group here is C[sub]2N[/sub]. Each extension, up to N = 7 is an odd or even number of central (single-sticker) pieces. Therefore there are 3 separate groups commuted, by the total space.

You can analyze these groups independently so there is a correspondence in each graph (where a graph is the total presentation) for each value of N. The initial construction or stacking is a permutation of these 3 groups.

Then, you construct an algebra (like Singmaster did) to map the groups to "operators". The algebra is constrained or restricted by the geometry and the "color values". The color function is parity (or "contrast").
skipper

Hmm. The title "Turing numbers and geometry" implies a connection between the two subjects. This connection is to the numbers in the geometry, the ones derived from N as above.
Although I've used letters like K and C for corners and centers, and E for edges, each subgroup is also a symmetric group S[sub]n[/sub].

The interval (a,b) is the boundary of G the full group of a N-cube; where there is an extended group "G" for all N. Bear in mind that the construction goes from 2 to 7 in ordinary Euclidean space with 3 dimensions, so time or "rotation" is a 4th.
There are, as some may know, versions of cube stacks in higher dimensions where hypercubes live; this (so far) is all "simple" geometry plus an algebra of permutation operators. The constructions in 3 dimensions are all obvious. simply-connected symmetries.
skipper

Now suppose I want to think about "heat and temperature". There is an obvious "work function" which is rotation of any face, X, where X is a member of the basic moves {U,R,F,D,L,B}. There are exactly 4 places, for any continuous rotation, where "corners meet corners".

This models a Carnot-cycle engine (as well as a kind of switch). The "work" is the length of the word that contains all the permutations, as repeated by any continuous cycle. So X, XX, XXX, ...., X[sup]n[/sup] words are "written" when a face is worked this way; since any rotation is reversible this models the reversible flow of "heat" through an engine.

A dW/dT formula is couched in terms of "steps T" and W is the set of all "words" that can be written, some of which have the same cycle-length but different word-length.
skipper

Ah, you see, any letter in the basic alphabet is a number in 4 places, as mentioned.

In fact, each "X" an element of {B,F,U,R,D,L} is a composition of four functions f[sub]1[/sub], f[sub]2[/sub], f[sub]3[/sub], f[sub]4[/sub].
If you assign the indices of each f[sub]i[/sub] to the "moves" needed to visit each of the "digital functions" you essentially write down a number.

The number's digits appear and vanish with each transition, => there is a transition function that takes each 4-dimensional number X to each digit or place in X.
This "one-letter" function has exactly 6 representatives, or "figures" from the set, selected one at a time; each letter is a functorial that writes and erases "digits" on an imaginary Turing tape.

The function f[sub]1234[/sub](z) is also known as a Mobius function; there is a Mobius "word" that takes edges to inversions of edge-parity and back, which is a 4-cycle that rotates a face X twice (i.e. through 720[sup]o[/sup]).

Now representing this transition, t, is easy: assume a Turing machine with a 4-cell tape width; the transition functions "visit" or read/write each cell, f[sub]i[/sub], i = {1,2,3,4}. Rotating a face X continuously is equivalent to a Turing machine reading and writing the same 4-cell of the tape - i.e. a loop. The current version reads an empty cell, writes a symbol which is the same symbol each time, erases it and moves to the next cell - (if you get tired, think about building a motor that will do this "automatically"; wait - someone did build a robot that solves Rubik's cubes !!)

Corollary: N is a divisor function(a number). It acts first on edges of a N-cube. The action divides edges and there is a need to categorize this.
Since the term "edge" is used, a fraction of an edge - divided evenly by N so all sections of an edge = distances are equal - let these be "edgeons"; the degree of a straight edge in Euclidean space, for a Platonic solid with faces, is always 2 because there is a dihedral angle between adjacent faces, by construction.

The edgeons subtend two sections of different (but adjacent) faces. Call the total an edgit (a kind of digit). An edgeon is positional - there are 12 edgits that can be in a given position, hence the "-on" ending. Each edge-digit has a position and an orientation, there are two orientations per position including the "home" position for each of these components. This is a product of the group of even integers, Z[sub]2[/sub] and the symmetry group S[sub]12[/sub].
The edgits encode the Mobius transformation of the faces group. Each face in the edgit-less 2-cube, in that case, permutes the same transformations in a "real imaginary" space; the edgits when N=2 are imaginary but there is a real "contrast remainder" between two k-bits ("cornits") which is the mathematical "integral" of imaginary e-bits.
skipper

There are a lot of memonics "buried" in these things; apart from building patterns and finding words that preserve them there is the interest in finding the shortest path (word) from any permutation.

The problem of God's algorithm is a recursive problem - because we "know" how to solve a cube which has been "scrambled" by a single move (even in the full set of 3 possible in the so-called face-turn metric or FTM), away from the "solved" state - normally labeled the identity by group theorists.

So there is a forward-recursive solution that will reach the extreme of the full graph as well as a backward-recursive solution (by induction) that will reach the identity. Starting at I, we want to know what I + f, or I + q means, where f is from the full set and q is from the 'singleton' set.

Here I wander off into the game of chess, and consider pieces that can only move one square, and that can move 1, 2 or 3 squares, etc. Since moves are allowed in "reverse' because for a single face, X[sup]3[/sup] = X[sup]-1[/sup], singleton moves are what a king makes, but the king is on a board with 4 squares. A bishop in one corner of such a board, can only move from one corner to the opposite and back, restricting the moves of the king, which is 'in the FTM' so can move diagonally as well as clockwise/anticlockwise around the board.

Next, you need to be able to get the king and/or bishop to another set of 4 squares - a different level; things get more complex because there are 4 of these, one along each edge.

You are reading an archived discussion.

Turing numbers and geometry

Replies

Related Posts

Remote assistance

Today's Featured Downloads: NTBACKUP.MSI

Innovative clamping\fixture technology (instead vacuum, magnet, ice).

Guides on writing a MATLAB software for Kalman filter

Wish to get in IITm for MS - I have 3+ years work experience