Looping or Repeating Algorithms?

[rjohnson_8ball]

Yep, all algorithms repeated enough times will return to its original position.
If it didn't, then that [would] mean the rubik's cube has infinite positions

False.

In order to confirm the bold statement, you would need to repeat an infinite number of times -- an impossible task. So the sentence cannot make sense in that respect. Is this the answer to this Stefan Quiz? If so, I think it is stretching things a bit.

 

[Muesli]

What Stefan is saying is that, given that the cube has an algorithm that DOESN'T return it to the original state given enough iterations, that wouldn't necessarily mean that there are an infinite number of states of the cube. It could, for example, come to cycle between 3 states, where none of the three are the original state of the cube.
Correct me if I'm wrong, Stefan, but I believe that's what you're talking about.

*snaps fingers* I get it!

 

[rjohnson_8ball]

What Stefan is saying is that, given that the cube has an algorithm that DOESN'T return it to the original state given enough iterations, that wouldn't necessarily mean that there are an infinite number of states of the cube. It could, for example, come to cycle between 3 states, where none of the three are the original state of the cube.
Correct me if I'm wrong, Stefan, but I believe that's what you're talking about.

*snaps fingers* I get it!

But that cannot happen with a 3x3 cube. You cannot get into a cycle by coming from a state that is not in that cycle. That would imply 2 different states would lead into the cycle. So, if you begin in a solved state, then that solved state will remain part of the cycle.

 

[Stefan]

Yup, hawkmp4 correctly described the problem, and rjohnson_8ball almost fixed it.

 

[rjohnson_8ball]

Yup, hawkmp4 correctly described the problem, and rjohnson_8ball almost fixed it.

Why "almost"? Would I need to prove that an algorithm applied to 2 different states cannot produce the same resulting state?

 

[TMOY]

Well it's easy to fix.
Let's call S our original state, and A our algorithm. Since the number of states of the cubes is finite, there exists integers p<q and a state T such that when applying A either p times or q times on the cube starting with state S, we'll get to state T (let's write A^p.S=A^q.S=T). But then, if A' is the inverse sequence of A, we also have A'^p.T=S, hence A'^p.A^q.S=S. Since A'^p.A^q=A^(q-p), it means that the cube actually returns to its original state after q-p iterations, and since q-p is a positive integer, this finishes the proof.

 

[Stefan]

Yup, hawkmp4 correctly described the problem, and rjohnson_8ball almost fixed it.

Why "almost"? Would I need to prove that an algorithm applied to 2 different states cannot produce the same resulting state?

Not necessarily prove, but at least state. Previously you only went down to "2 different states would lead into the cycle" which I deem insufficient.

 

[Stefan]

Nice proof by TMOY, although I do prefer the illustrative one...

 

[hawkmp4]

Yeah, I don't have the maths knowledge to prove it yet. The key was forgetting the assumption (Which is true, but here we're supposing that it's not true) that an algorithm enters a closed loop.

 

[AndyRoo789]

I sort of understand, but I don't see how by repeating an algorithm, the cube could cycle between different states, none of which is the original state.
I mean, what's an algorithm that does that? O.O

 

[Stefan]

I mean, what's an algorithm that does that? O.O

None, at least for the 3x3x3 and similar puzzles. I think the Atomic Chaos might have some.

 

[Tim Major]

Try R U R' U'

 

[AndyRoo789]

Ohok, I get it. Let me fix my statement..

Yep, all algorithms repeated enough times will return to its original position.
If you were to get a NEW position everytime, that would mean it has infinite positions.

 

[qqwref]

Stefan: I don't have a problem with what AndyRoo789 said, because for the 3x3x3 every algorithm does

There are only two ways that an algorithm repeated over and over on a finitely complex puzzle cannot return to solved: either an infinitely repeating cycle which does not contain solved (call this an orbit) occurs, or at some point we reach a position that the algorithm cannot be performed from. If an orbit is possible on any sequential movement puzzle, there has to be some point in which the same sequence of moves can be applied to two different positions and have the same result. If moves are invertible (i.e. whenever you do a move, you can do another move to return to the position before the first move took place) then this can be rephrased as saying that, starting from one position, we can apply the same sequence and get either of two different positions at the end. This is impossible if the puzzle is deterministic, by which I mean that applying a given move to a given position will always return the same result.

So in fact every sequential movement puzzle that:
- is finitely complex (that is, does not have an infinite number of valid positions),
- allows any valid move to be performed from any valid position,
- only has invertible moves, and
- is deterministic
satisfies the condition that all algorithms have a finite positive order (by which I mean that, starting from solved, applying the algorithm some finite positive number of times will bring the puzzle back to solved). Fortunately the vast majority of puzzles we care about (for instance every 'regular' twisty puzzle and every cuboid) fall under these criteria, so this condition almost always holds.

 

[Stefan]

Yep, all algorithms repeated enough times will return to its original position.
If you were to get a NEW position everytime, that would mean it has infinite positions.

Doesn't help at all, cause now you need to argue why it should visit a new position every time.

 

[Stefan]

I don't have a problem with what AndyRoo789 said, because for the 3x3x3 every algorithm does

When writing a proof, just because something happens to be true doesn't mean you don't need to mention it.

Plus in general, algs-return-to-start even is wrong, and in our case of puzzles where it's correct, you just demonstrated with your elaborate post that it's not at all obvious/trivial. Thanks for that post, btw. That's what I've been roughly thinking for a while but I never thought it through and put it in words.

Atomic Chaos violates the "invertible" condition, that's why I think there are algs for it that don't return to start. Think-a-Dot is another interesting one, it does violate the "invertible" condition as well but I believe does have the algs-return-to-start property (I'm not entirely sure, though... someone wants to prove it?).

 

[Stefan]

Ugh. Two trivial counter-examples for Atomic Chaos:

Algorithm 1: "Turn it upside down"
If you start with let's say the long tubes matched and each containing exactly one ball, this alg will never return to that.

Algorithm 2: "Turn the top"
This will never return if you start with any balls in the top half.

 

[AndyRoo789]

Yep, all algorithms repeated enough times will return to its original position.
If you were to get a NEW position everytime, that would mean it has infinite positions.

Doesn't help at all, cause now you need to argue why it should visit a new position every time.

I'm not sure if this was the kinda answer you wanted, but whatever.


If you were repeating an algorithm and getting a new position everytime, it obviously has infinite positions.
But if you were repeating an algorithm and eventually got back to the original state, or start cycling between positions you've already encountered then it doesn't have infinite positions.

Like this...

If you were repeating an alg and you always encountered a new position, it would look like this...

Original state
NEW
NEW
NEW
NEW
NEW
NEW
NEW x infinite

But if you were repeating an alg and eventually came back to the original position, it would looks like this...

Original state
State A
State B
State C
State D
Original state
State A
State B
State C
State D
And it would keep repeating in the same order. (It doesn't take 5 times for everything, this is just an example)

 

[qqwref]

When writing a proof, just because something happens to be true doesn't mean you don't need to mention it.

Plus in general, algs-return-to-start even is wrong, and in our case of puzzles where it's correct, you just demonstrated with your elaborate post that it's not at all obvious/trivial. Thanks for that post, btw. That's what I've been roughly thinking for a while but I never thought it through and put it in words.

It's true - it isn't obvious or trivial at all. However, if you assume he was only talking about 3x3 algs (or even NxN algs), his post was in fact correct You're welcome for the post; when I saw this topic I thought I'd like to think about the the matter a bit more closely, because it did seem like it might be more complicated than I first thought.

By the way, Think-a-Dot actually doesn't violate the invertible condition, in the extended sense that the "inverse" of a single move can be a sequence. (The length of an inverse doesn't affect the validity of the proof because we still end up with the same sequence from the same position having to yield two different results.) The three possible moves each have order 8 (this can be verified by hand) so applying a move 7 times is the inverse of applying it once. Since the extended invertibility condition holds, the puzzle does indeed have the algs-return-to-start property.

 

[Stefan]

But if you were repeating an algorithm and eventually got back to the original state, or start cycling between positions you've already encountered then it doesn't have infinite positions.

You mean the path created by the algorithm. The puzzle could have infinite positions.

And if you don't have determinism, then even the path can have infinitely many positions despite getting back to the original state:

Original state
NEW
Original state
NEW
NEW
NEW
NEW
NEW
NEW x infinite

If you were repeating an alg and you always encountered a new position, it would look like this...

But if you were repeating an alg and eventually came back to the original position, it would looks like this...

Yeah. So? What about the crucial third case? If you want to argue that there are no black swans, stop showing me white swans.