A characterization of the power of vector machines

ABSTRACT

Random access machines (RAMs) are usually defined to have registers that hold integers. While this captures in part the structure of a commercial computer, it overlooks an implementation-dependent feature of most binary oriented machines, namely their ability to operate bit by bit on the bit vectors used to represent integers. Typical operations are bit-wise Boolean operations (and, or, not, etc.) and shifts by an amount specified in some register. These operations are ideal for certain problems, such as dealing with sets represented as bit vectors, some parsing algorithms [4], propositional calculus theorem proving, and analysis of sorting networks. A RAM so implemented we shall call a vector machine.

REFERENCES

• 1: Aho, A., J. Hopcroft and J. Ullman. 1968. Time and tape complexity of pushdown automaton languages. Information and Control 13, 186-206.
• 2: Stephen A. Cook, An observation on time-storage trade off, Proceedings of the fifth annual ACM symposium on Theory of computing, p.29-33, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804032]
• 3: Savitch, W.J. 1970. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4, 177-192.
• 4: Younger, D. 1967. Recognition and parsing of context-free languages in time n3. Information and Control 10, 2, 189-208.

INDEX TERMS

Primary 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)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Theory