Publication
Journal of Computer and System Sciences
Paper

A characterization of the power of vector machines

View publication

Abstract

A new formal model of register machines is described. Registers contain bit vectorswhich are manipulated using bitwise Boolean operations and shifts. Our main results relate the language recognition power of such vector machines to that of Turing machines. A class of vector machines is exhibited for which time on a vector machine supplies, to within a polynomial, just as much power as space on a Turing machine. Moreover, this is true regardless of whether the machines are deterministic or non-deterministic. © 1976 Academic Press, Inc.

Date

01 Jan 1976

Publication

Journal of Computer and System Sciences

Authors

Topics

Share