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?