A note on Monte Carlo primality tests and algorithmic information theory
David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
clusions are only probably correct. On the other hand, algorithmic information theory provides a precise mathematical definition of the notion of random or patternless sequence. In this paper we shall describe conditions under which if the sequence of coin tosses in the Solovay– Strassen and Miller–Rabin algorithms is replaced by a sequence of heads and tails that is of maximal algorithmic information content, i.e., has maximal algorithmic randomness, then one obtains an error-free test for primality. These results are only of theoretical interest, since it is a manifestation of the G¨ odel incompleteness phenomenon that it is impossible to “certify” a sequence to be random by means of a proof, even though most sequences have this property. Thus by using certified random sequences one can in principle, but not in practice, convert probabilistic tests for primality into deterministic ones.
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library||
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Wayne Aitken & Jeffrey A. Barrett (2007). Stability and Paradox in Algorithmic Logic. Journal of Philosophical Logic 36 (1):61 - 95.
Jeffrey Barrett (2007). Stability and Paradox in Algorithmic Logic. Journal of Philosophical Logic 36 (1):61 - 95.
Yuri Gurevich & Grant Olney Passmore (2012). Impugning Randomness, Convincingly. Studia Logica 100 (1-2):193-222.
Alejandro Balbín & Eugenio Andrade (2004). Protein Folding and Evolution Are Driven by the Maxwell Demon Activity of Proteins. Acta Biotheoretica 52 (3):173-200.
Michiel Van Lambalgen (1987). Von Mises' Definition of Random Sequences Reconsidered. Journal of Symbolic Logic 52 (3):725 - 755.
Michiel Van Lambalgen (1989). Algorithmic Information Theory. Journal of Symbolic Logic 54 (4):1389 - 1400.
Marcin Miłkowski (2009). Is Evolution Algorithmic? Minds and Machines 19 (4):465-475.
Panu Raatikainen (2000). Algorithmic Information Theory and Undecidability. Synthese 123 (2):217-225.
W. J. (2003). Algorithmic Randomness in Empirical Data. Studies in History and Philosophy of Science Part A 34 (3):633-646.
Added to index2009-02-15
Total downloads84 ( #49,450 of 1,796,217 )
Recent downloads (6 months)14 ( #51,296 of 1,796,217 )
How can I increase my downloads?