Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Entire DC Network
Computational Complexity For Continuous Time Dynamics, Hava Siegelmann, Asa Ben-Hur, Shmuel Fishman
Computational Complexity For Continuous Time Dynamics, Hava Siegelmann, Asa Ben-Hur, Shmuel Fishman
Hava Siegelmann
Dissipative flows model a large variety of physical systems. In this Letter the evolution of such systems is interpreted as a process of computation; the attractor of the dynamics represents the output. A framework for an algorithmic analysis of dissipative flows is presented, enabling the comparison of the performance of discrete and continuous time analog computation models. A simple algorithm for finding the maximum of n numbers is analyzed, and shown to be highly efficient. The notion of tractable (polynomial) computation in the Turing model is conjectured to correspond to computation with tractable (analytically solvable) dynamical systems having polynomial complexity.
Discontinuities In Recurrent Neural Networks, R. Gavaldà, Hava Siegelmann
Discontinuities In Recurrent Neural Networks, R. Gavaldà, Hava Siegelmann
Hava Siegelmann
This article studies the computational power of various discontinuous real computational models that are based on the classical analog recurrent neural network (ARNN). This ARNN consists of finite number of neurons; each neuron computes a polynomial net function and a sigmoid-like continuous activation function. We introduce arithmetic networks as ARNN augmented with a few simple discontinuous (e.g., threshold or zero test) neurons. We argue that even with weights restricted to polynomial time computable reals, arithmetic networks are able to compute arbitrarily complex recursive functions. We identify many types of neural networks that are at least as powerful as arithmetic nets, …