2
$\begingroup$

This reference from the german wikipedia article on neural networks states:

There are also many other important problems that are so difficult that a neural network will be unable to learn them without memorizing the entire training set, such as:

  • Predicting random or pseudo-random numbers.

  • Factoring large integers.

  • Determining whether a large integer is prime or composite.

  • Decrypting anything encrypted by a good algorithm.

Can someone explain, why this limitation should hold for all kinds of neural networks and for any advances in the future?

Are there any formal possibilities to prove that this problems cant be solved with a neural network?

Lets look at the third note. There are many insights on the distribution of prime numbers and this paper shows, that the calculations for proving that an integer is a prime number, can be done in polynomial time (PRIMES is in P). So why is this problem "to difficult" to be solved by a neural network?

Improve this question
$\endgroup$
1
  • $\begingroup$ Neural networks solve problems in a very specific way. $\endgroup$
    – Yuval Filmus
    Sep 15 '17 at 12:17
2
$\begingroup$

This paper introduces a finite size neural network and proves that it can simulate a Turing Machine, meaning that this NN is Turing complete. Thus anything that may be computed using TMs can be computed by this type of NNs. You may want to read this too.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Note that the problems listed in the question are (thought to be) hard for TMs. Except for primality checking, that is. $\endgroup$
    – adrianN
    Sep 15 '17 at 11:11
  • $\begingroup$ @adrianN I am curious, too, If there is a NN more powerful than TMs. $\endgroup$
    – fade2black
    Sep 15 '17 at 11:31
  • $\begingroup$ Probably not, Church-Turing thesis and all that. $\endgroup$
    – adrianN
    Sep 15 '17 at 12:32
  • $\begingroup$ @adrianN, probably, he asked if deterministic NN can solve harder (than $\mathsf P$) problems in polynomial amount of resources. But I don't think so. $\endgroup$
    – rus9384
    Sep 15 '17 at 12:57
  • 1
    $\begingroup$ This answer talks about the expressive power of NN, I think a good answer should talk about the learning perspective, though to do this you need to have a well defined learning task at hand. See e.g this question cstheory.stackexchange.com/questions/15039/… $\endgroup$
    – Ariel
    Sep 15 '17 at 13:38

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.