That's true, clean app state gets you far. And that's something I'm going to add to Bombadil once it gets an ability to run many tests (broad exploration, reruns, shrinking), i.e. something in the spec where you can supply reset hooks, maybe just bash commands.

Regarding state machines: yeah, it can often become an as-complex mirror of the system your testing, if the system has a large complicated surface. If on the other hand the API is simple and encapsulates a lot of complexity (like Ousterhout's "Deep Modules") state machine specs and model-based testing make more sense. Testing a key-value store is a great example of this.

If you're curious about it, here's a very detailed spec for TodoMVC in Bombadil: https://github.com/owickstrom/bombadil-playground/blob/maste... It's still work-in-progress but pretty close to the original Quickstrom-flavored spec.