3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ Can you add a citation for the proof? $\endgroup$
    – dynrepsys
    Commented Aug 2, 2016 at 23:05

2 Answers 2

Reset to default
4
$\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$
4
  • $\begingroup$ Do you have a link? Not behind a paywall? $\endgroup$
    – Doxosophoi
    Commented Sep 3, 2016 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
    Commented Sep 3, 2016 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
    Commented Sep 3, 2016 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
    Commented Sep 3, 2016 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .