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.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1109/TNNLS.2018.2872676 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Self-averaging of digital memcomputing machines.
Phys Rev E
September 2023
Department of Physics, University of California San Diego, La Jolla, California 92093, USA.
Digital memcomputing machines (DMMs) are a new class of computing machines that employ nonquantum dynamical systems with memory to solve combinatorial optimization problems. Here, we show that the time to solution (TTS) of DMMs follows an inverse Gaussian distribution, with the TTS self-averaging with increasing problem size, irrespective of the problem they solve. We provide both an analytical understanding of this phenomenon and numerical evidence by solving instances of the 3-SAT (satisfiability) problem.
View Article and Find Full Text PDFGlobal minimization via classical tunneling assisted by collective force field formation.
Sci Adv
December 2021
MemComputing Inc., San Diego, CA 92121, USA.
Simple elements interacting in networks can give rise to intricate emergent behaviors. Examples such as synchronization and phase transitions often apply in many contexts, as many different systems may reduce to the same effective model. Here, we demonstrate such a behavior in a model inspired by memristors.
View Article and Find Full Text PDFMode-assisted joint training of deep Boltzmann machines.
Sci Rep
September 2021
Department of Physics, University of California, San Diego, La Jolla, CA, 92093, USA.
The deep extension of the restricted Boltzmann machine (RBM), known as the deep Boltzmann machine (DBM), is an expressive family of machine learning models which can serve as compact representations of complex probability distributions. However, jointly training DBMs in the unsupervised setting has proven to be a formidable task. A recent technique we have proposed, called mode-assisted training, has shown great success in improving the unsupervised training of RBMs.
View Article and Find Full Text PDFDirected percolation and numerical stability of simulations of digital memcomputing machines.
Chaos
June 2021
Department of Physics, University of California, San Diego, California 92093, USA.
Digital memcomputing machines (DMMs) are a novel, non-Turing class of machines designed to solve combinatorial optimization problems. They can be physically realized with continuous-time, non-quantum dynamical systems with memory (time non-locality), whose ordinary differential equations (ODEs) can be numerically integrated on modern computers. Solutions of many hard problems have been reported by numerically integrating the ODEs of DMMs, showing substantial advantages over state-of-the-art solvers.
View Article and Find Full Text PDFEfficient solution of Boolean satisfiability problems with digital memcomputing.
Sci Rep
November 2020
Department of Physics, University of California, San Diego, La Jolla, CA, 92093, USA.
Article Synopsis
- Boolean satisfiability (SAT) is a significant problem in various fields and involves determining if a Boolean formula can be satisfied; it typically requires exponentially increasing time to solve difficult instances.
- A new digital memcomputing machine shows promise in efficiently solving hard SAT instances that usually need exponential time using its memory-assisted approach and integration of non-linear differential equations.
- This research highlights the machine's ability to solve SAT problems in continuous time without chaos or excessive energy, suggesting potential advancements in physics-inspired computing and applications.
Want AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!