On the Universality of Memcomputing Machines
arXiv:1712.08702 · doi:10.1109/TNNLS.2018.2872676
Abstract
Universal memcomputing machines (UMMs) [IEEE Trans. Neural Netw. Learn. Syst. 26, 2702 (2015)] represent a novel computational model in which memory (time non-locality) 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, using set theory and cardinality arguments, we compare them with 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 method presented here provides a general framework in which to describe the relation between UMMs and any other type of computational model.
arXiv comment10 pages, 2 figures
References in corpus (12)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- 14-qubit entanglement: creation and coherence
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- 10-qubit entanglement and parallel logic operations with a superconducting circuit
- Memcomputing: a computing paradigm to store and process information on the same physical platform
- Universal Memcomputing Machines
- Memcomputing: Leveraging memory and physics to compute efficiently
- Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
- Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
- Benchmarking Quantum Hardware for Training of Fully Visible Boltzmann Machines
- MemComputing Integer Linear Programming