  We introduce the notion of universal memcomputing machines (UMMs): a class of
brain-inspired general-purpose computing machines based on systems with memory,
whereby processing and storing of information occur on the same physical
location. We analytically prove that the memory properties of UMMs endow them
with universal computing power - they are Turing-complete -, intrinsic
parallelism, functional polymorphism, and information overhead, namely their
collective states can support exponential data compression directly in memory.
We also demonstrate that a UMM has the same computational power as a
non-deterministic Turing machine, namely it can solve NP--complete problems in
polynomial time. However, by virtue of its information overhead, a UMM needs
only an amount of memory cells (memprocessors) that grows polynomially with the
problem size. As an example we provide the polynomial-time solution of the
subset-sum problem and a simple hardware implementation of the same. Even
though these results do not prove the statement NP=P within the Turing
paradigm, the practical realization of these UMMs would represent a paradigm
shift from present von Neumann architectures bringing us closer to brain-like
neural computation.
