3 ms·
This gets greatly compounded when you have a lot of states. As an easy example, consider the "state machine" for a rubik's cube. All told, this isn't insurmou
by taeric 6y ago
This gets greatly compounded when you have a lot of states. As an easy example, consider the "state machine" for a rubik's cube. All told, this isn't insurmountable, but you are almost certainly not going to write down all of the allowed states with all of the possible transitions.
Which is not to say you can't make a program to reason about what the allowed states are. I started a probably bad attempt at that a while back at https://taeric.github.io/cube-permutations-1.html https://taeric.github.io/cube-permutations-1.html. (And, I just noticed the mathjax included on that page isn't loading. Almost certainly my fault... :( )
- fabian2k 6y agoState charts avoid that problem to some extent, you don't explode the number of state like in a simple finite state machine. But that's a point where you certainly want to use a library.
- taeric 6y agoRight. My assertion would then be that many things are modeled on a ton of possible states. Granted. In context of this story, I'm in complete agreement with you.
- Jtsummers 6y agoMight be worth reposting that link, it's an interesting topic on its own. Rubik's cube transformations as permutations is one of those "obvious" things that had never occurred to me before, plus the neat interactive demo at the bottom.
- taeric 6y agoWould love to see feedback on it. I posted back when I wrote it. I think it was mostly lost to the noise.
- madpata 6y agoI think your answer boils down to "pick the right tool for the job". Of course state machines are cumbersome for systems with loads of different states and transitions. But state machines are really useful when designing safety-critical systemsfor aeronautical, automotive or train components, especially if one uses timed automata for modelling. It's possible to either generate the code from the model or use the model to automatically generate a complete test suite for the modelled system. Very useful for verification purposes.
- taeric 6y agoCompletely agree. I did not mean my post as an argument against state machines.
- sdenton4 6y agoThe permutations you're getting are Cayley's Theorem in action: https://en.wikipedia.org/wiki/Cayley%27s_theorem https://en.wikipedia.org/wiki/Cayley%27s_theorem Basically, there's a finite group that acts on the Rubik's cube, and every finite group is a subgroup of a permutation group if you squint at it right. (what's a 'finite group action?' The 'group' is a set of composable and reversible "moves." The 'action' means that the group moves are effectively state transitions acting on a set of states, and that the action is nice and associative: g(hs) = (gh)s. And 'finite' just says that there's only so many states possible...) Really nice demo, by the way! Very fun to see the squares go flying.
- taeric 6y agoI'll have to read up on Cayley's Theorem. Thanks for the link! Glad others found the squares flying as much fun to watch as I did. :D