Normality in non-integer bases and polynomial time randomness

作者：

Highlights：

• Relationship between polynomial time randomness and normality in Pisot bases.

• Generalization of martingales to non-uniform distributions.

• Invariant Markov measures and martingales computed by a DFA.

摘要

•Relationship between polynomial time randomness and normality in Pisot bases.•Generalization of martingales to non-uniform distributions.•Invariant Markov measures and martingales computed by a DFA.

论文关键词：Algorithmic randomness,Polynomial time randomness,Normality,Subshift,Pisot number,Deterministic finite automaton,Martingale

论文评审过程：Received 31 October 2014, Revised 13 April 2015, Accepted 16 April 2015, Available online 29 April 2015, Version of Record 10 June 2015.

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