PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal Memcomputing Machines

Fabio L. Traversa, Massimiliano Di Ventra

arXiv:1405.0931v2cs.NEcond-mat.mes-hallcs.ETcs.ITmath.IT

TL;DR

The paper asks how a general-purpose memcomputing machine relates to Turing machines and computational complexity. It defines UMMs as interacting memory processors and argues that their properties support polynomial-time solutions to NP-complete problems, while the result does not establish NP=P within the Turing paradigm.

  • Problem

    Separate CPU and memory require substantial data transfer, limiting computing time and energy, and parallel processing does not eliminate communication between processors and memory.

    Source: §I · p. 1

  • Method

    The paper defines UMMs as general-purpose machines of interacting memprocessors and analyzes their memory properties and subset-sum algorithms.

    Source: VON NEUMANN ARCHITECTURE MEMCOMPUTING… · p. 2, §VII · p. 9

  • Results

    UMMs are shown to be Turing-complete and to solve NP-complete problems in polynomial time, with subset-sum examples using either exponentially or linearly many memprocessors.

    Source: VON NEUMANN ARCHITECTURE MEMCOMPUTING… · p. 2, B. UMMs solve NP–complete problems in… · p. 7

  • Takeaways & Limitations

    The authors conclude that UMMs could offer a computing paradigm that addresses limitations of present platforms, including the von Neumann bottleneck and rising energy requirements, if realized in practice.

    Source: §VIII · p. 13

Abstract

from arXiv · show

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 non-deterministic Turing machine, namely it can solve 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 present von Neumann architectures bringing us closer to brain-like neural computation.

I. INTRODUCTION

The introduction frames data movement between separate CPU and memory as a time and energy bottleneck that parallel processors do not eliminate. It presents UMMs as general-purpose machines computing and storing information in interconnected memory, with memory properties supporting polynomial-time solutions to NP problems.

I. INTRODUCTION

  • Separate CPU and memory require substantial data transfer, limiting computation in time and energy; parallel processors still communicate extensively with memory.The paper identifies this transfer burden as the von Neumann bottleneck and an information-latency issue.Source: §I · p. 1
  • Existing alternatives are described as not fully resolving von Neumann limitations or offering substantial advantages over Turing machines.The introduction includes Harvard, pipelined, and liquid-state architectures among these alternatives.Source: §I · p. 1
  • Memcomputing places computation in memory, using memory response properties; its memory elements can support learning, adaptation, and self-organizing computation.The paper describes physical systems with time-nonlocal responses as potential realizations and notes work on memelements and memristor networks.Source: §I · p. 1

VON NEUMANN ARCHITECTURE MEMCOMPUTING ARCHITECTURE

  • Intrinsic parallelism means memprocessors operate collectively, while functional polymorphism lets input signals select functions without changing network topology.The control unit directs execution but does not need arithmetic or logic functions; data can reach it directly or through the memprocessors.Source: VON NEUMANN ARCHITECTURE MEMCOMPUTING… · p. 2, Figure 1 · p. 2
  • Information overhead is the ability of physically coupled memprocessors to store and compress more information than the same non-interacting cells.The paper states that a linear number of interconnected memprocessors can store and compress an exponentially growing amount of data.Source: VON NEUMANN ARCHITECTURE MEMCOMPUTING… · p. 2
  • UMMs are general-purpose machines of interacting memprocessors, defined broadly to include systems with memory responses, and are shown to be Turing-complete.The introduction also states that UMMs can solve NP problems in polynomial time and presents subset-sum algorithms, including one using linearly many memprocessors through information overhead.Source: VON NEUMANN ARCHITECTURE MEMCOMPUTING… · p. 2

II. UNIVERSAL TURING MACHINE

The section distinguishes the UTM as an abstract model for evaluating computation from physical systems. It then defines memprocessors and their networks through state, internal and connecting variables, and evolution operators.

II. UNIVERSAL TURING MACHINE

  • A UTM operates on a tape using a head, state register, and finite instruction table, with a transition function specifying state, symbol, and head movement.The formal description includes possible states, tape symbols, blank and input symbols, an initial state, and final states.Source: §II · p. 3
  • The UTM is an abstract mathematical object without explicit physical-system properties, used to determine an algorithm’s operation count as a function of input size.Variants including nondeterministic and parallel Turing machines are treated as equivalent in the types of problems they can solve, though execution times may differ.Source: §II · p. 3

III. MEMPROCESSORS

  • A memprocessor is defined by state x, internal variables y, connecting variables z, and an evolution operator σ.The definition is intended to link real memcomputing architectures with the formal UMM and is not limited to passive memory elements.Source: §III · p. 3
  • Connected memprocessors form a computational-memory network whose state collects individual states and whose connecting variables collect each processor’s connections.Two processors are connected when their connecting-variable sets intersect; an isolated processor has no dynamics under the stated condition.Source: §III · p. 3
  • The network’s connecting variables evolve through Ξ, with internal variables and external signals supplying stimuli; σ and Ξ may describe discrete or continuous evolution.The discrete interpretation includes artificial neural networks, while the continuous interpretation covers more general dynamical systems.Source: §III · p. 3

A. Memprocessors made by memelements

For memprocessors made from memelements, the paper uses constitutive input-output relations to connect a system’s internal state and response to its evolution over time.

A. Memprocessors made by memelements

  • Standard memelement equations describe a system using internal state variables and complementary constitutive input and output variables.The response is represented by a generalized function g, while f is a continuous vector function.Source: A. Memprocessors made by memelements · p. 4
  • The memelement’s connection variables are its external output and input, while its memprocessor state is the internal state xin.The paper treats the constitutive relation as a constraint that can be substituted into the state evolution equation.Source: A. Memprocessors made by memelements · p. 4
  • After defining x as xin(t) and x′ as xin(t + T), the state evolution over time T follows from the reduced relation.The connecting-variable evolution operator Ξ is defined by Kirchhoff’s laws and external generators that include signals s.Source: A. Memprocessors made by memelements · p. 4

B. Memprocessors made of generic electronic devices

The paper extends the memprocessor model to generic electronic devices and defines a UMM as a controlled network of such memory cells. Its transition functions encode parallelism and polymorphism in the network’s state evolution.

B. Memprocessors made of generic electronic devices

  • A memprocessor made from generic electronic devices is represented by a differential-algebraic equation system for circuit state variables.The derivation assumes an invertible reduced Jacobian, obtainable by eliminating variables through constraints when needed.Source: B. Memprocessors made of generic… · p. 4
  • The generic electronic-device model uses circuit evolution over time T, with Kirchhoff laws and external generators defining Ξ.The paper identifies DCRAM cells and the later hardware cells as examples of this type of memprocessor.Source: B. Memprocessors made of generic… · p. 4

IV. UNIVERSAL MEMCOMPUTING MACHINE

  • A UMM is an ideal bank of interconnected memory cells that performs digital or analog operations under a control unit’s direction.Connected memprocessors change internal states according to their initial states and the control signal, giving rise to parallelism and polymorphism.Source: §IV · p. 4

A. Formal definition

  • The formal UMM definition specifies memprocessor states, transition functions, pointer arrays, input states, and final states.The state set may be finite and digital or continuous or infinite-discrete and analog; each transition function reads selected memprocessors and writes outputs.Source: A. Formal definition · pp. 4–5
  • Unlike a UTM, a UMM’s transition functions can vary and act simultaneously on multiple memprocessors, while data and machine states share memprocessor states.This shared state representation is described as crucial to computation and data storage on the same physical platform.Source: A. Formal definition · p. 5
  • A UMM can retain intrinsic parallelism even when its control unit addresses only one memprocessor, because the network changes states at other selected locations.The paper also notes that a finite number of memprocessors can, in principle, have infinitely many continuous states.Source: A. Formal definition · p. 5

B. Proof of universality

The proof constructs a UMM that simulates a UTM by encoding its state and tape in memprocessor states and updating them according to the UTM transition rules. This establishes Turing-completeness, but not the reverse simulation needed to establish Turing-equivalence.

B. Proof of universality

  • The construction stores the UTM state in one memprocessor and tape symbols in the others, then applies the UTM transition rules and updates the tape-head pointer.The UMM's single transition function implements the simulation.Source: B. Proof of universality · p. 5
  • Actual implementations discretize the continuous state range, with attainable state density limited by the resolution of writing and reading operations.Source: B. Proof of universality · p. 5
  • A UMM simulates any Turing machine, establishing Turing-completeness but not showing that a UTM can simulate a UMM.The authors leave open whether the two models are equivalent.Source: B. Proof of universality · p. 5

V. PROPERTIES OF UMMS

UMMs use coupled memprocessors for network-wide computation and information storage, unlike conventional parallel architectures with a fixed or polynomial number of processing units. The paper argues that a UMM can solve problems represented by exponentially growing solution trees in polynomial time, using polynomially many memprocessors when information overhead is employed.

A. On the parallel computing of UMMs

MEMORY

  • Physical coupling lets a signal to one or a group of memprocessors induce computation across a larger group, potentially the entire network.One input signal can induce massively parallel computation.Source: MEMORY · p. 6

B. UMMs solve NP–complete problems in polynomial time

  • A UMM solves an NP-complete problem in time proportional to P(n), matching the computational power of an NTM in the paper's model.Each UMM transition advances one iteration of the solution tree.Source: B. UMMs solve NP–complete problems in… · p. 7
  • Information overhead lets a UMM encode groups of solution-tree nodes collectively, reducing the required memprocessors from an exponential count to a polynomial one.Without that overhead, the NTM-style exploration requires exponentially many processing units and tapes; the argument applies to problems represented by exponentially growing trees.Source: MEMORY · p. 6, B. UMMs solve NP–complete problems in… · p. 7

VI. INFORMATION OVERHEAD

The paper defines information overhead as a benefit of interacting memory cells: their collective state can store more information than the same cells acting independently. A series-connected example illustrates quadratic storage, while the authors note a practical limitation of the demonstrated reduction strategy.

VI. INFORMATION OVERHEAD

  • The authors describe the brain's information storage as collective behavior of interacting neurons, rather than storage proportional simply to neuron or synapse count.Source: §VI · p. 8

A. Quadratic Information Overhead

  • Connected memprocessors can store n(n −1)/2 messages, a quadratic number in the memprocessor count, by directly reading sums of stored numbers.Independent cells in the comparison store at most ⌊k/3⌋ messages.Source: A. Quadratic Information Overhead · p. 8, Figure 6 · p. 8
  • Information overhead is in-memory compression: interacting cells store more information than the same non-interacting cells, without requiring a CPU program to decompress it.The paper contrasts this with standard compression using memory plus a CPU program.Source: A. Quadratic Information Overhead · p. 8
  • The demonstrated hardware strategy reduces the number of memprocessors only polynomially, which the authors identify as a practical limitation.The example uses interconnected memristors and current measurement to read sums.Source: A. Quadratic Information Overhead · p. 8

B. Exponential Information Overhead

Interacting memprocessors can encode exponentially many subset-derived messages in their collective state. This information overhead arises from physical coupling and is distinct from computation, which changes memprocessor states.

B. Exponential Information Overhead

  • A memprocessor stores data in components of an internal state vector, and interconnected cells expose a readable global state.The cells are modeled as two-terminal polarized devices whose terminals interact differently.Source: B. Exponential Information Overhead · pp. 8–9
  • With n interconnected memprocessors, the global state can encode all 2^n possible messages formed from subsets of the input set.Each message combines a product over a subset with the subset's elements.Source: B. Exponential Information Overhead · p. 9
  • Physical coupling can compress more information than the same non-interacting memprocessors can store, including an exponential amount with a linear number of cells.The paper distinguishes this collective information overhead from computation: computation changes states, whereas overhead is associated with the global state of interacting cells.Source: B. Exponential Information Overhead · p. 9

VII. THE SUBSET-SUM PROBLEM

The section presents UMM algorithms for the subset-sum problem, then describes a DCRAM-inspired implementation whose operations combine data across memory cells. Its transition function solves the problem in n − 1 iterations, although the first algorithm's memory-cell requirement grows exponentially.

VII. THE SUBSET-SUM PROBLEM

  • Subset-sum asks whether a non-empty subset of an integer set has a specified sum.The input set has cardinality n.Source: §VII · p. 9

A. DCRAM-based algorithm

  • The DCRAM-inspired machine arranges memprocessors in a matrix and performs three operations through a control unit.The machine is an idealized version of DCRAM; its states are analog, while the χ operation can in principle be realized with Boolean gates.Source: A. DCRAM-based algorithm · p. 9, Figure 8 · p. 10
  • The χ operation sums the first-column datum into other columns of selected rows in parallel, without moving data during computation.The control unit selects rows and applies a signal at two selected columns.Source: A. DCRAM-based algorithm · p. 10
  • The DCRAM-inspired algorithm solves subset-sum in n − 1 iterations but requires a maximum number of memory cells that grows exponentially with n.The stated maximum is about (n/2π)^1/2 2^(n−1).Source: A. DCRAM-based algorithm · p. 10
  • The transition function δ = μ ◦ χ ◦ ρ combines the three operations; μ moves data between columns and ρ replicates data.At each iteration, the algorithm calculates sums for subsets of successively smaller cardinalities and stops when it finds the target or reaches the final iteration.Source: A. DCRAM-based algorithm · p. 10

B. Exponential information overhead-based algorithm

The paper describes an information-overhead-based subset-sum algorithm that uses interacting memprocessors to represent subset sums. A discrete Fourier transform reveals target sums through spectral peaks whose magnitudes count matching subsets.

B. Exponential information overhead-based algorithm

  • The information-overhead-based algorithm requires only a linear number of interacting memprocessors to solve subset-sum.The paper distinguishes its numerical implementation, analyzed in the classical UTM context, from its hardware implementation in the UMM paradigm.Source: B. Exponential information… · p. 10

1) Algorithm for the solution of the SSP:

2) Numerical implementation:

The numerical method represents subset sums in a frequency spectrum, bounds and samples that spectrum, then uses Goertzel’s algorithm or the FFT to identify solutions. Its numerical complexity is comparable to dynamic programming, while the authors motivate the FFT-based approach for implementation in memcomputing hardware.

2) Numerical implementation:

  • fmax is bounded by n times the largest absolute input, with the cutoff determined from the sums of positive and negative elements.The method treats frequencies beyond ±fmax as negligible.Source: 2) Numerical implementation · p. 11
  • Integer inputs make g(x) periodic with period T at most 1, allowing the DFT to provide its exact spectrum through FFT sampling.The spectrum has peaks at natural numbers between −fmax and fmax.Source: 2) Numerical implementation · p. 11
  • 4np floating-point operations are needed to compute g(xk) across the discretization points.This count covers np complex exponentials and np complex multiplications.Source: 2) Numerical implementation · p. 11
  • O(np) operations solve for one target sum with Goertzel’s algorithm, but p is not bounded by n and depends on the precision required for fmax.The passage says the number of discretization points N scales exponentially with the number of bits used to represent fmax.Source: 2) Numerical implementation · p. 11
  • O((n + log(p))p) is the stated cost for computing all sums with FFT, matching dynamic programming’s O(np) order, though dynamic programming is practically better for Turing computation.The figure shows representative solutions from the proposed method and dynamic programming for a 27-element set, without reporting a quantitative comparison.Source: 2) Numerical implementation · pp. 11–12, Figure 10 · p. 11

3) Hardware implementation:

The proposed hardware connects CVM memprocessors and reads their output spectrum with a signal analyzer. The authors claim this implementation solves the subset-sum decision problem in one step, while concluding that UMMs have broader computational properties and practical scope tied to their memory architecture.

3) Hardware implementation:

  • Connected CVM memprocessors with a signal analyzer at the final port provide a direct readout of the SSP solution.The signal analyzer selects a frequency-amplitude window without increasing computational burden.Source: 3) Hardware implementation · p. 12, Figure 12 · p. 12
  • A band-pass filter bounds the signal analyzer’s required sample count independently of n and p, and the authors claim the hardware solves SSP in one step for any s.The execution time to obtain the function is determined by its bounded period T, rather than the numerical sampling-point count N.Source: 3) Hardware implementation · p. 12
  • The hardware readout solves the decision version of SSP—whether a subset sums to s—but initially does not identify the subset.The authors describe a procedure using at most n configurations to find one such subset.Source: 3) Hardware implementation · pp. 12–13

VIII. CONCLUSIONS

  • UMMs combine memory storage and processing with intrinsic parallelism, functional polymorphism, and information overhead, which interconnected memprocessors use to store and retrieve more information than cell count alone implies.The paper states these features allow polynomial-time solutions to NP-complete problems, with polynomial versus exponential memprocessor growth depending on whether information overhead is used.Source: §VIII · p. 13
  • The proposed topologically specific hardware architecture is described as solving subset-sum in one step with a linear number of memprocessors if realized.The paper says memelements are one possible implementation, while any system with memory could implement the broader concept.Source: §VIII · p. 13

Related papers

Loading 1405.0931v2…