ON ANALOGUES OF THE CHURCH-TURING THESIS IN ALGORITHMIC RANDOMNESS

作     者：Porter, Christopher P. 

作者机构：Univ Florida Dept Math Gainesville FL 32611 USA 

出 版 物：《REVIEW OF SYMBOLIC LOGIC》 (符号逻辑评论)

年 卷 期：2016年第9卷第3期

页      面：456-479页

核心收录：

学科分类：01[哲学] 0101[哲学-哲学] 0701[理学-数学] 

基　　金：National Science Foundation as part of the International Research Fellowship Program [OISE-1159158] John Templeton Foundation as part of the project, "Structure and Randomness in the Theory of Computation" 

主　　题：ALGORITHMIC randomness MATHEMATICS ALGORITHMS THEOREMS (Mathematics) FUNCTIONS (Mathematics) 

摘      要：In this article, I consider the status of several statements analogous to the Church-Turing thesis that assert that some definition of algorithmic randomness captures the intuitive conception of randomness. I argue that we should not only reject the theses that have appeared in the algorithmic randomness literature, but more generally that we ought not evaluate the adequacy of a definition of randomness on the basis of whether it captures the so-called intuitive conception of randomness to begin with. Instead, I argue that a more promising alternative is to evaluate the adequacy of a definition of randomness on the basis of whether it captures what I refer to as a notion of almost everywhere typicality. In support of my main claims, I will appeal to recent work in showing the connection between of algorithmic randomness and certain almost everywhere theorems from classical mathematics.