Optimal redundancy in computations from random oracles

作者：

Highlights：

• Kucera–Gacs theorem.

• Optimal redundancy.

• Logarithmic redundancy.

• New coding method.

• Compressing streams into random streams.

摘要

•Kucera–Gacs theorem.•Optimal redundancy.•Logarithmic redundancy.•New coding method.•Compressing streams into random streams.

论文关键词：Optimal coding,Algorithmic randomness,Minimal redundancy,Random codes,Algorithmic information theory

论文评审过程：Received 28 June 2016, Revised 12 June 2017, Accepted 20 June 2017, Available online 20 July 2017, Version of Record 13 November 2017.

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