Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T11:58:46.839Z Has data issue: false hasContentIssue false

Algorithmic Randomness and Measures of Complexity

Published online by Cambridge University Press:  05 September 2014

George Barmpalias*
Affiliation:
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, P.O. BOX 8718, China E-mail: barmpalias@gmail.com, URL: http://www.barmpalias.net

Abstract

We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable