# Computability considerations regarding neural nets

In mathematics and logic, computable functions = Turing computable functions

## Question#1: Neural network computable → Turing computable?

- Presumably Turing machines can simulate any neural network to arbitrary finite precision given enough memory.

## Question#2: Turing computable → neural network computable?

- 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.`

@

## Comments

- 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.

Mind