Anurag Ajay, Seungwook Han, et al.
NeurIPS 2023
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. © 1967, ACM. All rights reserved.
Anurag Ajay, Seungwook Han, et al.
NeurIPS 2023
Guojing Cong, David A. Bader
Journal of Parallel and Distributed Computing
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Ryan Johnson, Ippokratis Pandis
CIDR 2013