Algorithmic randomness [Elektronische Ressource] / vorgelegt von Nenad Mihailovic

I n a u g u r a l - D i s s e r t a t i o nzurErlangung der Doktorwurde¨derNaturwissenschaftlich-Mathematischen Gesamtfakultat¨derRuprecht-Karls-Universitat¨Heidelbergvorgelegt vonDiplom-Mathematiker Nenad Mihailovi´caus ZrenjaninTag der mundlichen Prufung: 25. Oktober 2007¨ ¨ThemaAlgorithmic RandomnessGutachter: Prof. Dr. Klaus Ambos-SpiesPriv.-Doz. Dr. Wolfgang MerkleZusammenfassungWir betrachten algorithmische Zufalli¨ gkeit im Cantorraum C der unendlichenBinarfolgen. Durch ein algorithmisches Zufalligkeitskonzept wird eine Menge¨ ¨von Elementen von C bestimmt, denen jeweils die Eigenschaft zugeordnet wird,zuf¨alligzusein.SolcheKonzeptewerdenunterVerwendungvonverschiedenenbe-rechenbarkeitstheoretischenBegriffendefiniertundgehenimWesentlichenaufdiefolgendendreiintuitivenAnforderungenanzufalli¨ geFolgenzuruc¨ k:DieAnfangs-stucke einer zufalligen Folge sollen effektiv inkomprimierbar sein, keine zufallige¨ ¨ ¨Folge soll in einer effektiven Nullmenge von Folgen mit einer “Ausnahmeeigen-schaft” enthalten sein, und schließlich soll fur ein Wettspiel, in welchem die¨Bits einer Folge nacheinander geraten werden, bei einer zuf¨alligen Folge keineeffektive Strategie dem Spieler unbeschrankt viel Kapital verschaffen. Fur ver-¨ ¨schiedene Formalisierungen dieser Anforderungen werden jeweils Versionen vonKolmogorov-Komplexitat, Tests und Martingalen verwendet.