Abstract
The purpose of this paper is to consider how memory requirements grow with the length of the input sequence recognized by a machine. In particular we develop lower bounds on such growth. Such bounds have been developed for a particular form of Turing machine,[1]. In this form of machine, the input is permanently stored on an input tape which may be read in either direction, but the memory used for storing the input is not included in the bound. We wish to consider a bound on all the memory used in a machine, considering the input as coming from outside the machine. The machine may or may not store individual input symbols. We define a machine In terms of states only, without specifying the nature of the form of memory in which these states are recorded, A machine, as defined here, may have an infinite number of states. A machine specification M will consist of a set of input symbols, I; a set of states, S (generally Infinite); a subset R of S of 'read' states such that if M is in a member of R, M will read the next input a 'read-next-state' function which for each state in R and each input in I, specifies a member of S as next state; a non-read-next-state' function which for each state In S but not in R specifies a member of S as next state; a member of S called the starting state; a subset of S of terminal states. An Input sequence I takes M from state a to state b if starting in a and applying the next state functions to the states and inputs of I in the expected way (similar to the way it is done with finite state machines) M will, after the last input of I ss read, be in state b. A sequence is recognized by M If it will take M from starting state s to a terminal state of M, in a way defined analogously to that for finite state machines. As when considering finite state machines we can use state diagrams in representing aspects of these generally-infinite state machines, we develop this state diagram or graph form of representation now in greater detail in preparation for the use we intend to make of it in developing the memory bound. In fact, the memory bound will be shown to be equivalent to a bound on the number of branches in certain graphs. Consider an Input sequence,I, of length k recognized by a machine M having l input symbols in such a way that M passes through n states in the process. The way in which this occurs can be represented by an appropriate state diagram i.e. by a directed graph U having: (1) N nodes, one designated the starting node, (s), one the terminal node (t) (2) At least k branches, with k of the branches labeled with input symbols (those branches from 'read' states) and the remaining branches unlabelled (those branches from 'non-read states. (3) Each node has either a single unlabelled branch (a Non-read-state) or no more than l labeled branches (Read state) emerging from it. Furthermore, U must have a path p from s to t traversing each and every branch In U once, such that writing the labels on the labeled branches in the order they occur in the path p yields the input sequence i.