Get a Rubik’s Cube playing robotic arm, and ask it to flip a shuffled Rubik’s Cube randomly until it’s solved. How many years will it take until it’s solved? It’s some finite time, right? Millions of year? Billions of years?
Get a chicken and give it a Rubik’s Cube and ask it to solve it. I don’t think it will perform better than our random robot above.
I just think that randomness is a useful benchmark for performance on accomplishing tasks.
In Bogosort, the lower bound for random version is unbounded which is O(inf). You can even turn the Rubiks Cube problem into a sorting problem of finding path from starting position to solved position, involving a series of moves. I’m not sure if there are more than one set of shortest path solution to each scenario.
Oh, I’m not making the argument that randomly permuting the Rubik’s Cube will always solve it in a finite time, but that it might. I think it has a better chance of solving it than the chicken. The chicken might get lucky and knock the Rubik’s Cube off the edge of a cliff and it might rotate by accident, but other than that, the chicken isn’t going to do much work on solving it in the first place. Meanwhile, randomly permuting might solve it (or might not solve it in the worst case). I just think that random permutations have a higher chance of solving it than the chicken, but I can’t formally prove that.
How?
We can demonstrate this wth a test.
Get a Rubik’s Cube playing robotic arm, and ask it to flip a shuffled Rubik’s Cube randomly until it’s solved. How many years will it take until it’s solved? It’s some finite time, right? Millions of year? Billions of years?
Get a chicken and give it a Rubik’s Cube and ask it to solve it. I don’t think it will perform better than our random robot above.
I just think that randomness is a useful benchmark for performance on accomplishing tasks.
In Bogosort, the lower bound for random version is unbounded which is O(inf). You can even turn the Rubiks Cube problem into a sorting problem of finding path from starting position to solved position, involving a series of moves. I’m not sure if there are more than one set of shortest path solution to each scenario.
Oh, I’m not making the argument that randomly permuting the Rubik’s Cube will always solve it in a finite time, but that it might. I think it has a better chance of solving it than the chicken. The chicken might get lucky and knock the Rubik’s Cube off the edge of a cliff and it might rotate by accident, but other than that, the chicken isn’t going to do much work on solving it in the first place. Meanwhile, randomly permuting might solve it (or might not solve it in the worst case). I just think that random permutations have a higher chance of solving it than the chicken, but I can’t formally prove that.