Universal Memcomputing Machines
Open accessThe DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Abstract
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 nondeterministic Turing machine, namely, it can solve nondeterministic polynomial (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 the present von Neumann architectures, bringing us closer to brain-like neural computation.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2005) · doi:10.1002/047174882x · Cited by 13,791
Strukov, D. B., Snider, G. S., Stewart, D. R., & Williams, R. S. (2008) · Nature · doi:10.1038/nature06932 · Cited by 11,828
Self-Organization and Associative Memory
Kohonen, T. (1989) · Springer Series in Information Sciences · doi:10.1007/978-3-642-88163-3 · Cited by 8,740
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Quantum Computation and Quantum Information: 10th Anniversary Edition
Nielsen, M. A., & Chuang, I. L. (2012) · doi:10.1017/cbo9780511976667 · Cited by 8,436
On computable numbers, with an application to the entscheidungsproblem
Turing, A. M. (1937) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-42.1.230 · Cited by 8,283
Nanoionics-based resistive switching memories
Waser, R., & Aono, M. (2007) · Nature Materials · doi:10.1038/nmat2023 · Cited by 4,923
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597
Maass, W., Natschläger, T., & Markram, H. (2002) · Neural Computation · doi:10.1162/089976602760407955 · Cited by 4,025 · cited 1×
“Very recently, a new computing paradigm, inspired by the operation of our own brain, has been proposed which is not based on the UTM concept, and which puts the whole burden of computation directly into the memory.”
Method‘Memristive’ switches enable ‘stateful’ logic operations via material implication
Borghetti, J., Snider, G. S., Kuekes, P. J., Yang, J. J., Stewart, D. R., & Williams, R. S. (2010) · Nature · doi:10.1038/nature08940 · Cited by 1,929 · cited 1×
“For instance, physical and statistical properties, [23]–[26] computing capability [27], [28], and more [29] have been studied for networks of memristors.”
BackgroundComputational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Circuit Elements With Memory: Memristors, Memcapacitors, and Meminductors
Di Ventra, M., Pershin, Y. V., & Chua, L. O. (2009) · Proceedings of the IEEE · doi:10.1109/jproc.2009.2021077 · Cited by 1,212 · cited 2×
“This particular architecture, we have called Dynamic Computing Random Access Memory (DCRAM) and expends a very small amount of energy per operation, is just an example of what can be accomplished with memelements.”
BackgroundFirst draft of a report on the EDVAC
von Neumann, J. (1993) · IEEE Annals of the History of Computing · doi:10.1109/85.238389 · Cited by 1,112 · cited 1×
“The practical realization of a UTM is commonly done using the von Neumann architecture [4], which apart from some inconsequential details, it can be viewed as a device that requires a central processing unit (CPU) that is physically separate from the memory (see figure 1, left panel).”
MethodMemory effects in complex materials and nanoscale systems
Pershin, Y. V., & Di Ventra, M. (2011) · Advances In Physics · doi:10.1080/00018732.2010.544961 · Cited by 823 · cited 2×
“For instance, physical and statistical properties, [23]–[26] computing capability [27], [28], and more [29] have been studied for networks of mem-ristors.”
BackgroundMethodSelf-citationA case of unusual autobiographical remembering
Parker, E. S., Cahill, L., & McGaugh, J. L. (2006) · Neurocase · doi:10.1080/13554790500473680 · Cited by 318 · cited 1×
“For example, a person affected by hyperthymesia is not able to erase his/her memory [44], [45], thus demonstrating the capability of our brain to store such a large quantity of information whose limits, currently, cannot even be estimated.”
BackgroundProgrammable Resistance Switching in Nanoscale Two-Terminal Devices
Jo, S. H., Kim, K.-H., & Lu, W. (2009) · Nano Letters · doi:10.1021/nl803669s · Cited by 302
On the physical properties of memristive, memcapacitive and meminductive systems
Di Ventra, M., & Pershin, Y. V. (2013) · Nanotechnology · doi:10.1088/0957-4484/24/25/255201 · Cited by 130 · cited 2×
“The whole concept of memcomputing can be realized in practice by utilizing physical properties of many materials and systems which show a certain degree of time non-locality (memory) in their response functions at particular frequencies and strengths of the inputs [14]–[16].”
Background
Cited by
Neuromorphic computing using non-volatile memory
Burr, G. W., Shelby, R. M., Sebastian, A., Kim, S., Kim, S., Sidler, S., Virwani, K., Ishii, M., Narayanan, P., Fumarola, A., et al. (2017) · Advances in Physics: X · doi:10.1080/23746149.2016.1259585 · Cited by 1,107
Ising machines as hardware solvers of combinatorial optimization problems
Mohseni, N., McMahon, P. L., & Byrnes, T. (2022) · Nature Reviews Physics · doi:10.1038/s42254-022-00440-8 · Cited by 543
Mixed-precision in-memory computing
Le Gallo, M., Sebastian, A., Mathis, R., Manica, M., Giefers, H., Tuma, T., Bekas, C., Curioni, A., & Eleftheriou, E. (2018) · Nature Electronics · doi:10.1038/s41928-018-0054-8 · Cited by 485
In-memory computing on a photonic platform
Ríos, C., Youngblood, N., Cheng, Z., Le Gallo, M., Pernice, W. H. P., Wright, C. D., Sebastian, A., & Bhaskaran, H. (2019) · Science Advances · doi:10.1126/sciadv.aau5759 · Cited by 391
In‐Sensor Computing: Materials, Devices, and Integration Technologies
Wan, T., Shao, B., Ma, S., Zhou, Y., Li, Q., & Chai, Y. (2023) · Advanced Materials · doi:10.1002/adma.202203830 · Cited by 327
Metadata
- Authors
- Traversa, F. L., & Di Ventra, M.
- Venue
- IEEE Transactions on Neural Networks and Learning Systems
- Published
- 2015-11
- Volume
- 26
- Issue
- 11
- Pages
- 2702-2715
- ISSN
- 2162-237X (ISSN-L)
- 2162-2388
- OpenAlex
- W2038569833
- Cited by
- 153
- References
- 18
- FWCI
- 8.66
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.