Minimal Experiments for Input-Independent Machines
Bruce H. Barnes, John M. Fitzgerald · Journal of the ACM · 1967
If, in a sequential machine, the output upon application of an input character depends only upon the current state of the machine and not upon the input character, the machine is called input-independent. Two states, p and q, of an input-independent machine are compatible if and only if the output strings from the machine starting in initial state, p , are the same as the output strings from the machine with initial state, q , for all input strings to the machine in both states. The minimal length of tape which tests compatibility of states in an input-independent sequential machine with n states is ( n 2 - 2 n )/4 + 1 if n is even, and ( n 2 - 2 n + 1)/4 if n is odd. There are machines with incompatible states such that no tapes of length less than the given bounds will detect the incompatibility.