Yes, but computation can be performed with a function approximator where each iteration is a function `f :: (state, input) -> (state', output)`. This is the bas

Yes, but computation can be performed with a function approximator where each iteration is a function `f :: (state, input) -> (state', output)`. This is the basis of an architecture called a 'neural turing machine' (http://arxiv.org/abs/1410.5401 http://arxiv.org/abs/1410.5401) and it is, indeed, Turing complete and can be trained through standard neural network training algorithms to perform arbitrary computations.