3 ms·

But on a computational power level, does that actually make them more powerful? What I mean is that Finite state machines are less powerful computationally tha

by mabbo 12y ago

But on a computational power level, does that actually make them more powerful? What I mean is that Finite state machines are less powerful computationally than context free grammars. A FSM cannot compute certain things that a CFG can. Further, a CFG can't compute certain things that a Turing machine can. But we do know that Neural networks like the ones being used for Deep Learning can compute anything a Turing machine can, and anything a Turing machine can compute, so can the NN. They're equivalent. So the real question is this: do those features (spiking, conduction delays) actually make biological neural networks capable of computing something that Turing Machines and Artificial Neural Networks cannot? I hypothesize the answer is "no". A Turing machine could simulate any of those features you've mentioned, and therefore an ANN could also simulate them. (But I would love to be wrong about it, that would be amazing if human minds could do something that no machine would ever be capable of!)

dragonwriter 12y ago
> So the real question is this: do those features (spiking, conduction delays) actually make biological neural networks capable of computing something that Turing Machines and Artificial Neural Networks cannot? Are Turing machines proven to be able to compute anything computable, so isn't this known absolutely to be a "no"?
- mabbo 12y ago
  Well, ask this: does "computable" mean the upper limit of all things that can be computed ever, or simply the upper limit of what can be computed in the ways we know to compute things? Maybe there is indeed a way to solve the halting problem using a type of computation we can't quite imagine yet. And maybe the human brain is capable of that kind of computation. I don't even know if we know the answers to those questions. I suspect not. This is where computer science starts to get all philosophical, which is pretty awesome.
Houshalter 12y ago
Neural networks are universal function approximators, not Turing machines. They can theoretically learn any series of "if...then..." functions with enough neurons. But there are a lot of functions they can't represent very efficiently or without absurdly large numbers of neurons and training data.
- a-priori 12y ago
  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.
a-priori 12y ago
Sorry for the delayed response here. I was speaking before on a neuron-for-neuron basis. In computation-theoretic terms, I presume a spiking neural network model such as Izhikevich E.M. (2003) is equally powerful to a rate-based model such as Graves et al. (2014), in that they're both equivalent to a Turing machine. (At least I assume Izhikevich's model can be, though I'm not aware of any proofs or demonstrations of it performing arbitrary computations.) Also, keep in mind that saying something is 'Turing complete' only says that a machine is capable of computing anything that any other universal Turing machine can perform. It doesn't say anything about how efficiently it can do it. For example, a conventional computer and a quantum computer can both do integer factorization. But a quantum computer can do it much more efficiently, being able to do it in polynomial time. A quantum computer is therefore more powerful, even if they're both equivalent machines in computation-theoretic terms.

by mabbo 12y ago

dragonwriter 12y ago

> So the real question is this: do those features (spiking, conduction delays) actually make biological neural networks capable of computing something that Turing Machines and Artificial Neural Networks cannot? Are Turing machines proven to be able to compute anything computable, so isn't this known absolutely to be a "no"?

mabbo 12y ago
Well, ask this: does "computable" mean the upper limit of all things that can be computed ever, or simply the upper limit of what can be computed in the ways we know to compute things? Maybe there is indeed a way to solve the halting problem using a type of computation we can't quite imagine yet. And maybe the human brain is capable of that kind of computation. I don't even know if we know the answers to those questions. I suspect not. This is where computer science starts to get all philosophical, which is pretty awesome.

Houshalter 12y ago

Neural networks are universal function approximators, not Turing machines. They can theoretically learn any series of "if...then..." functions with enough neurons. But there are a lot of functions they can't represent very efficiently or without absurdly large numbers of neurons and training data.

a-priori 12y ago
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.

a-priori 12y ago

Sorry for the delayed response here. I was speaking before on a neuron-for-neuron basis. In computation-theoretic terms, I presume a spiking neural network model such as Izhikevich E.M. (2003) is equally powerful to a rate-based model such as Graves et al. (2014), in that they're both equivalent to a Turing machine. (At least I assume Izhikevich's model can be, though I'm not aware of any proofs or demonstrations of it performing arbitrary computations.) Also, keep in mind that saying something is 'Turing complete' only says that a machine is capable of computing anything that any other universal Turing machine can perform. It doesn't say anything about how efficiently it can do it. For example, a conventional computer and a quantum computer can both do integer factorization. But a quantum computer can do it much more efficiently, being able to do it in polynomial time. A quantum computer is therefore more powerful, even if they're both equivalent machines in computation-theoretic terms.