20.500.12556/RUL-170216 Mutual independence and algorithmic randomness master's thesis Medsebojna neodvisnost in algoritmična naključnost 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. Š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. 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 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 true false false Angleški jezik Slovenski jezik Magistrsko delo/naloga 2025-07-02 15:27:43 2025-07-02 15:27:45 2025-07-07 12:50:44 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 510.6 150686 240937987 17865.pdf 17865.pdf 1 E9049D21CA3DE4168C9C1B6462A27BD8 a5dd1aee6949cb99bbcbbc7a53fd3bd7387a860494a8f8e7a6ab9807b5541fc2 7402b9f3-5746-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=212169 Fakulteta za matematiko in fiziko 0 0 0