The ARNN abstract computer, extensively analysed in [28], introduces an analogue-digital model of computation in discrete time. When the parameters of the system (so-called weights) are real-valued, the computations cannot be specified by finite means: we have computation without a program. Several other models of analogue-digital computation were introduced around the same time to explore the power of reals added to digital computation (see [17,27,29]). Under the polynomial time constraint, the ARNN efficiently performs not only all Turing machine efficient computations, but also computes non-recursive functions such as (a unary encoding of) the halting problem (of Turing machines). The reals are introduced into the computation by means of measurements made either by a few neurons that read a weight byte by byte, or by means of a real-valued probability of transition. In the first case, the ARNN decides P/poly in polynomial time and, in the second case, the ARNN decides BPP// log* in polynomial time. However, in these systems, measurements sound physically unrealistic since the function involved in computing the so-called activation of the neurons (the physical processors) is the well-behaved piecewise linear function, exhibiting sharp vertices. In an attempt to recover the classical analytic sigmoid activation function, in [25], the power of the deterministic ARNN in polynomial time drops to P/log* as shown in [7,19].
展开▼
