L¹-Computability, Layerwise Computability and Solovay Reducibility

Article type: Research Article

Authors: Miyabe, Kenshi

Affiliations: Research Institute for Mathematical Sciences, Kyoto University Kitashirakawa-Oiwakecho, Sakyo-ku, Kyoto 606-8502, Japan [email protected] http://kenshi.miyabe.name/wordpress/

Abstract: We propose a hierarchy of classes of functions that corresponds to the hierarchy of randomness notions. Each class of functions converges at the corresponding random points. We give various characterizations of the classes, that is, characterizations via integral tests, L1-computability and layerwise computability. Furthermore, the relation among these classes is formulated using a version of Solovay reducibility for lower semicomputable functions.

Keywords: algorithmic randomness, computable analysis, [TeX:] $L^1$-computability, layerwise computability, Solovay reducibility

DOI: 10.3233/COM-13015

Journal: Computability, vol. 2, no. 1, pp. 15-29, 2013