Service de Physique de l'Etat Condensé

I will discuss a novel computing paradigm we named memcomputing [1] inspired by the operation of our own brain which uses (passive) memory circuit elements or memelements [2] as the main tools of operation. I will first introduce the notion of universal memcomputing machines (UMMs) as a class of general-purpose computing machines based on systems with memory. We have shown [3] 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. It is the presence of collective states in UMMs that allows them to solve NP-complete problems in polynomial time using polynomial resources [3]. As an example I will show the polynomial-time solution of the subset-sum problem implemented in a simple hardware architecture that uses standard microelectronic components [4]. Even though we have not proved NP=P within the Turing paradigm, the practical implementation of these UMMs would represent a paradigm shift from present von Neumann architectures bringing us closer to brain-like neural computation [5].

[1] M. Di Ventra and Y.V. Pershin, Computing: the Parallel Approach, Nature Physics, 9, 200 (2013).

[2] M. Di Ventra, Y.V. Pershin, and L.O. Chua, Circuit Elements with Memory: Memristors, Memcapacitors, and Meminductors, Proc. IEEE, 97, 1717 (2009).

[3] F. L. Traversa and M. Di Ventra, Universal Memcomputing Machines, IEEE Transactions on Neural Networks and Learning Systems, 99 (2015), DOI: 10.1109/TNNLS.2015.2391182.

[4] F. L. Traversa, C. Ramella, F. Bonani,  and M. Di Ventra, Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states, arXiv:1411.4798

[5] F. L. Traversa, F. Bonani, Y.V. Pershin and M. Di Ventra, Dynamic Computing Random Access Memory, Nanotechnology 25, 285201 (2014).