Simultaneous control of many MEMS microrobots through a common, global, control signal is one of the grand unsolved challenges of microrobotics. At present, most mobile, aqueous, or aerial microrobots, are actuated and maneuvered using global externally supplied fields. The differentiation of the microrobot motion within a larger swarm is achieved through differences in their design that lead to different responses to these global fields. Such differentiation imposes a limit on the number of independently controllable microrobots due to the finite number of significant different levels (e.g. voltages) of these applied fields (or signals). In this paper, we present a new paradigm for control of large numbers of MEMS microrobots through a global control signal by introducing a mechanism call physical finite state machines (PFSM). PFSM can causes a change in the motion of the robot based on a temporal sequence in the global control and power delivery signal. We show that a PFSM can be implemented using stress-engineered MEMS microrobots, and show that the previously presented sub-linear control voltage bandwidth of O/n is a direct consequence of the application of an on-board two-state PFSM. We further show that the PFSM concept can be extended to on-board multistate FSM, and can, in theory further reduce the control voltage bandwith to O(c), a constant bound.