Why can machine learning not recognize prime numbers? Say we have a vector representation of any integer of magnitude n, V_n

This vector is the input to a machine learning algorithm.

First question : For what type of representations is it possible to learn the primality/compositeness of n using a neural network or some other vector-to-bit ML mapping. This is purely theoretical -- the neural network could be possibly unbounded in size. 

Let's ignore representations that are already related to primality testing such as : the null separated list of factors of n, or the existence of a compositeness witness such as in Miller Rabin. Let's instead focus on representations in different radices, or representations as coefficient vectors of (possibly multivariate) polynomials. Or other exotic ones as are posited.

Second question : for what, if any, types of ML algorithm will learning this be impossible regardless of the specifics of the representation vector? Again, let's leave out 'forbidden by triviality' representations of which examples are given above. 

The output of the machine learning algorithm is a single bit, 0 for prime, 1 for composite.

The title of this question reflects my assessment that the consensus for question 1 is 'unknown' and the consensus for question 2 is 'probably most ML algorithms'. I'm asking this as I don't know any more than this and I am hoping someone can point the way.

The main motivation, if there is one, of this question is : is there an 'information theoretic' limit to the structure of the set of primes that can be captured in a neural network of a particular size? As I'm not expert in this kind of terminology let me rephrase this idea a few times and see if I get a Monte-Carlo approximation to the concept : what is the algorithmic complexity of the set of primes? Can the fact that the primes are Diophantine recursively enumerable (and can satisfy a particular large diophantine equation) be used to capture the same structure in a neural network with the inputs and outputs described above.
The question is, in my opinion, quite vague and involves some misunderstanding, so this answer attempts only to provide the right vocabulary and point you in the right direction.

There are two fields of computer science that directly study such problems. Inductive inference and computational learning theory. The two fields are very closely related and the distinction is a social and aesthetic one, rather than a formal one. 

Fix a finite alphabet $A$ and the set of all languages $\mathcal{P}(A^*)$ consisting of finite-length words over $A$. This is everything you can express in terms of $A$. Now consider a family of languages $\mathcal{F} \subseteq \mathcal{P}(A^*)$. You can think of this as the concepts you are interested in. You often have to fix the family of concepts you care about because, as others have pointed out, the representation of the concept and presentation of data are extremely important.

Imagine a teacher who is going to teach you a concept. The teacher will choose one of the languages without your knowledge. The teacher will then present information to you about the language. There are many presentations. The simplest is to give you examples. A presentation of positive data is a function $f: \mathbb{N} \to A^*$ satisfying that 

$$\bigcup_{i \in \mathbb{N}} f(i) = T, \text{ for some } T \text{ in } \mathcal{F}.$$

So, a presentation of positive data is an enumeration of the target concept, often with some additional fairness conditions thrown in. You can similarly ask for a presentation that labels words depending on whether they are in the language or not. Again, you can add additional conditions to ensure fairness and coverage of all words. 

Suppose we have a family $Rep$ of representations of languages. That means every element $M$ of $Rep$ defines a language $L(M)$. Examples of representations are Boolean formulae, finite automata, regular expressions, systems of linear equations, domain specific programming languages, etc. Anything you want, really, except various condition are usually imposed to ensure the representation has basic tractability properties.

A passive learner is a function $p: \mathbb{N} \to Rep$ that makes a conjecture after seeing each word provided by the teacher. We may often require that the learner is consistent. Meaning, the language $L(p(i))$ should contain all the words $f(j)$ for $j \le i$. The learner stabilizes if the learner's guess for the target language does not change. Specifically, there should exist some index $k$ such that for all $j \ge k$, $L(p(j)) = L(p(j+1))$. The learner succeeds if the final language equals the target language. 

Let me emphasise that this is only one specific formalisation of one specific learning model. But this is step zero before you can start asking and studying questions that you are interested in. The learning model can be enriched by allowing interaction between the learner and the teacher. Rather than arbitrary families of languages, we can consider very specific languages, or even specific representations (such as monotone Boolean functions). There is a difference between what you can learn in each model and the complexity of learning. Here is one example of a fundamental impossibility result.


  Gold [1967] No family of languages that contains all finite languages and at least one super-finite language is passively learnable from positive data alone.


One should be very very careful in interpreting this result. For example, Dana Angluin showed in the 80s that 


  Angluin [1982] The class of $k$-reversible languages is passively learnable in the limit from positive data.


The class of $k$-reversible languages is infinite, contains super-finite languages, but interestingly, does not contain all finite languages. Now once you change the learning model, the fundamental results change. 


  Angluin [1987] Regular languages are learnable from a teacher that answers equivalence queries and provides counterexamples. The algorithm is polynomial in the set of states of the minimal DFA and length of the maximal counterexample.


This is quite a strong and positive result and recently has found several applications. However, as always the details are important, as the title of the paper below already suggests.


  The minimum consistent DFA problem cannot be approximated within and polynomial
  , Pitt and Warmuth, 1989.


Now you may be wondering, how is any of this relevant to your question? To which my answer is that the design space for a mathematical definition of your problem is very large and the specific point you choose in this space is going to affect the kind of answers you will get. The above is not meant to be a comprehensive survey of how to formalise the learning problem. It's just meant to demonstrate the direction you may want to investigate. All the references and results I quote are extremely dated, and the field has done a lot since then. There are basic textbooks you could consult to obtain the sufficient background to formulate your question in a precise manner and determine if the answer you seek already exists.