Premium
Algorithmic randomness over general spaces
Author(s) -
Miyabe Kenshi
Publication year - 2014
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201200051
Subject(s) - randomness , mathematics , measure (data warehouse) , computable analysis , space (punctuation) , metric space , metric (unit) , randomness tests , discrete mathematics , computable function , pure mathematics , computer science , statistics , data mining , operations management , economics , operating system
The study of Martin‐Löf randomness on a computable metric space with a computable measure has seen much progress recently. In this paper we study Martin‐Löf randomness on a more general space, that is, a computable topological space with a computable measure. On such a space, Martin‐Löf randomness may not be a natural notion because there is no universal test, and Martin‐Löf randomness and complexity randomness (defined in this paper) do not coincide in general. We show that SCT 3 is a sufficient condition for the existence and coincidence, and study how much we can weaken this condition.