Before revision:  In particular, we show that  having access to one extra binary degree of freedom (doubling the  number of states) is sufficient to carry out any P  . Our results provide a novel type of bound on the physical resources needed to perform information processing---the size of a system's  state space.
After revision:  In particular, we show that having access to one extra binary degree of freedom (doubling the number of states) is sufficient to carry out any P . Our results also imply that for certain P that can be implemented without hidden states, having additional states available permits an implementation that generates less heat. These results can be seen as uncovering and investigating a novel type of bound on the physical resources needed to perform information processing---the size of a system's state space.