July 6, 2015 report
Researchers build first working memcomputer prototype
(Tech Xplore)—A combined team of researchers from the University of California and Politecnico di Torino in Italy has built, for the first time, a working memory-crunching computer (memcomputer) prototype. It is capable, the team reports in their paper published in the journal Science Advances, of solving the NP-complete version of the subset sum problem.
The idea for a memcomputer has been around for nearly half a century, but until now it has remained mostly theoretical. The problem has been that while the idea is really straightforward and easy to understand, the implementation has been troublesome due to a wide variety of variables. At its most basic level, a memcomputer is a computer that solves problems by crunching numbers and storing results simultaneously, rather than as completely separate processes, as is done with all modern computing machines. In that respect, it should work much more like the human brain. It has been in trying to figure out how to do that in a machine that has kept scientists from building such computers. If they could, it is believed that such machines would be capable of running some applications that are now impossible, and perhaps allow for the creation of devices that would dwarf the capabilities of those we have now, e.g. smart phones that communicate with us as naturally as other humans.
To create their prototype, the researchers had to come up with a completely new computer design, one based on what the team calls memprocessors—their prototype has six of them. The memprocessors have the ability to change their own properties—one of which is electrical resistance—depending on things such as how much energy is passing through. That allows the processors to store information in a new way, even as the processor continues processing. To prove that it can do actual work, the prototype is able to solve the NP-complete version of the subset sum problem—where given a set of numbers, is there a subset with at least one number, whose sum is zero?
The prototype proves that the memcomputer idea is sound, the team claims, though it suffers from noise, preventing it from being scaled up. The researchers suggest that improvements will likely lead to dedicated machines capable of doing one thing really good, and as such, likely will not appear in smartphones any time soon.
More information: Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states, Science Advances 03 Jul 2015: Vol. 1, no. 6, e1500031. DOI: 10.1126/sciadv.1500031
Abstract
Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It was recently proven mathematically that memcomputing machines have the same computational power of nondeterministic Turing machines. Therefore, they can solve NP-complete problems in polynomial time and, using the appropriate architecture, with resources that only grow polynomially with the input size. The reason for this computational power stems from properties inspired by the brain and shared by any universal memcomputing machine, in particular intrinsic parallelism and information overhead, namely, the capability of compressing information in the collective state of the memprocessor network. We show an experimental demonstration of an actual memcomputing architecture that solves the NP-complete version of the subset sum problem in only one step and is composed of a number of memprocessors that scales linearly with the size of the problem. We have fabricated this architecture using standard microelectronic technology so that it can be easily realized in any laboratory setting. Although the particular machine presented here is eventually limited by noise—and will thus require error-correcting codes to scale to an arbitrary number of memprocessors—it represents the first proof of concept of a machine capable of working with the collective state of interacting memory cells, unlike the present-day single-state machines built using the von Neumann architecture.
© 2015 Tech Xplore
