An Improvement on a Theorem of E. F. Moore
Gregory J. Chaitin · IEEE Transactions on Electronic Computers · 1965
A necessary and sufficient condition for the existence of an autonomous clock in a sequential machine M is found to be the existence of a nontrivial input-independent partition on the set of internal states of M, no matter whether M is completely specified or incompletely specified. Two different techniques are given for generating the smallest input-independent partition πI, from which all other input-independent partitions can be obtained. One is suitable for a sequential machine whose state behavior is specified in the form of a flow table, while the other is convenient for a sequential machine whose state behavior is specified in the form of a connection matrix. Both techniques are efficient, and give all possible assignments to the redundant conditions of an incompletely specified sequential machine to reach the same nontrival input-independent partition, and hence the same autonomous clock.