Solovay functions and their applications in algorithmic randomness

作者：

Highlights：

• We introduce the notion of Solovay function, as a type of ‘good approximation of Kolmogorov complexity’.

• We show that most of the classical theory of algorithmic randomness can be rebuilt based on Solovay functions.

• Likewise, we show that Solovay functions integrate nicely in the study of K-triviality.

摘要

•We introduce the notion of Solovay function, as a type of ‘good approximation of Kolmogorov complexity’.•We show that most of the classical theory of algorithmic randomness can be rebuilt based on Solovay functions.•Likewise, we show that Solovay functions integrate nicely in the study of K-triviality.

论文关键词：Kolmogorov complexity,Algorithmic randomness,Solovay functions

论文评审过程：Received 29 July 2014, Revised 14 April 2015, Accepted 16 April 2015, Available online 18 May 2015, Version of Record 25 August 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.04.004