The difference between optimality and universality

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

We discuss the difference between optimality and universality. The sequence of measures of a universal test is well studied. To analyze the sequence of measures of an optimal Martin-L̈of test, we introduce uniform Solovay reducibility. Solovay reducibility is a measure of relative randomness between two reals. In contrast uniform Solovay reducibility is a measure of relative randomness between two sequences of reals. Finally we prove that a sequence is uniform Solovay complete iff it is the sequence of measures of an optimal Martin-L̈of test.

Original languageEnglish
Article numberjzr032
Pages (from-to)222-234
Number of pages13
JournalLogic Journal of the IGPL
Volume20
Issue number1
DOIs
Publication statusPublished - 1 Feb 2012

Keywords

  • Martin-Lof randomness
  • Randomness deficiency
  • Sequence of measures
  • Solovay reducibility
  • Universal Martin-Lof test

Fingerprint Dive into the research topics of 'The difference between optimality and universality'. Together they form a unique fingerprint.

  • Cite this