Kolmogorovkomplexität [Elektronische Ressource] / vorgelegt von Rupert Hölzl

INAUGURALDISSERTATIONzurErlangung der DoktorwürdederNaturwissenschaftlich-MathematischenGesamtfakultätderRuprecht-Karls-Universität HeidelbergVorgelegt vonDiplom-Mathematiker Rupert HölzlausMünchen.Tag der mündlichen Prüfung: 16. Dezember 2010ThemaKolmogorovkomplexitätGutachter: Priv.-Doz. Dr. Wolfgang MerkleProf. Dr. Frank StephanKolmogorov complexityby Rupert HölzlEnglish abstract: This dissertation discusses new results on Kolmogorov com-plexity. Its first part focuses on the study of Kolmogorov complexity without timebounds. Here we deal with the concept of non-monotonic randomness, that israndomness characterized by martingales that bettonically. We will statethe definitions of several different randomness classes and then separate them fromeach other. We also present a a systematic survey of a wide array of traceabilitynotions and characterize them through (auto)complexity notions. Traceabilities area group of notions that express that a set is not far away from being computable.The second part of the document deals with the topic of time bounded Kol-mogorov complexity. First we investigate the difference between two ways ofdescribing a word: the complexity of describing it well enough so that it can bedistinguished from other words; and the complexity of describing it well enough sothat the word can actually be produced from the description.