Whether Kolmogorov-Loveland randomness is equal to the Martin-Löf randomness is a well known open question in the field of algorithmic information theory. Randomness of infinite binary sequences can be defined in terms of betting strategies, a string is non-random if a computable betting strategy wins unbounded capital by successive betting on the sequence. For Martin-Löf randomness, a betting strategy makes a bet by splitting a set of sequences into any two clopen sets, and placing a portion of capital on one of them as a wager. Kolmogorov-Loveland betting strategies are more restricted, they bet on a value of the bit at some position they choose, which splits a set of sequences into two clopen sets, the sequences that have 0 at the chosen position and the sequences that have 1. In this thesis we consider betting strategies that when making a bet are restricted to split a set of sequences into two sets of equal uniform Lebesgue measure. We call this generalization of Kolmogorov-Loveland betting strategies the half-betting strategies. We show that there is a pair of such betting strategies such that for every non-Martin-Löf random sequence one of them wins unbounded capital (the pair is universal). Next, we define a finite betting game where the betting strategies bet on finite binary strings, and show that in this game Kolmogorov-Loveland betting strategies cannot increase capital by more than an arbitrary small amount on all strings on which the unrestricted betting strategy achieves arbitrary large capital. We also look at another relaxation of Kolmogorov-Loveland betting, where a betting strategy is allowed to access bits of the sequence within a set of positions a bounded number of times. We show that if this bound is less than ℓ - log ℓ for the first ℓ positions then a pair of such betting strategies cannot be universal. Furthermore, we show that, at least for some universal betting strategies, this bound is exponential.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-10-13T19:12:35Z No. of bitstreams: 2 Dissertação - Bruno Rigonato Mundim - 2013.pdf: 1303876 bytes, checksum: 4f1bada6e1186d920d0d0bfcd28d47f1 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2014-10-13T20:49:48Z (GMT) No. of bitstreams: 2 Dissertação - Bruno Rigonato Mundim - 2013.pdf: 1303876 bytes, checksum: 4f1bada6e1186d920d0d0bfcd28d47f1 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-13T20:49:48Z (GMT). No. of bitstreams: 2 Dissertação - Bruno Rigonato Mundim - 2013.pdf: 1303876 bytes, checksum: 4f1bada6e1186d920d0d0bfcd28d47f1 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-09-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / By means of the Curry-Howard Correspondence Martin-Löf’s intuitionistic type theory claims that to define a proposition by laying down how its canonical proofs are formed is the same as to define a set by laying down how its canonical elements are formed; consequently a proposition can be seen as the set of its proofs. On the other hand, we find in this very same theory a distinction between the notions of set and of type, such that the difference of the latter in relation to the former consists in the fact that to form a type we do not need to present an exhaustive prescription for the formation of its objects; it is sufficient to just have a general notion of what would be an arbitrary object that inhabits such type. Thus we argue that we can extract two distinct notions of propositon from the intuitionistic type theory, one which treats propositions as types and another which treats propositions as sets. Such distinction will have some bearing on discussions concerning hypothetical demonstrations and conjecture’s formation. / A teoria intuicionista de tipos, de Martin-Löf, alega, à luz da correspondência Curry- Howard, que definir uma proposição por meio do estabelecimento de como as suas provas canônicas são formadas é o mesmo que definir um conjunto por meio do estabelecimento de como os seus elementos canônicos são formados, fazendo com que uma proposição possa ser vista como o conjunto de suas provas. Por outro lado, encontramos nessa mesma teoria uma distinção entre as noções de conjunto e tipo, sendo que a diferença deste em relação àquele consiste no fato de que para se formar um tipo não é preciso apresentar uma prescrição exaustiva da formação de seus objetos, basta se ter uma noção geral do que seria um objeto arbitrário que o habita. Tendo isso em conta, argumentamos que podemos extrair da teoria intuicionista de tipos duas concepções de proposição distintas, uma que considera proposições como tipos e outra que considera proposições como conjuntos. Tal distinção implicará em algumas considerações envolvendo questões sobre demonstrações hipotéticas e a formação de conjecturas.