Let's look at some specific tasks.
Input is the bytecode of a program, as integers.
Let's use a program that computes prime numbers. I'm pretty sure you can write such a program in a reasonably small number of bytes. Let's add another integer, the number of primes we want to find.
The output would be whether the second highest bit of the prime is 0 or 1 (i.e. if the prime begins with 0...010 or 0...011) Just two classes.
Alternatively, let the input be a program, and the output whether the program halts, or not (cf. "halting problem").
I'm pretty sure, not even the largest neural network can predict the output reliably of these two examples even if you bound the input length. So there is no guarantee of being able to learn anything with just enough nodes. what you can probably guarantee id the ability to overfit. Given N training examples (that have consistent labels), you can build a network with x nodes that perfectly memoizes the training data (but that is unable to generalize, so it is overfitted to the training data).