<p>this is an old question/problem with many, many connections deep into number theory, mathematics, TCS and in particular Automated Theorem Proving.[5]</p>

<p>the old, near-ancient question is, "is there a formula for computing primes"</p>

<p>the answer is, yes, in a sense, there are various <em>algorithms</em> to compute it.</p>

<p>the Riemann zeta function can be reoriented as an "algorithm" to find primes.</p>

<p>seems possible to me that a GA, genetic-algorithm approach may succeed on this problem some day with an ingenious setup, ie GAs are the nearest known technology that have the most chance of succeeding.[6][7] its the problem of finding an algorithm from a finite set of examples, ie machine learning, which is very similar to mathematical induction. however there does not seem to be much research into application of GAs in number theory so far.</p>

<p>the nearest to this in existing literature seems to be eg [8] that discusses developing the twin prime conjecture in an automated way ie "automated conjecture making".</p>

<p>another approach is a program that has a large set of tables of standard functions, along with some sophisticated conversion logic, to recognize standard integer sequences. this is a new function built into Mathematica called <code>findsequence</code> [3]</p>

<p>its also connected to a relatively new field called "experimental mathematics" [9,10] or what is also called "empirical" research in TCS.</p>

<p>another basic point to make here is that the sequence of primes is not "smooth", highly irregular, chaotic, fractal, and standard machine learning algorithms are historically based on numerical optimization and minimizing error (eg gradient descent), and do not do so well on finding exact answers to discrete problems. but again GAs can succeed and have been shown to succeed in this area/regime.</p>

<p>[1] <a href="https://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime">is there a math eqn for the nth prime,</a> math.se</p>

<p>[2] <a href="http://en.wikipedia.org/wiki/Formula_for_primes" rel="nofollow noreferrer">formula for primes</a>, wikipedia</p>

<p>[3] <a href="http://reference.wolfram.com/mathematica/ref/FindSequenceFunction.html" rel="nofollow noreferrer">wolfram findsequence function</a></p>

<p>[4] <a href="http://en.wikipedia.org/wiki/Riemann_zeta_function" rel="nofollow noreferrer">riemann zeta function</a></p>

<p>[5] <a href="https://cstheory.stackexchange.com/questions/11784/automated-theorem-proving-via-unsupervised-approaches">top successes of automated theorem proving</a></p>

<p>[6] <a href="https://cstheory.stackexchange.com/questions/427/what-are-some-real-world-applications-for-genetic-algorithms">applications of genetic algorithms in real world</a></p>

<p>[7] <a href="http://books.google.com/books/about/Applying_Genetic_Algorithms_to_Automated.html?id=5psmMwAACAAJ" rel="nofollow noreferrer">applying genetic algorithms to automated thm proving</a> by Wang</p>

<p>[8] <a href="http://www.doc.ic.ac.uk/~sgc/papers/colton_jsc05.pdf" rel="nofollow noreferrer">Automated Conjecture Making in Number
Theory using HR, Otter and Maple</a> colton</p>

<p>[9] <a href="https://cstheory.stackexchange.com/questions/14605/are-there-applications-of-experimental-mathematics-in-tcs">Are there applications of experimental mathematics in TCS?</a></p>

<p>[10] <a href="https://cstheory.stackexchange.com/questions/822/a-reading-list-on-experimental-algorithmics">A reading list on experimental algorithmics</a></p>

CC BY-SA 3.0
2013-01-11T16:20:15.320Z
this is a great answer. Not sure if the site will agree, but it was what I was looking for. A bunch of new directions to explore and age old connections. Thanks, really appreciate that. Particularly GAs. Also, you read between the lines and generalized from machine learning to 'formular for primes'. That is very helpful thanks.
Cris Stringfellow
CC BY-SA 3.0
2013-01-11T16:49:08.940Z
@Cris, there is almost nothing in this answer which is about machine learning. From your comment on Aryeh's answer it seems to me that you are not familiar with machine learning (may I ask where have you seen a machine learn an algorithm like primality  testing from a list of examples?)
Kaveh
CC BY-SA 3.0
2013-01-12T00:25:29.973Z
GA can "learn" a primality testing algorithm in the same sense in which the proverbial infinite monkey will one day type the full works of Shakespeare
Sasho Nikolov
CC BY-SA 3.0
2013-01-12T02:52:19.433Z
@sasho, it hasnt been demonstrated yet but (yes, imho) its probably not due to limitations in the technology but rather lack of attempt. koza demonstrated GAs "solving/learning" complex algorithms for video games eg pacman (via lisp trees of primitives), and also constructing circuits using subcomponents. isnt that at least as hard as finding primes? the real question is, what types of primitives would the system have, and how primitive can they be & still find the solution?
vzn
CC BY-SA 3.0
2013-01-11T16:06:47.043Z
2013-01-11T16:33:03.997Z
2017-04-13T12:32:30.623Z
vzn
<p>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.</p>

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

<p>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 <em>concepts</em> 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.</p>

<p>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 <em>presentation of positive data</em> is a function $f: \mathbb{N} \to A^*$ satisfying that </p>

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

<p>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. </p>

<p>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.</p>

<p>A <em>passive learner</em> 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 <em>stabilizes</em> 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 <em>succeeds</em> if the final language equals the target language. </p>

<p>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.</p>

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

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

<blockquote>
  <p><strong>Angluin [1982]</strong> The class of $k$-reversible languages is passively learnable in the limit from positive data.</p>
</blockquote>

<p>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. </p>

<blockquote>
  <p><strong>Angluin [1987]</strong> 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.</p>
</blockquote>

<p>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.</p>

<blockquote>
  <p><a href="http://dl.acm.org/citation.cfm?doid=73007.73048">The minimum consistent DFA problem cannot be approximated within and polynomial
  </a>, Pitt and Warmuth, 1989.</p>
</blockquote>

<p>Now you may be wondering, <em>how is any of this relevant to your question?</em> 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. </p>

CC BY-SA 3.0
2013-01-12T06:44:48.713Z
That's great @Vijay D, thank you for that.
Cris Stringfellow
CC BY-SA 4.0
2020-01-15T18:32:20.917Z
It is an ill formed question. My answer (and comments) below show why. ML can recognize primes, but not in any practical sense, it would take too long. Such is the nature of that particular beasty.
Birkensox
CC BY-SA 3.0
2013-01-11T23:40:12.317Z
2013-01-11T23:40:12.317Z
Vijay D
<p>The success of a learning algorithm depends critically on the representation. How do you present the input to the algorithm? In an extreme case, suppose you present the numbers as sequences of prime factors -- in this case, learning is quite trivial. In another extreme, consider representing the numbers as binary strings. All the standard learning algorithms I know would fail here. Here is one that would work: find the smallest Turing machine that accepts all the positive examples and rejects all the negative ones. [Exercise: prove that this is a universal learner.] One problem with that is that the task is not Turing-computable. To put things in perspective, can <em>you</em> learn to recognize primality based only on the binary representation?</p>

CC BY-SA 3.0
2013-01-11T16:26:05.577Z
I can learn to recognize primality based in binary rep if I 'learn' , say, the Miller Rabin algorithm. But I want to go beyond things like that, and see if there is something else. Why is the task you mention not Turing-computable?
Cris Stringfellow
CC BY-SA 3.0
2013-01-11T23:05:31.170Z
I don't understand how one can talk about a learning problem here without referring to, for instance, the target class of functions.
Lev Reyzin
CC BY-SA 3.0
2013-01-13T12:31:51.743Z
Lev is right, of course -- but I thought a discussion of function classes would be beyond the scope of the question... :)
Aryeh
CC BY-SA 3.0
2013-01-11T07:36:28.640Z
2013-01-11T07:36:28.640Z
Aryeh
<p>This problem is part of modern research: given input and output data, find simplest algorithm which produces output from input. RNN networks are Turing-complete, so theoretically by endless SGD you can end up in RNN which is equivalent to this code:</p>

<pre><code>bool isPrime(int n, int d) {
    if(n&lt;2)
        return 0;
    if(d == 1)
        return true;
    else 
    {
        if(n % d == 0) 
            return false;
        else
            return isPrime(n, d - 1);
    }
}
</code></pre>

<p>on this dataset:
0=>0, 1=>0, 2=>1, 3=>1, 4=>0, 5=>1, ... etc</p>

<p>The problem is that we have no practically-reliable theory on SGD convergency nor any estimates of time required for convergence or neural network depth. But latest research shows that alike problems can be though solved:</p>

<p><a href="https://en.wikipedia.org/wiki/Neural_Turing_machine" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Neural_Turing_machine</a></p>

<p><a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/curr_opin_sys_biol_17.pdf" rel="nofollow noreferrer">https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/curr_opin_sys_biol_17.pdf</a></p>

<p><a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/cav13.pdf" rel="nofollow noreferrer">https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/cav13.pdf</a></p>

<p>use google scholar to search for keywords...</p>

CC BY-SA 4.0
2018-06-08T13:24:20.363Z
2018-06-08T13:24:20.363Z
Stepan Yakovenko
<p>Machine learning is subject to the laws of computing complexity.</p>

<p>The prime factorization problem is in the NP complexity class, possibly even NP-hard (not proven).</p>

<p>That is why detecting primes is among the hardest problems in machine learning, and might not be possible at all with that approach.</p>

<p>Quantum computers (QC) can do it in polynomial time, but Shor's is brute-force determinism, not machine learning. </p>

<p>Possibly a QC learning algorithm based on Shor's is an approach. I am really just banging the rocks together by suggesting that.</p>

CC BY-SA 4.0
2020-01-15T05:13:00.520Z
PRIMES is in P, so I wouldn’t say “detecting primes” is among the hardest problems in ML — or any other branch of computer science, for that matter. “It’s all about representation” hits a lot closer to home—as explained in my answer and the comments below it.
Aryeh
CC BY-SA 4.0
2020-01-15T18:23:08.880Z
Excuse mee, P≠NP! PRIMES is co-NP, and to solve it in P would currently require a Galactic algorithm entirely unsuited in any computing paradigm - especially machine learning, no matter how you represent it. In any practical sense it is NP, and possibly NP-hard, thank yoo.
Birkensox
CC BY-SA 4.0
2020-01-22T01:41:19.997Z
@Birkensocks you appear to have conflated Primality testing with Factoring. "PRIMES is in P" is actually the name of the paper that first provided a polynomial-time algorithm to check primality, https://en.wikipedia.org/wiki/AKS_primality_test. Also note, that Factoring is in NP and co-NP, so very unlikely to be NP-hard, see e.g., https://blog.computationalcomplexity.org/2002/09/complexity-class-of-week-factoring.html
Rahul Savani
CC BY-SA 4.0
2020-01-22T06:28:14.477Z
Yeah I think I already said that ...
Birkensox
CC BY-SA 4.0
2020-01-15T00:42:09.893Z
2020-01-15T00:59:07.127Z
2020-01-15T00:59:07.127Z
Birkensox
<p>Say we have a vector representation of any integer of magnitude n, V_n</p>

<p>This vector is the input to a machine learning algorithm.</p>

<p>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. </p>

<p>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.</p>

<p>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. </p>

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

<p>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.</p>

<p>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 href="http://op.to/primephantine+" rel="noreferrer">a particular large diophantine equation</a>) be used to capture the same structure in a neural network with the inputs and outputs described above. </p>

CC BY-SA 3.0
2013-01-10T20:55:47.013Z
From the theory perspective, your problem isn't well-defined.  What are the inputs to the machine learning algorithm? How are they generated?  What does the algorithm know in advance of its learning task?
Lev Reyzin
CC BY-SA 3.0
2013-01-10T21:02:59.387Z
I don't think this is a good question in its current form for this site.
Kaveh
CC BY-SA 3.0
2013-01-11T00:10:45.353Z
It can. But in machine learning we want to minimize error on testing dataset. Now, if you train on $[1, 20]$ you might end up learning $f(n) = n^2 - n + 41$ and which works perfectly for numbers less that $41$. But after that its performance is no good. People have tried this(manually :-) ) and so far [without much success](http://en.wikipedia.org/wiki/Formula_for_primes). In ML we try to find patterns but what if there isn't any pattern?
Pratik Deoghare
CC BY-SA 3.0
2013-01-11T01:25:48.733Z
You seem to be asking whether there is an algorithm that given a function from finite sequences of natural numbers to predicates on the natural numbers, can correctly output a primality predicate given a sequence of primes, subject to additional constraints on the algorithm. Articulating your restriction further is non-trivial, if at all possible. If you try to make it precise, you may see.
Vijay D
CC BY-SA 3.0
2013-01-11T03:12:54.510Z
A simple answer, because it is difficult to approximate the search space $S$ of the prime number function $f$ you are looking for (that is, $f(n)$ returns 1 if $n$ is prime and 0 otherwise for every $n$). In  relation to @PratikDeoghare comment, it is difficult to find a pattern in $S$.
AJed
CC BY-SA 3.0
2013-01-11T15:45:54.890Z
think this is a well-defined near-TCS problem related to _induction_ (from a finite set of examples) and _automated theorem proving_ but not a well _studied_ problem....
vzn
CC BY-SA 3.0
2013-01-11T16:00:38.567Z
@vzn could you expand that a little?
Cris Stringfellow
CC BY-SA 3.0
2013-11-23T21:18:54.380Z
somewhat related, recently the breakthrough zhang proof on twin primes was optimized using genetic algorithms. see [machine learning applications in number theory](http://stats.stackexchange.com/questions/73801/machine-learning-applications-in-number-theory)
vzn
CC BY-SA 4.0
2018-06-10T19:07:19.237Z
It might be whether primes is in $TC^0$ is relevant here before thinking ML for primes. Is it in $TC^0$?
Turbo
<co.combinatorics><machine-learning><primes>
Why can machine learning not recognize prime numbers?
Cris Stringfellow
# Why can machine learning not recognize prime numbers?

(Asked by: username_0 on 2013-01-10)

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](http://op.to/primephantine+)) be used to capture the same structure in a neural network with the inputs and outputs described above.

**Tags:** co.combinatorics, machine-learning, primes
> **Comments:**
> **username_1**: From the theory perspective, your problem isn't well-defined.  What are the inputs to the machine learning algorithm? How are they generated?  What does the algorithm know in advance of its learning task?  
> **username_2**: I don't think this is a good question in its current form for this site.  
> **username_3**: It can. But in machine learning we want to minimize error on testing dataset. Now, if you train on $[1, 20]$ you might end up learning $f(n) = n^2 - n + 41$ and which works perfectly for numbers less that $41$. But after that its performance is no good. People have tried this(manually :-) ) and so far [without much success](http://en.wikipedia.org/wiki/Formula_for_primes). In ML we try to find patterns but what if there isn't any pattern?  
> **username_4**: You seem to be asking whether there is an algorithm that given a function from finite sequences of natural numbers to predicates on the natural numbers, can correctly output a primality predicate given a sequence of primes, subject to additional constraints on the algorithm. Articulating your restriction further is non-trivial, if at all possible. If you try to make it precise, you may see.  
> **username_5**: A simple answer, because it is difficult to approximate the search space $S$ of the prime number function $f$ you are looking for (that is, $f(n)$ returns 1 if $n$ is prime and 0 otherwise for every $n$). In  relation to @PratikDeoghare comment, it is difficult to find a pattern in $S$.  
> **username_6**: think this is a well-defined near-TCS problem related to _induction_ (from a finite set of examples) and _automated theorem proving_ but not a well _studied_ problem....  
> **username_0**: @vzn could you expand that a little?  
> **username_6**: somewhat related, recently the breakthrough zhang proof on twin primes was optimized using genetic algorithms. see [machine learning applications in number theory](http://stats.stackexchange.com/questions/73801/machine-learning-applications-in-number-theory)  
> **username_7**: It might be whether primes is in $TC^0$ is relevant here before thinking ML for primes. Is it in $TC^0$?  

---

## 5 answers

### Answer by username_6 on 2013-01-11. Score: -7 | Accepted answer

this is an old question/problem with many, many connections deep into number theory, mathematics, TCS and in particular Automated Theorem Proving.[5]

the old, near-ancient question is, "is there a formula for computing primes"

the answer is, yes, in a sense, there are various *algorithms* to compute it.

the Riemann zeta function can be reoriented as an "algorithm" to find primes.

seems possible to me that a GA, genetic-algorithm approach may succeed on this problem some day with an ingenious setup, ie GAs are the nearest known technology that have the most chance of succeeding.[6][7] its the problem of finding an algorithm from a finite set of examples, ie machine learning, which is very similar to mathematical induction. however there does not seem to be much research into application of GAs in number theory so far.

the nearest to this in existing literature seems to be eg [8] that discusses developing the twin prime conjecture in an automated way ie "automated conjecture making".

another approach is a program that has a large set of tables of standard functions, along with some sophisticated conversion logic, to recognize standard integer sequences. this is a new function built into Mathematica called `findsequence` [3]

its also connected to a relatively new field called "experimental mathematics" [9,10] or what is also called "empirical" research in TCS.

another basic point to make here is that the sequence of primes is not "smooth", highly irregular, chaotic, fractal, and standard machine learning algorithms are historically based on numerical optimization and minimizing error (eg gradient descent), and do not do so well on finding exact answers to discrete problems. but again GAs can succeed and have been shown to succeed in this area/regime.

[1] [is there a math eqn for the nth prime,](https://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime) math.se

[2] [formula for primes](http://en.wikipedia.org/wiki/Formula_for_primes), wikipedia

[3] [wolfram findsequence function](http://reference.wolfram.com/mathematica/ref/FindSequenceFunction.html)

[4] [riemann zeta function](http://en.wikipedia.org/wiki/Riemann_zeta_function)

[5] [top successes of automated theorem proving](https://cstheory.stackexchange.com/questions/11784/automated-theorem-proving-via-unsupervised-approaches)

[6] [applications of genetic algorithms in real world](https://cstheory.stackexchange.com/questions/427/what-are-some-real-world-applications-for-genetic-algorithms)

[7] [applying genetic algorithms to automated thm proving](http://books.google.com/books/about/Applying_Genetic_Algorithms_to_Automated.html?id=5psmMwAACAAJ) by Wang

[8] [Automated Conjecture Making in Number
Theory using HR, Otter and Maple](http://www.doc.ic.ac.uk/~sgc/papers/colton_jsc05.pdf) colton

[9] [Are there applications of experimental mathematics in TCS?](https://cstheory.stackexchange.com/questions/14605/are-there-applications-of-experimental-mathematics-in-tcs)

[10] [A reading list on experimental algorithmics](https://cstheory.stackexchange.com/questions/822/a-reading-list-on-experimental-algorithmics)

> **Comments:**
> **username_0**: this is a great answer. Not sure if the site will agree, but it was what I was looking for. A bunch of new directions to explore and age old connections. Thanks, really appreciate that. Particularly GAs. Also, you read between the lines and generalized from machine learning to 'formular for primes'. That is very helpful thanks.  
> **username_2**: @Cris, there is almost nothing in this answer which is about machine learning. From your comment on Aryeh's answer it seems to me that you are not familiar with machine learning (may I ask where have you seen a machine learn an algorithm like primality  testing from a list of examples?)  
> **username_8**: GA can "learn" a primality testing algorithm in the same sense in which the proverbial infinite monkey will one day type the full works of Shakespeare  
> **username_6**: @sasho, it hasnt been demonstrated yet but (yes, imho) its probably not due to limitations in the technology but rather lack of attempt. koza demonstrated GAs "solving/learning" complex algorithms for video games eg pacman (via lisp trees of primitives), and also constructing circuits using subcomponents. isnt that at least as hard as finding primes? the real question is, what types of primitives would the system have, and how primitive can they be & still find the solution?  

---

### Answer by username_4 on 2013-01-11. Score: 19

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](http://dl.acm.org/citation.cfm?doid=73007.73048), 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.

> **Comments:**
> **username_0**: That's great @Vijay D, thank you for that.  
> **username_9**: It is an ill formed question. My answer (and comments) below show why. ML can recognize primes, but not in any practical sense, it would take too long. Such is the nature of that particular beasty.  

---

### Answer by username_10 on 2013-01-11. Score: 13

The success of a learning algorithm depends critically on the representation. How do you present the input to the algorithm? In an extreme case, suppose you present the numbers as sequences of prime factors -- in this case, learning is quite trivial. In another extreme, consider representing the numbers as binary strings. All the standard learning algorithms I know would fail here. Here is one that would work: find the smallest Turing machine that accepts all the positive examples and rejects all the negative ones. [Exercise: prove that this is a universal learner.] One problem with that is that the task is not Turing-computable. To put things in perspective, can *you* learn to recognize primality based only on the binary representation?

> **Comments:**
> **username_0**: I can learn to recognize primality based in binary rep if I 'learn' , say, the Miller Rabin algorithm. But I want to go beyond things like that, and see if there is something else. Why is the task you mention not Turing-computable?  
> **username_1**: I don't understand how one can talk about a learning problem here without referring to, for instance, the target class of functions.  
> **username_10**: Lev is right, of course -- but I thought a discussion of function classes would be beyond the scope of the question... :)  

---

### Answer by username_11 on 2018-06-08. Score: 0

This problem is part of modern research: given input and output data, find simplest algorithm which produces output from input. RNN networks are Turing-complete, so theoretically by endless SGD you can end up in RNN which is equivalent to this code:
bool isPrime(int n, int d) {
    if(n<2)
        return 0;
    if(d == 1)
        return true;
    else 
    {
        if(n % d == 0) 
            return false;
        else
            return isPrime(n, d - 1);
    }
}

on this dataset:
0=>0, 1=>0, 2=>1, 3=>1, 4=>0, 5=>1, ... etc
The problem is that we have no practically-reliable theory on SGD convergency nor any estimates of time required for convergence or neural network depth. But latest research shows that alike problems can be though solved:
https://en.wikipedia.org/wiki/Neural_Turing_machine
https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/curr_opin_sys_biol_17.pdf
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/cav13.pdf
use google scholar to search for keywords...


---

### Answer by username_9 on 2020-01-15. Score: -3

Machine learning is subject to the laws of computing complexity.

The prime factorization problem is in the NP complexity class, possibly even NP-hard (not proven).

That is why detecting primes is among the hardest problems in machine learning, and might not be possible at all with that approach.

Quantum computers (QC) can do it in polynomial time, but Shor's is brute-force determinism, not machine learning.

Possibly a QC learning algorithm based on Shor's is an approach. I am really just banging the rocks together by suggesting that.

> **Comments:**
> **username_10**: PRIMES is in P, so I wouldn’t say “detecting primes” is among the hardest problems in ML — or any other branch of computer science, for that matter. “It’s all about representation” hits a lot closer to home—as explained in my answer and the comments below it.  
> **username_9**: Excuse mee, P≠NP! PRIMES is co-NP, and to solve it in P would currently require a Galactic algorithm entirely unsuited in any computing paradigm - especially machine learning, no matter how you represent it. In any practical sense it is NP, and possibly NP-hard, thank yoo.  
> **username_12**: @Birkensocks you appear to have conflated Primality testing with Factoring. "PRIMES is in P" is actually the name of the paper that first provided a polynomial-time algorithm to check primality, https://en.wikipedia.org/wiki/AKS_primality_test. Also note, that Factoring is in NP and co-NP, so very unlikely to be NP-hard, see e.g., https://blog.computationalcomplexity.org/2002/09/complexity-class-of-week-factoring.html  
> **username_9**: Yeah I think I already said that ...  

---

