Every finite sequential machine is linearly realizable

摘要

We prove that, using the definitions of realization of one sequential machine by another which appear to be most widely accepted today, every finite sequential machine is linearly realizable over any field of infinite characteristic and even over some fields of finite characteristic. This will give us, as corollaries, answers to two open questions posed in an earlier publication. We shall show that our result is the strongest we can hope for, putting various additional restrictions on the definition of linear realizability would result in the existence of not linearly realizable finite sequential machines.