Top EDTN Story: from EE Times

Analog computer trumps Turing model

By Sunny Bains

HAIFA, Israel — Recent developments in computing theory challenge longstanding assumption about digital and analog computing, and suggest that analog computations are more powerful than digital ones.

The latest thesis, advanced by Hava Siegelmann at the Technion Institute of Technology, claims that some computational problems can only be solved by analog neural networks. Since neural networks are essentially analog computers, the work suggests, on a theoretical level, that analog operations are inherently more powerful than digital.

Based on her work, Siegelmann believes that neural networks represent a "super-Turing" computer more comprehensive than even a hypothetical digital computer with unlimited resources. Long-term, Siegelmann said she hopes her model will open up completely new ways of thinking about computing.

Siegelmann would like to see the neural network "considered a standard model in the realm of analog computation, functioning in a role parallel to that of the Turing machine in the Church-Turing thesis," she said. "Our analog computation thesis suggests that no possible abstract analog device can have more computational capabilities than neural networks."

British mathematician Alan Turing proposed the hypothetical Turing computer in the 1930s to settle a question in mathematical logic. His purpose was to give a precise mathematical definition to the concept of an algorithm. Turing's theoretical computer was designed with only a finite number of discrete states, and used a finite alphabet of symbols stored on an infinitely long tape that would be read by the machine.

Turing was able to show that the hypothetical computer could execute any mathematically defined algorithm, a result that became known as the "Church-Turing thesis" because Alonzo Church, another logician, proved essentially the same theorem using a different approach. Turing went on to develop one of the first digital electronic computers at the end of World War II.

While both analog and digital computers have been developed, the digital variety triumphed for purely technical reasons. The digital approach makes the control of errors more feasible, and the unexpected success of VLSI technology has made each generation of machine more accurate and powerful.

"Computer science is deeply rooted in the idea of the classical computer," Siegelmann said. "The entire structure of the language is geared toward the Turing machine." Neural networks, however, have introduced an interesting counterpoint to the digital paradigm.

Siegelmann's computational model is a conventional collection of neurons arranged in a general structure that includes loops. However, the weights between the neurons, the strength of their connection, is represented by real numbers, not just the rational values that digital computers can represent.

Regardless of whether the input and output are digital, the analog nature of the network means the whole structure acts as a complex dynamical system. For this reason, the information processing going on has much more in common with physics than does conventional computing.

The crux of the difference between analog and digital computing is the number of bits of precision available. In the Turing machine, numbers can be stored with any degree of precision since the storage medium is an infinite tape. Depending on the sensitivity of the algorithm being used, enough decimal places can be included to get the right answer.

On this basis, it has generally been believed that an analog computer has no advantages. Not only will it suffer from problems of noise and unpredictability, conventional wisdom holds, but the "infinite precision" that it might theoretically offer is already effectively available to digital computers.

In nature, said Siegelmann, physical quantities such as energy or position are not incremented in discrete chunks, as they are in their binary, or digital, representation. Instead, their exact values can vary continuously.

"Furthermore," she said, "the dynamical behavior of natural systems is influenced by real [numerical] values, which may describe basic physical constants such as the speed of light, Planck's constant and the charge of the electron." In particular, the recent revelations of chaos theory have shown that extremely small errors in initial conditions can grow to influence behavior on a large scale.

When the functions being computed are complex to the point of being chaotic, it's not difficult to see how the abilities of digital computers can fall short.

The mathematical model of analog computation suggested by Siegelmann is, similarly, a dynamical system that evolves in a continuous-phase space, in contrast to the discrete-space model of digital computers. She interprets the dynamical behavior of systems as a process of computation and shows, mathematically, the essential difference between the two paradigms. "The neural network that represents the analog computer proves to be inherently richer than the standard Turing model," said Siegelmann. "It encompasses and transcends digital computation while its power remains bounded and sensitive to resource constraints."

This model cuts little ice with many computer scientists and programmers, however. Christos Papadimitriou, professor of computer science at the University of California at Berkeley, summed up their objections. Trivially, he said, physical systems may well take on irrational values. "Even a rod of length equal to a noncomputable number is non-Turing." However, said Papadimitriou, "the interesting question is whether such systems can be usefully employed in computation. I do not think so. How do you manufacture such a rod, and how do you read its thousandth digit?"

Assumption of continuity
Siegelmann understands the concern. She views the neural networks her project has analyzed mainly as a mathematical idealization, "assuming continuous-phase space and exactly precise data in order to enable the design of novel continuous algorithms."

This assumption of continuity is common in mathematics, she said. It is the basis for using integrals to approximate volumes and allows the design of efficient "interior point" algorithms for linear programming, where the previously used discrete algorithms are exponentially slow. This continuous framework may be what makes many neural networks so efficient, Siegelmann said.

Papadimitriou said he remains skeptical. "I don't think that analog systems can be dramatically more powerful than ordinary computers," he said. "The argument is simple and familiar: Analog systems based on physical phenomena that can be described by differential equations can be simulated by ordinary computers in time not substantially greater than the delay of such systems. Substantial, and by this I mean exponential, gains are thus impossible."

Siegelmann countered that analog computing is fundamentally different than its digital counterpart. "With analog computers, the classical models of computing that everybody uses simply do not hold up, at least not in all circumstances," she said. "Those working in the area of analog computing should note that, if they were using an irrational number, they were probably not computing the Turing algorithms that they intended to."

---