--- In [email protected], "Gilles Roux" <[EMAIL
PROTECTED]> wrote:
>
>
> A very technical post is rare and nice.
> If there's a way to make it accessible to people with finite
> knowledge, it would be bonus.
>
> Gilles.
I'm not sure if I can do that completely but maybe I can describe some of the
ideas and
flesh things out a bit more.
An order on a set S is a relation R such that for any distinct s,t,u in R
not(sRs) (irreflexive condition)
if sRt and tRu then sRu (transitive condition).
(e.g. <)
(This is a strict order; for a weak order the conditions are sRs (reflexive, if
sRt and tRs then
s=t (symmetric) and if SRt and tRu then sRu (transitive). e.g. <=, but we only
consider
strict orders here.)
For instance, in the game of rock, paper, scissors. We can define a relation B
(beats) such
that paperBrock, rockBscissors, scissorsBpaper.
This is not an order. It is irreflexive (we don't have things like paper
Bpaper) but not
transitive - whilst paperB rok and rockBscissors, we don't have paperBscissors.
The order is total (or linear) if for any s,t either sRt or s=t or tRs. (i.e.
you can compare any
two elements). The usual order on the integers is a total order.
The order is a well-order if it is a total order and any non-empty subset T of
S has a least
element - that is an element m of T such that for each t in T either mRt or
m=t. (This
element is then unique by the conditions above.)
An ordinal is a particular type of well-ordered set (well-ordered by
membership) and any
well-ordered set is (order-)isomorphic to an ordinal.
For instance, any subset of the natural numbers is well-ordered and so is the
entire set of
natural numbers but the set of integers is not well-ordered (it has no least
element).
The empty set is an ordinal (with the empty relation being the order) and is
commonly
called 0.
If an ordinal has a maximum element it is a successor ordinal - otherwise it is
a limit
ordinal. Any ordinal looks like alpha+n where alpha is a limit ordinal and n is
a finite
ordinal.
The set of natural numbers is a limit ordinal (the first limit ordinal except
0).
w={0,1,2,3,...}
but there are other subsequent ordinals e.g.
w+1={0,1,2,3,...,w}
and w+w={0,1,2,3,...,w,w+1,w+2,...}=w*2 etc.
And there are still larger ones like w_1 which is far bigger.
Ordinals have curious properties. w+1 is distinct from w (it has a last
element) but 1+w is
actually the same ordinal. Putting 1 element in front of a list of type w,
doesn't change the
type (they are order-isomorphic) - e.g. {-1,0,1,2,...} is clearly the same type
as {0,1,2,...}
(just map k to k+1).
Similarly w*2 is bigger than w but 2*w is the same as w.
In {a_{0,0},a_{0,1},a_{1,0},a_{1,1},...} (which is w copies of 2
({a_{i,0},a_{i,1}})) can be
mapped to w by taking a_{i,0} to 2i and a_{i,1} to 2i+1 and this is an
order-isomorphism.
It is this property that effectively allows us to take an order-type for 1
face-centre and put
all 6 faces into the same type (as long as such type is a limit and this can
always be
arranged by putting some finite stuff at the start).
You basically use {a_{0,0},a_{0,1},...,a_{0,5},a_{1,0},...} to transfer one to
the other (and this
puts each centre coordinate into blocks of 6 (so you have the same coordinate
for each
centre in turn). Similarly n*alpha=alpha for any finite n>0 (n=1,2,3,...).
Anyway, for any ordinal alpha at least as big as w, the reverse order alpha* is
not a well-
order (because you get a subset {...,3,2,1,0} with no least element).
So it will turn out that your centres have strips of type
alpha+n (+1)+(alpha+n)* for some limit alpha (because I effectively made an
assumption
right at the start that I wasn't going to consider anything more complicated.
The +1 would be the case of an odd cube.
(Essentially, the logic here is that because you can rotate the face by a half
turn the end of
strip must be the reverse order of the start. I'm only looking at getting half
way via an
ordinal so I must have alpha+n(+1)+(alpha+n)*=alpha+n(+1)+n+alpha* (since
(beta+gamma)*=gamma*+beta* and n*=n).
Including the edges the whole face has strips of type 1+alpha+n(+1)+n+alpha*+1.
Similrly the same type must run both vertically and horizontally because you
can do
quarter turns too.
Thus I can break a centre into pieces:
alpha*alpha n*alpha (1*alpha) n*alpha (alpha*)*alpha
alpha*n n*n (1*n) n*n (alpha*)*n
(alpha*1) (n*1) (1*1) (n*1) (alpha*)*1
alpha*n n*n (1*n) n*n (alpha*)*n
alpha*(alpha*) n*(alpha*) (1*(alpha*)) n*(alpha*) (alpha*)*(alpha*)
And going across all 6 centres we can put these into types like
6*(alpha*alpha) 6*(n*alpha) (6*(1*alpha)) 6*(n*alpha) 6*((alpha*)*alpha)
etc.
As indicated earlier n*alpha=alpha so 6*(n*alpha)=6*alpha=alpha.
Clearly, we can run reverse type on the alpha* to type 6*((alpha*)*alpha) in
type
6*((alpha)*alpha). (This is effectively coming in from the corner.)
Less obviously, we can type alpha*alpha in type alpha and we can even do it in
a canonical
(methodical etc.) way, independent of alpha.
So effectively then 6*((alpha)*alpha) can be typed in type 6*alpha=alpha.
So we get a finite load of chunks that can be typed in type alpha or in a
finite type (like
n*n). Put the finite bunch first to get N+k alpha=alpha.
(We can also do this methodically - putting them in in a particular order -
after all, we only
have finitely many chunks.)
So we get to type all the centres in type alpha. We can also splice things
together (the 4
things that are effectively alpha*alpha etc. to ensure that orbits of 24
centres all come in
one bunch). (An orbit being just the set of positions a particular piece can
occupy. If you
include orientation this is actually of size 24 for every piece - 8*3 for
corners 12*2 for
centre edges, 24*1 for other edges, 24*1 for non-central centres, 6*4 for
centre centres.)
The corners can be typed in type 8; there are only 8 corners.
If the cube is odd, the central edges can be typed in type 12. So the two of
these can be
typed in type 20 (finite). This is going to be put at the start of the order.
The non-central edges can be typed in type 24*n+12*alpha+12*alpha* which is
easily
convertible into type 24*alpha=alpha.
Each orbit (of 24 non-central edges) comes together as a clump.
Since 20+2*alpha=alpha, we can easily put the entire cube into type alpha.
We need to do this carefully, to ensure that each orbit of edges comes before
all the centre
pieces running off from those edges. (But there are only finitely many edges
per orbit, so it
is not too difficult.)
In fact, one could run through this by transfinite induction on the (already
ordered in type
alpha) centres. At stage beta, if the appropriate orbit of edges hasn't been
put in the
order, put them in before centre beta. (This can be used to define the
well-ordering of the
edges!) (We can define the order to add the orbit using a lexicographic
ordering - there
are two edge positions per edge to add - two on the edge joining UFR to UFL
etc. - and
each lies nearest to one corner so we can order first by edge and then by
nearest corner.)
This, then effectively types the entire cube into type alpha (half a side
length, more or
less).
If the corner permutation is odd, start by using D (this will make that
permutation even -
but it will move some centres, edge pieces around - but it will always do so in
a fixed way
and, moreover, in a canonical way that it easy to
Find the first non-solved position (NB the corners and central edges are right
up front, but
of course, they might already be solved.)
In the case of corners, central edges, you can orient them in a finite number
of moves and
permute them with 3 cycles in a finite number of moves. (3-cycles, because we
made the
permutation even.)
For a non-solved corner/edge we just cycle the position in question, the
position holding
the piece in question and the least other remaining position. In this way we
can
methodically solve the corners and edges.
Then you simply use transfinite induction as follows.
If the cube is not yet solved, there is a least unsolved position (because we
have well-
ordered the positions in type alpha and so the set of unsolved positions is a
non-empty
subset of a well-ordered set and hence has a least element).
Given the next unsolved position, if it is a centre, we must already have
solved all the
edges that can be reached by running to the edge from the centre (in a slice)
plus all the
edges in the orbit of such (by way of setting up the order in that way). This
implies that
the orbit of the centre in question has at least 3 unsolved centres and we can
3-cycle the
unsolved centre in the position we want to solve, the centre that goes into
that position
and the least other unsolved centre.
Again this takes a finite number of moves.
If on the other hand it is an edge, then gain if possible use a 3-cycle
described in the
same way. Otherwise, there will be only two unsolved edges. In this case we
slice the
position in question - this disturbs 4 edges (including the one in question and
some
already solved ones) - in the direction that takes it to the lesser edge
position (for
definiteness). It also permutes several centres (who appear later in the
solving stage) doing
so in a canonical way (that makes it easier to remember where each has mapped
to).
In this event we go back and solve those edges in that orbit again, in order
(now using
only 3-cycles). At most this will take 2 3-cycles (we could be left with 1
3-cycle, a double
transposition or 1 5-cycle) and so again solving the edge (plus correcting any
prior
disturbed edges) takes only a finite number of moves. All these 3-cycles can be
done
similarly to a 5x5x5 and have definite upper lengths, and there are only a
finite number
(of equivalence classes) of algorithms we need, so each stage will take at most
M turns (for
some M). That means the entire solution can be effected in type M*alpha=alpha.
>
>
> --- In [email protected], GameOfDeath2
> <no_reply@> wrote:
> >
> > --- In [email protected], David Barr
> <david20708@> wrote:
> > >
> > > Can someone summarize this in English? :)
> >
> > It's an (ordinal length) algorithm to solve infinite cubes.
> >
> > >
> > > On 2/2/06, GameOfDeath2 <[EMAIL PROTECTED]> wrote:
> > > >
> > > > This post is rather technical in nature but if you do understand
> the technicalities the
> > > > details are not difficult. It deals with solving sizeable cubes
> in a canonical way. To
> > alert
> > > > you, this post is about infinite cubes. The scrambling is
> assumed to be a function
> > from
> > > > some ordinal into the slice space (including face turns and
> inner slices). In particular
> > the
> > > > scramble might not be finite (so it's not part of the group
> generated by the slices, in
> > > > general). The solution described will also often be infinite
> even if the scramble is not.
> > The
> > > > aim is to solve the cube in type alpha where the cube length is
> of type 1+alpha+n
> > (+1)
> > > > +n+alpha*+1.
> > >
> >
>
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/speedsolvingrubikscube/
<*> To unsubscribe from this group, send an email to:
[EMAIL PROTECTED]
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
