Main.NeuralNetworkComputability History
Hide minor edits - Show changes to output
Changed lines 6-7 from:
to:
* Note: choice of activation functions.
Changed lines 7-8 from:
!!Neural network computable → Turing computable?
to:
!!Question#1: Neural network computable → Turing computable?
Changed lines 11-12 from:
!!Turing computable → neural network computable?
to:
!!Question#2: Turing computable → neural network computable?
Changed lines 11-12 from:
!!Neural networks can compute Turing computable functions
to:
!!Turing computable → neural network computable?
Added line 14:
Added line 16:
Added line 18:
Changed lines 21-22 from:
to:
Added lines 1-23:
!Computability considerations regarding neural nets
In mathematics and logic, computable functions = Turing computable functions
* [[Computation Turing|Turing machines]]
!!Neural network computable → Turing computable?
* Presumably Turing machines can simulate any neural network to arbitrary finite precision given enough memory.
!!Neural networks can compute Turing computable functions
* Siegelmann and Sontag (1991). Turing Computability With Neural Nets. ''Applied Mathematics Letters''.
@@@This paper shows the existence of a finite neural network, made up of sigmoidal neurons, which simulates a universal Turing machine. It is composed of less than 10'^5^' synchronously evolving processors, interconnected linearly. High-order connections are not required.@@@
* J. Pedro Neto, Hava T. Siegelmann, J. Félix Costa, C.P. Suarez Araujo. (1997). Turing Universality of Neural Nets (Revisited). ''Lecture Notes in Computer Science – 1333'', 361-366. Springer-Verlag.
@@@We show how to use recursive function theory to prove Turing universality of finite analog recurrent neural nets, with a piecewise linear sigmoid function as activation function.@@@
!!Comment
* Such mathematical results do not show that if X is computational equivalent to Y, then X is just as efficient and practical to implement as Y.
* The systems can differ at the level of algorithm and at the level of hardware implementation.
[[Category/Mind]]