Mutual independence and algorithmic randomness : master's thesis

Pustoslemšek, Andraž (author), Simpson, Alexander Keith (mentor)

The Swedish mathematician Per Martin-Löf defined in 1966 that a sequence is random if it passes all so-called Martin-Löf tests. We would like to seemingly strengthen this definition and say that a random sequence $X$ should not only pass all computable Martin-Löf tests, but also all $Y$-computable Martin-Löf tests, for any oracle $Y$ that is independent of $X$. To do this, we need a suitable notion of independence between infinite sequences. In this thesis, we define such a notion. Indeed, more generally, we define a relation of conditional mutual independence between sequences, and we show that this relation possesses many desirable properties. Furthermore, with this definition, Martin-Löf random sequences automatically satisfy the desired oracle-strengthened definition of randomness. In building towards these results, we shall recall some key statements from computability theory and prove important theorems from the field of algorithmic randomness.

• Language: English
• Keywords: Turing machine, infinite binary sequence, prefix, prefix-free Turing reducibility, oracle, Cantor space, computably open set, pushforward measure, Martin-Löf random sequence, proper sequence, mutual independence
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2025
• PID: 20.500.12556/RUL-170216
• UDC: 510.6
• COBISS.SI-ID: 240937987
• Publication date in RUL: 02.07.2025

Secondary language

• Language: Slovenian
• Title: Medsebojna neodvisnost in algoritmična naključnost

Abstract

Švedski matematik Per Martin-Löf je leta 1966 definiral, da je zaporedje naključno, če opravi vse tako imenovane Martin-Löf teste. To definicijo bi radi navidezno zaostrili in rekli, da naključno zaporedje $X$ ne opravi samo vseh izračunljivih Martin-Löf testov, temveč tudi vse $Y$-izračunljive Martin-Löf teste, pri čemer je $Y$ orakelj, neodvisen od $X$. Za to potrebujemo ustrezno definicijo neodvisnosti med neskončni\-mi zaporedji. V tem delu bomo podali takšno definicijo. Natančneje, definirali bomo relacijo pogojne medsebojne neodvisnosti in pokazali, da ima številne želene lastnosti. Poleg tega bodo s to definicijo medsebojne naključnosti Martin-Löf naključna zaporedja samodejno zadostovala zaostreni definiciji naključnosti z orakljem. Za dosego teh rezultatov bomo povzeli nekatere ključne trditve iz teorije izračunljivosti in dokazali pomembne izreke s področja algoritmične naključnosti.

• Keywords: Turingov stroj, neskončno binarno zaporedje, predpona, brez predpone, Turingova reduktibilnost, orakelj, Cantorjev prostor, izračunljivo odprta množica, potisnjena mera, Martin-Löf naključno zaporedje, pravilno zaporedje, medsebojna neodvisnost