Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Theory of Computing Systems 2/2017

14.04.2016

Conditional Measure and the Violation of Van Lambalgen’s Theorem for Martin-Löf Randomness

verfasst von: Bruno Bauwens

Erschienen in: Theory of Computing Systems | Ausgabe 2/2017

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

Van Lambalgen’s theorem states that a pair (α, β) of bit sequences is Martin-Löf random if and only if α is Martin-Löf random and β is Martin-Löf random relative to α. In [Information and Computation 209.2 (2011): 183-197, Theorem 3.3], Hayato Takahashi generalized van Lambalgen’s theorem for computable measures P on a product of two Cantor spaces; he showed that the equivalence holds for each β for which the conditional probability P(⋅|β) is computable. He asked whether this computability condition is necessary. We give a positive answer by providing a computable measure for which van Lambalgen’s theorem fails. We also present a simple construction of a computable measure for which conditional measure is not computable. Such measures were first constructed by Ackerman et al. ([1]).

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 15 Tage kostenlos.

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
There exist two types of Martin-Löf tests relative to a non-computable measure P [5]:
  • A uniform P-Martin-Löf test is a P-Martin-Löf test that is effectively open relative to each oracle that computes P.
  • A Hippocratic or blind P-Martin-Löf test is a Martin-Löf test that is effectively open without any oracle.
If P is computable, then both types of tests define the same set of random sequences. Otherwise, the second type of tests defines a weaker notion of randomness, which we use here. Although the definition looks easier, it might not be the most natural definition of randomness relative to a non-computable measure P.
 
2
2 The construction has some similarities with the measure constructed in the proof of Proposition 6.3 in [2]: the measure has also singularities that approach a left computable real. However, I believe there is no deeper correspondence between this measure and the measure constructed here.
 
Literatur
1.
Zurück zum Zitat Ackerman, N., Freer, C., Roy, D.: Noncomputable conditional distributions. In: Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS), pp. 107–116. IEEE (2011) Ackerman, N., Freer, C., Roy, D.: Noncomputable conditional distributions. In: Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS), pp. 107–116. IEEE (2011)
4.
Zurück zum Zitat De Leeuw, K., Moore, E.F., Shannon, C.E., Shapiro, N.: Computability by probabilistic machines. Autom. Stud. 34, 183–198 (1955) MathSciNet De Leeuw, K., Moore, E.F., Shannon, C.E., Shapiro, N.: Computability by probabilistic machines. Autom. Stud. 34, 183–198 (1955) MathSciNet
5.
Zurück zum Zitat Kjos-Hanssen, B.: The probability distribution as a computational resource for randomness testing. J. Logic Anal. 2 (2010) Kjos-Hanssen, B.: The probability distribution as a computational resource for randomness testing. J. Logic Anal. 2 (2010)
6.
Zurück zum Zitat Lambalgen, M.V.: The axiomatization of randomness. J. Symbol. Logic, 1143–1167 (1990) Lambalgen, M.V.: The axiomatization of randomness. J. Symbol. Logic, 1143–1167 (1990)
7.
Zurück zum Zitat Rute, J.: Personal communication (2014) Rute, J.: Personal communication (2014)
8.
9.
Zurück zum Zitat Shen, A., et al.: Conditional probabilities and van Lambalgen theorem revisited. In preparation (2015) Shen, A., et al.: Conditional probabilities and van Lambalgen theorem revisited. In preparation (2015)
10.
Zurück zum Zitat Takahashi, H.: On a definition of random sequences with respect to conditional probability. Inf. Comput. 206(12), 1375–1382 (2008) MathSciNetCrossRefMATH Takahashi, H.: On a definition of random sequences with respect to conditional probability. Inf. Comput. 206(12), 1375–1382 (2008) MathSciNetCrossRefMATH
11.
12.
Zurück zum Zitat Takahashi, H.: Generalization of van Lambalgen’s theorem and blind randomness for conditional probability. Preprint arXiv: 1310.​0709. Presented in sept 2013 at CCR in Moscow (2013) Takahashi, H.: Generalization of van Lambalgen’s theorem and blind randomness for conditional probability. Preprint arXiv: 1310.​0709. Presented in sept 2013 at CCR in Moscow (2013)
Metadaten
Titel
Conditional Measure and the Violation of Van Lambalgen’s Theorem for Martin-Löf Randomness
verfasst von
Bruno Bauwens
Publikationsdatum
14.04.2016
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 2/2017
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-016-9675-3

Weitere Artikel der Ausgabe 2/2017

Theory of Computing Systems 2/2017 Zur Ausgabe

Premium Partner