Edit: Reading the paper they're approximating xorshift which as I understand it is fast and efficient but has very little internal state and is not a strong PRNG.
For such PRNGs, you can either view them as having a known state and an unknown output function or you can view them as having a known output function and a state composed of a known part and of an unknown, secret, part.
The second point of view is more general, as the first case can always be reduced to the second, because the unknown output function must be derived using known functions from a secret key, so you can consider the secret key as the part of the state that is unknown.
(There is a third possible structure for a PRNG, with known state, known output function and unknown transition function, but this is obsolete for making unpredictable PRNGs, as it has inferior properties).
So yes, a pseudo RNG that has a part of its state that remains unknown may produce an output sequence from which it is computationally infeasible to determine its complete state.
Nonetheless, an unpredictable PRNG remains a PRNG, not a true RNG. You can reproduce any time its output sequence if you know the secret part of the state, e.g. when you are the recipient of an encrypted message.
If a ML method would be able to recover the secret part of the state when given the output sequence, obviously that PRNG would be considered broken.
Many PRNGs are designed for high-speed in non-cryptographic applications, e.g. simulations, and for those PRNGs it is usually very easy to determine the internal state from the output sequence, without the need of any ML.
Such RNGs are used instead of true RNGs, which might not be able to provide the required random numbers fast enough. They cannot be used instead of normal PRNGs in most of their applications.
Unpredictable cryptographic PRNGs can be used instead of any other PRNG for simulations, games, MonteCarlo integration etc. and they are actually better than simpler predictable PRNGs, except that they might be too slow.
On modern CPUs with hardware AES instructions, any of the traditional PRNGs that is not faster than computing AES, has become obsolete, as using AES with a counter would provide a random sequence with a higher quality.
In most cases, the output is determined by the output function based on a small part of the state (e.g. you may have 128 bits of state, feed the first 64 bits of it to an output function, and derive a 32-bit output as a result). This means that you don't learn much about the internal state of the generator merely by looking at an output value: you need to observe a lot of consecutive outputs to recover the internal state of the generator, and without knowing the internal state it's difficult (i.e. very hard to impossible) to use a relatively small number of known outputs to predict the next output.
The xorshift128 generator tested in the article has a nigh-trivial output function (because it's designed to be fast, not hard-to-predict) and a very simple transition function, which is why 4 outputs can be used to recover the internal state and to train a NN to predict the next output.
Here's a simple random number generator. You start with a 16 bit number x, (your internal state). At each step you update your internal state to 75x + 74 (mod 65537), and output the first digit of your internal state (your random number)
Here's a sequence of outputs: 6,5,3,3,3,5. Does this information allow you to predict the next output? No.
For example, if the generator's starting state is x=60160, then the generator's internal state evolves as follows: [60160,55558,38093,38958,38296,54183,505]. So the seventh output will be 5. However, if your generator's starting state was instead x=6, then the generator's state evolved as follows: [6,524,39374,3959,34851,57956,21332]. So the seventh output will be 2. The releationship between the first six outputs and the seventh output is not deterministic.
Your prng looks like a truncated LCG, it could be broken if enough outputs are known. For example, 16 bits could be bruteforced in this case. If the internal state have more bits, depends on how much bits do the outputs provide, you could probably break it by Lattice (https://crypto.stackexchange.com/questions/37836/problem-wit...).
For this specific generator, knowing 6 outputs is not enough to pin down the seventh output. Not by using a NN, not by brute-forcing the possible starting seeds, not by lattice methods, not by solving a linear system over a finite field. Unless you know the internal state of the generator, you won't be able to predict the seventh output. And the first 6 outputs simply don't reveal enough information to recover the internal state.
2. To break a PRF it'd need to learn its inverse. For many of them it's unlikely that a small circuit computing the inverse even exists, so a non-iterated NN couldn't even represent the desired function, let alone converge to it.
So yes, an absurdly large ANN will break any PRNG, but so will other absurdly long-running algorithms, some of which are quite trivial: Just try every possible seed until you get the same sequence as what you observe, repeat until only one candidate seed is left.
EDIT: To add to this, you seem to be referring to the universal approximation theorems for ANNs. These theorems state that for any function (subject to some conditions not relevant here) and any arbitrary approximation ratio, there exists a finite ANN that approximates the function to within the desired approximation ratio. It says nothing about whether it's possible to train such an ANN, merely that it exists. Which in this case is a fairly trivial results, you could feasibly create a look-up table of PRNG sequences to seeds and encode that as an enormous ANN. But finding/training this ANN is prohibitively expensive.
Of course, this is assuming that practical CSPRNGs conform to the theory, but we're just debating theory here.
Yes. But chances are that the network size scales exponentially with the number of e.g. input bits. Good luck building/training/storing a model with 2^128 neurons in the hidden layer.