On a measure of complexity for stochastic sequential machines

The need for a measure different from the number of states in analyzing stochastic sequential machines is pointed out. Using the decomposition previously demonstrated in association with actual physical realization of stochastic sequential machines4, a particular measure of complexity C(M) for a given machine M is introduced. The computational aspect of C(M) is discussed and an example exhibiting two state-equivalent machines M1 and M2 with #{S1} ≫ #{S2} (#{Si} ≡ number of states of machine Mi i=1, 2) but C(M1) ≪ C(M2) is given. Areas for future research are pointed out.