ON ANALOGUES OF THE CHURCH–TURING THESIS IN ALGORITHMIC RANDOMNESS.

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 rando...

Descripción completa

Detalles Bibliográficos
Publicado en:Review of Symbolic Logic Vol. 9; no. 3; pp. 456 - 480
Autor principal: PORTER, CHRISTOPHER P.
Formato: Artículo
Publicado: Cambridge University Press Sep2016
Materias:
Acceso en línea:Ver este registro en EBSCOhost
Descripción
Sumario: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.