How long do you think the Devil's Algorithm will be for 4x4.

stormtrooper

Member
My personal inference is that it would be quadrillion moves long or even longer. My inference can be wrong.

Billabob

Member
There are 7401196841564901869874093974498574336000000000 permutations of the 4x4x4 cube so no, a quadrillion moves is not enough.

Julio974

Member
1st question: is is small than a googol?
2nd question: if not, is it smaller than a googolplex?
3rd question: if not, it is smaller than
?
4rd question: if not, is it smaller than Graham's Number?
5th question: it is smaller than SSCG(3)?
I'm just preparing for 5x5 and Megaminx at the same time, don't worry!

xyzzy

Member
2nd question: if not, is it smaller than a googolplex?
3rd question: if not, it is smaller than
?
4rd question: if not, is it smaller than Graham's Number?
5th question: it is smaller than SSCG(3)?
Roughly speaking, a googolplex is doubly-exponentially huge, 3^^^^3 involves tetration, Graham's number is in a class of its own, and SSCG(3) even further beyond that.

Graham's number and SSCG(k) both come from graph theory, and their mindboggling size comes from the fact that many advanced combinatoric results cannot be proven in Peano arithmetic, which "contains", among other things, the class of easily computable functions. (Very roughly speaking.) These results require more axioms to prove than just Peano arithmetic (e.g. the standard set theory axioms: ZFC), and consequently, the functions that come out of such results have to grow extremely quickly. (If they didn't, Peano arithmetic would've been able to handle them… roughly speaking. It might be possible that such functions don't grow quickly, but the fact that they don't grow quickly cannot be proven in PA; I can't think of any such example, however.)

In contrast, if you're just looking at something like the number of states on an n×n×n cube, that's only singly-exponentially large. You shouldn't even expect it to hit a googolplex for reasonable values of n, much less Graham's number or SSCG(3).

Julio974

Member
Roughly speaking, a googolplex is doubly-exponentially huge, 3^^^^3 involves tetration, Graham's number is in a class of its own, and SSCG(3) even further beyond that.

Graham's number and SSCG(k) both come from graph theory, and their mindboggling size comes from the fact that many advanced combinatoric results cannot be proven in Peano arithmetic, which "contains", among other things, the class of easily computable functions. (Very roughly speaking.) These results require more axioms to prove than just Peano arithmetic (e.g. the standard set theory axioms: ZFC), and consequently, the functions that come out of such results have to grow extremely quickly. (If they didn't, Peano arithmetic would've been able to handle them… roughly speaking. It might be possible that such functions don't grow quickly, but the fact that they don't grow quickly cannot be proven in PA; I can't think of any such example, however.)

In contrast, if you're just looking at something like the number of states on an n×n×n cube, that's only singly-exponentially large. You shouldn't even expect it to hit a googolplex for reasonable values of n, much less Graham's number or SSCG(3).
I'm already preparing for bigger cubes!
But you're right on that...

ichcubegerne

Member
In general I like the idea of finding an optimal solution for the devils alg on different cubes from the wca and proving that they are optimal^^

PapaSmurf

Member
What you can do is the devil's algorithm for every 2x2 state, but then within that nest an algorithm that with do the centres and wings, so if you work out the alg excluding corners, you can just do the 2x2 one, and within each turn do the centre/wing one. That would (probably) reach every state, although it probably won't be optimal.

Sion

Member
3^^^3 is 3 tetrated three times, in which means it is gargantuan compared to 3^^3.