A conceptual proposal on the undecidability of the distribution law of prime numbers and theoretical consequences

Gianfranco Minati


Within the conceptual framework of number theory, we consider prime numbers and the classic still unsolved problem to find a complete law of their distribution. We ask ourselves if such persisting difficulties could be understood as due to theoretical incompatibilities. We consider the problem in the conceptual framework of computational theory. This article is a contribution to the philosophy of mathematics proposing different possible understandings of the supposed theoretical unavailability and indemonstrability of the existence of a law of distribution of prime numbers. Tentatively, we conceptually consider demonstrability as computability, in our case the conceptual availability of an algorithm able to compute the general properties of the presumed primes’ distribution law without computing such distribution. The link between the conceptual availability of a distribution law of primes and decidability is given by considering how to decide if a number is prime without computing. The supposed distribution law should allow for any given prime knowing the next prime without factorial computing. Factorial properties of numbers, such as their property of primality, require their factorisation (or equivalent, e.g., the sieves), i.e., effective computing. However, we have factorisation techniques available, but there are no (non-quantum) known algorithms which can effectively factor arbitrary large integers. Then factorisation is undecidable. We consider the theoretical unavailability of a distribution law for factorial properties, as being prime, equivalent to its non-computability, undecidability. The availability and demonstrability of a hypothetical law of distribution of primes is inconsistent with its undecidability. The perspective is to transform this conjecture into a theorem.


algorithm; computation; decidability; incompleteness; indemonstrability; law of distribution; prime numbers; symbolic; undecidability.

Full Text:



Beltrami, E. (1868a). Saggio di interpretazione della geometria non-euclidea (English translation: Essay of interpretation of non-Euclidean geometry). Giornale di Mathematiche, VI, 285–315.

Beltrami, E. (1868b). Teoria fondamentale degli spazii di curvatura costante (English translation: Fundamental theory of the spaces of constant curvature). Annali di Matematica pura ed applicata, VI, 232–255.

Bifet, A., Gavaldà, R., Holmes, G., and Pfahringer B. (2018). Machine Learning for Data Streams; MIT Press: Cambridge, MA, USA.

Bohr, N. (1928). The Quantum Postulate and the Recent Development of Atomic Theory. Nature, 121, 580–590.

Brabazon, A., O'Neill, M., McGarraghy, S. (2015). Natural Computing Algorithms. Springer: New York, USA.

Cabessa, J., Villa, A.E.P. (2013). The super-Turing computational power of interactive evolving recurrent neural networks. In ICANN 2013; Mladenov, V., Koprinkova-Hristova, P., Palm, G., Villa, A.E.P., Appollini, B., Kasabov, N., Eds.; Lecture Notes in Computer Science (LNCS); Springer: Berlin/Heidelberg, Germany, Volume 8131, pp. 58–65.

Crandall, R., Pomerance, C.B. (2010). Prime Numbers: A Computational Perspective. Springer: New York, NY, USA.

Edwards, M. (2001). Riemann’s Zeta Function. Dover Publications: New York, NY USA.

Feferman, S., Parsons, C., Simpson, S. Eds. (2010). Kurt Gӧdel: Essays for his centennial; Cambridge University Press: Cambridge, UK.

Ford, J. (1986). Chaos: Solving the unsolvable, predicting the unpredictable. In Chaotic Dynamics and Fractals; Barnsley, M.F., Demko, S.G., Eds.; Academic Press: New York, USA, pp. 1–52. Available online: https://www.sciencedirect.com/science/article/pii/B9780120790609500072?via%3Dihub (accessed on 11 October 2019).

Franze´n, T. (2005). Gӧdel’s theorem: An incomplete guide to its use and abuse; A K Peters: Wellesley, MA.

Gödel, K. (1962). On Formally Undecidable Propositions of Principia Mathematica and Related Systems; Dover Publications Inc.: Mineola, NY, USA.

Goodfellow, I., Bengio, Y., Courville, A., Bach, F. (2017). Deep Learning; MIT Press: Cambridge, MA, USA.

Hawkins, D. (1958). Mathematical Sieves, Scientific American, 199(6), 105-114.

Heisenberg, W. (19721). Physics and Beyond; Harper & Row: New York, NY, USA.

Hernández-Orozco, S., Hernández-Quiroz, F. and Zenil, H. (2016). Undecidability and Irreducibility Conditions for Open-Ended Evolution and Emergence, Artificial Life, 24, 56-70.

Hinton. G. E. and Van Camp, D. (1993). Keeping neural networks simple by minimizing the description length of the weights. In Proceedings of the Sixth Annual Conference on Computational Learning Theory; Pitt, L., Ed.; ACM Press: New York, NY, USA, pp.5-13.

Ingham, A. E. (1932). The Distribution of Prime Numbers (Cambridge Mathematical Library). Cambridge University Press: New York, NY, USA (reprinted on 1990).

Kaplan, I. and Shelah, S. (2017). Decidability and classification of the theory of integers with primes. The Journal of Symbolic Logic, 82(3), 104.

Licata, I. and Minati, G. (2016). Emergence, Computation and the Freedom Degree Loss Information Principle in Complex Systems. Foundations of Science, 21, 863–881.

Longo, G. (2019). Interfaces of Incompleteness. In Systemics of Incompleteness and Quasi-Systems; Minati, G., Abram, M., Pessa, E., Eds.; Springer: New York, NY, USA, pp. 3-55.

Mac Lennan, B.J. (2004). Natural computation and non-Turing models of computation. Theoretical Computer Science, 317(1-3), 115–145.

Maynard-Smith, J. (1982). Evolution and the Theory of Games. Cambridge University Press: Cambridge, UK.

Mazur, B. and Stein, W. (2016). Prime Numbers and the Riemann Hypothesis. Cambridge University Press: New York, NY, USA.

Minati, G. (2016). Knowledge to Manage the Knowledge Society: The Concept of Theoretical Incompleteness. Systems, 4, 26.

Minati, G. (2019). On Theoretical Incomprehensibility. Philosophies, 4(3), https://www.mdpi.com/2409-9287/4/3/49 , Special Issue Philosophy and Epistemology of Deep Learning https://www.mdpi.com/journal/philosophies/special_issues/deep_learning (accessed on 11 October 2019).

Minati, G. and Pessa, E. (2006). Collective Beings; Springer: New York, NY, USA.

Minati, G. and Pessa, E. (2018). From Collective Beings to Quasi-Systems. Springer: New York., USA.

Nepomuceno, E.G., Martins, S.A.M., Silva, B.C., Amaral, G.F.V. and Perc, M. (2018). Detecting unreliable computer simulations of recursive functions with interval extensions. Applied Mathematics and Computation, 329, 408–419.

Nepomuceno, E.G. and Perc, M. (2019). Computational chaos in complex networks. Journal of Complex Networks, 2, 1–16.

Pintz. J. and Rassias, M. T. Eds. (2018). Irregularities in the Distribution of Prime Numbers: From the Era of Helmut Maier's Matrix Method and Beyond; Springer International Publishing.

Raatikainen, P. (2005). On the philosophical relevance of Gӧdel’s incompleteness theorems. Revue Internationale de Philosophie, 59, 513–534.

Riemann, B. (1859). Ueber die Anzahl der Primzahlen unter einer gegebenen Gr¨osse. Monatsberichte der Berliner Akademie, pp. 671-680. https://www.claymath.org/sites/default/files/zeta.pdf (original version), On the Number of Primes Less Than a Given Magnitude (Accessed on 10 November 2019).

https://www.claymath.org/sites/default/files/ezeta.pdf (English translation, (accessed on 11 October 2019).

Shor, P. (1994). Algorithms for quantum computation: Discrete log and factoring; In Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, Santa Fe, IEEE Computer Society Press, pp. 124-134. https://arxiv.org/abs/quant-ph/9508027 (Accessed on 10 November 2019).

Siegelmann, H.T. (2003). Neural and super-Turing computing. Minds and Machines, 13(1), 103–114.

Soare, R.I. (2009). Turing oracle machines, online computing, and three displacements in computability theory. Annals of Pure and Applied Logic, 160, 368–399.

Stinson, D.R. and Paterson, M. (2018). Cryptography: Theory and Practice. CRC Press: Boca Raton, FL, USA.

Syropoulos, A. (2008). Hypercomputation. Computing Beyond the Church–Turing Barrier. Springer: New York, NY, USA.

Toby, O. (2006). The many forms of hypercomputation. Applied Mathematics and Computation, 178(1), 143–153.

Turing, A.M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings London Mathematical Society, 42, 230–265.

Weibull, J. W. (1995). Evolutionary Game Theory. MIT Press, Cambridge, MA, USA.

Younger, A.S., Redd, E. and Siegelmann, H. (2014). Development of Physical Super-Turing Analog Hardware. In Unconventional Computation and Natural Computation; Ibarra, O., Kari, L., Kopecki, S., Eds.; Lecture Notes in Computer Science; Springer: Cham, Switzerland, Volume 8553, pp. 379–392.

Zhou, Z-H., Jiang, Y. and Chen, S-F. (2003). Extracting symbolic rules from trained neural network ensembles, AI Communications, 16: 3-15.

Web resources

See http://www.mat.uniroma2.it/~geo2/TEN/akl_factoring.pdf (accessed on 11 November 2019).

DOI: http://dx.doi.org/10.23755/rm.v37i0.480


  • There are currently no refbacks.

Copyright (c) 2019 Gianfranco Minati

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Ratio Mathematica - Journal of Mathematics, Statistics, and Applications. ISSN 1592-7415; e-ISSN 2282-8214.