A Characterization of Infinite Binary Sequences with Partial Randomness
Summary :
K-randomness and Martin-Lof randomness are among many formalizations of randomness of infinite sequences, and these two are known to be equivalent. We can naturally modify the former to the definition of partial randomness. However, it is not obvious how to modify the latter to the definition of partial randomness. In this paper, we show that we can modify Martin-Lof randomness to a definition of partial randomness that is equivalent to the definition obtained by naturally modifying K-randomness. The basic idea is to modify the notion of measures used in the definition of Martin-Lof tests.
- Publication
- IEICE TRANSACTIONS on Information Vol.E81-D No.8 pp.801-805
- Publication Date
- 1998/08/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroaki NAGOYA, "A Characterization of Infinite Binary Sequences with Partial Randomness" in IEICE TRANSACTIONS on Information,
vol. E81-D, no. 8, pp. 801-805, August 1998, doi: .
Abstract: K-randomness and Martin-Lof randomness are among many formalizations of randomness of infinite sequences, and these two are known to be equivalent. We can naturally modify the former to the definition of partial randomness. However, it is not obvious how to modify the latter to the definition of partial randomness. In this paper, we show that we can modify Martin-Lof randomness to a definition of partial randomness that is equivalent to the definition obtained by naturally modifying K-randomness. The basic idea is to modify the notion of measures used in the definition of Martin-Lof tests.
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_8_801/_p
Copy
@ARTICLE{e81-d_8_801,
author={Hiroaki NAGOYA, },
journal={IEICE TRANSACTIONS on Information},
title={A Characterization of Infinite Binary Sequences with Partial Randomness},
year={1998},
volume={E81-D},
number={8},
pages={801-805},
abstract={K-randomness and Martin-Lof randomness are among many formalizations of randomness of infinite sequences, and these two are known to be equivalent. We can naturally modify the former to the definition of partial randomness. However, it is not obvious how to modify the latter to the definition of partial randomness. In this paper, we show that we can modify Martin-Lof randomness to a definition of partial randomness that is equivalent to the definition obtained by naturally modifying K-randomness. The basic idea is to modify the notion of measures used in the definition of Martin-Lof tests.},
keywords={},
doi={},
ISSN={},
month={August},}
Copy
TY - JOUR
TI - A Characterization of Infinite Binary Sequences with Partial Randomness
T2 - IEICE TRANSACTIONS on Information
SP - 801
EP - 805
AU - Hiroaki NAGOYA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 1998
AB - K-randomness and Martin-Lof randomness are among many formalizations of randomness of infinite sequences, and these two are known to be equivalent. We can naturally modify the former to the definition of partial randomness. However, it is not obvious how to modify the latter to the definition of partial randomness. In this paper, we show that we can modify Martin-Lof randomness to a definition of partial randomness that is equivalent to the definition obtained by naturally modifying K-randomness. The basic idea is to modify the notion of measures used in the definition of Martin-Lof tests.
ER -
English
