There is a question someone (I'm hazy as to who) told me years ago. I found it fascinating for a time, but then I forgot about it, and I'm out of touch with any subsequent developments. Can anyone better identify the problem or fill in the history, and say whether it's still unsolved? It's a challenging question if I've gotten it right. Here it is:


Suppose you have some kind of machine with two buttons, evidently designed by people with poor instinct for UI. The machine has many states in which the buttons do different things.
Here are the assumptions:


1. There is no periodic quotient of the state space: no way to label states by an n-cycle so that both buttons advance the label by 1 mod n.
2. It is not reversible: there are situations when two states merge into one.
3. It's ergodic: you can get from any state to any other state by some sequence of buttons.


Now suppose its dinky little LCD is faded or broken, so you can't actually tell what the state it's in. Is there necessarily a universal reset code, a sequence that will get you to a known state no matter where you start?
(Formally, this is a finite state automaton, or an action of the free 2-generator semigroup on a finite set, and asks whether some element acts as a constant map).



Is there a reset sequence?
I believe you are referring to the [Road coloring theorem](http://en.wikipedia.org/wiki/Road_coloring_problem). It was solved [in this preprint](http://arxiv.org/abs/0709.0099).


