views:

44

answers:

2

I'm interested in the computational power of neural nets. It is generally accepted that recurrent neural nets are Turing complete. Now I was searching for some papers which proofs this.

What I found so far:

  • Turing computability with neural nets, Hava T. Siegelmann and Eduardo D. Sontag, 1991

    I think this is only interesting from a theoretical point of view because it needs to have the neuron activity of infinite exactness (to encode the state somehow as a rational number).

  • S. Franklin and M. Garzon, Neural computability

    This needs an unbounded number of neurons and also doesn't really seem to be that much practical.

(Note that another question of mine tries to point out this kind of problem between such theoretical results and the practice.)

I'm searching mostly for some neural net which really can execute some code which I can also simulate and test in practice. Of course, in practice, they would have some kind of limited memory.

Does anyone know something like this?

+1  A: 

Maybe this paper? http://lipas.uwasa.fi/stes/step96/step96/hyotyniemi1/

dmazzoni
Ah thank you for that.
Albert
+1  A: 

A bit off topic, but perhaps useful in your search (which sounds like a Masters/Ph.D. thesis). In my experience of using learning algorithms for things like classification, segmentation, etc., Bayesian learning is superior to all forms of neural nets, genetic algorithms, and other nifty sounding algorithms due to its strong mathematical basis.

A foundation in mathematics, in my book, makes a technique superior to ad-hoc methods. For example, the result from a Bayesian network can be mathematically interpreted as a probability (even with a p-value if you like), while a neural net is often guesswork. Unfortunately, Bayesian statistics doesn't sound as sexy as "neural network" even though it's arguably more useful and well founded.

I would love to see somebody shake this out formally in an academic setting.

Rich
Interesting statement. I'd also like to see some more formally and well worked out results on the comparison of computational power. But I think that (recurrent) neural networks are clearly more powerful in what they can calculate (everything what a Turing machine can) compared to what you get out of a Bayesian network.
Albert