2
$\begingroup$

It is proved that a recurrent neural net with rational weights can be a super-Turing machine. Can we achieve this in practice ?

$\endgroup$
  • 3
    $\begingroup$ Can you add a citation for the proof? $\endgroup$ – dynrepsys Aug 2 '16 at 23:05
3
$\begingroup$

I presume the proof the OP is referring to can be found in this monograph by Hava Siegelmann?

In his article 'The Myth of Hypercomputation', the eminent computer scientist Martin Davis explains (p8-9) that there is nothing 'super Turing' about this formulation.

EDIT: It's looking like the claim about rational weights being super-Turing is made in this more recent paper by Siegelmann, which introduces an additional assumption of plasticity, i.e. that weights can be dynamically updated.

| improve this answer | |
$\endgroup$
1
$\begingroup$

You mean real numbered weights (specifically, irrational). This would require a machine that has unlimited precision over irrational values. I've seen machine parts that have many qualities. I've never seen one that has unlimited qualities. QM may give us some magical transistors that can hold an unlimited number of different values - or by deferring computation into the future and then teleporting the results back into the past (our present). Outside of that, for classical systems, you'd need a analog device that can output irrational values with unlimited precision. I don't think we've discovered any devices that can do that.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Do you have a link? Not behind a paywall? $\endgroup$ – Doxosophoi Sep 3 '16 at 16:34
  • 1
    $\begingroup$ Something must have got lost in translation. This is from a paper on alanturing.net: In the special case where all the interconnection weights are rational, each such network is equivalent to a Turing machine (Siegelmann and Sontag 1992). If the connection matrix contains at least one irrational weight, the processor network can compute non Turing-machine-computable functions, even in polynomial time. p29, BEYOND THE UNIVERSAL TURING MACHINE $\endgroup$ – Doxosophoi Sep 3 '16 at 17:15
  • $\begingroup$ I just read those two referenced pages. I see no argument that a neural net with just rational weights is hyper Turing. $\endgroup$ – Doxosophoi Sep 3 '16 at 17:21
  • $\begingroup$ Yeah, I'm not saying they're they same thing. But it is the set of irrationals, within real numbers, not rationals, that suggest some hyper Turing possibility. $\endgroup$ – Doxosophoi Sep 3 '16 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.