• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

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

Billabob

Member
Joined
Jul 12, 2018
Messages
100
There are 7401196841564901869874093974498574336000000000 permutations of the 4x4x4 cube so no, a quadrillion moves is not enough.
 

Julio974

Member
Joined
Oct 17, 2018
Messages
146
Location
France
WCA
2018ROHA01
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
Joined
Dec 24, 2015
Messages
1,575
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
Joined
Oct 17, 2018
Messages
146
Location
France
WCA
2018ROHA01
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
Joined
Dec 21, 2013
Messages
160
WCA
2013BOTZ01
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
Joined
Jan 4, 2018
Messages
381
WCA
2016TUDO02
YouTube
PapaSmurf Cubes
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
Joined
Dec 13, 2015
Messages
765
Location
New York
3^^^3 is 3 tetrated three times, in which means it is gargantuan compared to 3^^3.
 

Want to hide this ad and support the community?
Top