On the Universality of Memcomputing Machines.

Abstract

Universal memcomputing machines (UMMs) represent a novel computational model in which memory (time nonlocality) accomplishes both tasks of storing and processing of information. UMMs have been shown to be Turing-complete, namely, they can simulate any Turing machine. In this paper, we first introduce a novel set theory approach to compare different computational models and use it to recover the previous results on Turing-completeness of UMMs. We then relate UMMs directly to liquid-state machines (or "reservoir-computing") and quantum machines ("quantum computing"). We show that UMMs can simulate both types of machines, hence they are both "liquid-" or "reservoir-complete" and "quantum-complete." Of course, these statements pertain only to the type of problems these machines can solve and not to the amount of resources required for such simulations. Nonetheless, the set-theoretic method presented here provides a general framework which describes the relationship between any computational models.