Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines

ABSTRACT

Any sequential machine M represents a function fM from input sequences to output symbols. A function f is representable if some finite-state sequential machine represents it. The function fM is called an n-th order approximation to a given function f if fM is equal to f for all input sequences of length less than or equal to n. It is proved that, for an arbitrary nonrepresentable function f, there are infinitely many n such that any sequential machine representing an nth order approximation to f has more than n/2 + 1 states. An analogous result is obtained for two-way sequential machines and, using these and related results, lower bounds are obtained for two-way sequential machines and, using these and related results, lower bounds are obtained on the amount of work tape required online and offline Turing machines that compute nonrepresentable functions.

REFERENCES

• 1: RABIN, M. 0., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 8, 2 (April 1959), 114-125.
• 2: SHEPHERDSON, J. C. The reduction of two-way automata to one-way automata, iBM J. Res. Develop. 3, 2 (April 1959), 198-220.
• 3: STEARNS, R. E., HAWrMANm, J., AND LEWIS, P. M., II. Hierarchies of memory limited computations. Proc. Sixth Annual Syrup. Switching Circuit Theory and Logical Design, Ann Arbor, Mich., 1965, pp. 179-190.
• 4: MOORE, E. F. Gedanken-experiments on sequential machines. In Shannon, C. E., and McCarthy, J. (Eds.), Automata Studies Ann. Math. Studies No. 341, Princeton U. Press, Princeton, N. J., 1956, pp. 129-153.
• 5: Konig, D. Theorie der Endlichen und Unendlichen Graphen. Chelsea Publishing Co., New York, 1950.
• 6: R0SENBERG, A.L. On n-tape finite-state acceptors. Proc. Fifth Annual Symp. Switching Circuit Theory and Logical Design, Princeton, N. J., 1964, pp. 76-81.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Measurement, Performance, Theory, Verification