Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
- 1 July 1967
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 14 (3), 478-489
- https://doi.org/10.1145/321406.321410
Abstract
Any sequential machine M represents a function f M from input sequences to output symbols. A function f is representable if some finite-state sequential machine represents it. The function f M is called an n-th order approximation to a given function f if f M 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 n th 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.Keywords
This publication has 1 reference indexed in Scilit:
- On n-type finite state acceptorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1964