v2i1 32 Letters and Notes For example, beings (as well as possible beings and things impossible of being) can be understood in the context of possible worlds. A “possible world” is a su!ciently complete description of possible states of a"airs described through chains of propositions. We may observe that things impos- sible of being, such as a square circle, have in them mutu- ally inconsistent required core attributes; they cannot be realised in any possible world. Possible beings would exist in at least one possible world were it actualised. For instance, a contingent being B that depends on C might exist in a world W and not in a closely neighbouring one W ! if C is present in W but not W !; C thus being an enabling, necessary causal factor for B. By contrast, a necessary be- ing F will exist in all possible worlds, showing itself to be a framework element for such a world. A key insight is that for any world W to be distinct from W ! it requires some factor A in W that is absent in W !. We may then partition the factors of W as W = {A|¬A}. After parti- tioning, we will have two distinct groups—the factor A and all of the factors which are not A. The null set corresponds to zero. Each particular set in the partition can be counted as the number one, and the combination of both partitions (even in a single world where A is an empty set) is two. Thus, for any particular possible world W , the quantities 0, 1, 2 are necessarily present. Taking the von Neumann construction, immediately we find N, thence (using addi- tive inverses) Z, so also (taking ratios) Q and (summing convergent power series) R; where Z provides unit-stepped mileposts in R. That is, a structured core of quantities will be present in any W , and we may regard mathematics as the study of the logic of structure and quantity. Extensions to the hyperreals R" follow by construction of some H that has as reciprocal h = 1 H closer to 0 than 1 n for any n in N. Therefore, relationships and linked operations across such quantities will also be present, or may be constructed as needed. Illustrating, after Abraham Robinson (Robinson, 1966), hyperreals allow calculus to be treated as extensions of algebra in R". Thus, while bare distinct identity and coherence focused on quantities will not cause things by the inherent potential or action of such entities, they instead are logical constraints on being and are tied to what can or must be or cannot be or happens not to be. So, too, we may see that the abstract logic model worlds that we may construct then lead to key entities that if necessary are framework to any possible world; thus applicable to our common world. By contrast, if certain quantities and relationships are merely part of the contingencies of some W !! that is close enough to our own, they may provide adequate analogies for mod- elling. As a result, we have good reason to expect that mathe- matical reasoning and core entities will in many cases be highly relevant to and have powerful predictive power for our common world. Robinson, Abraham (1966). Non-Standard Analysis. Ams- terdam: North-Holland Publishing Company. Wigner, Eugene (1960). “The Unreasonable E"ectiveness of Mathematics in the Natural Sciences”. In: Communica- tions in Pure and Applied Mathematics 13.1, pp. 1–14. doi: 10.1002/cpa.3160130102. Independence Conservation and Evolutionary Algorithms Eric Holloway DOI: 10.33014/issn.2640-5652.2.1.holloway.2 Levin’s Law of Independence Conservation Leonid Levin’s 1984 article (Levin, 1984) is the first to this author’s knowledge to prove a fully stochastic conservation of information law. Levin titled his law ’independence con- servation’ which he considered fairly obvious, describing it as “Torturing an uninformed witness cannot give informa- tion about the crime!” Levin’s law is not well known, which is unfortunate since the more commonly known conservation laws are focused either only on the random or deterministic case. Levin’s law is remarkable because it unifies both the random and deterministic cases, showing that the combination also can- not result in information increase. The second remarkable thing about his law is how easy it is to prove, given some preliminaries about algorithmic information. Volume 2, Issue 1 Independence Conservation and Evolutionary Algorithms 33 Algorithmic Information Theory Background First is required the notion of algorithmic information, which is defined on bitstrings. Algorithmic information is the length of the shortest program that generates a partic- ular bitstring. K (x) := min y |U (y)=x |y |. (1) The shortest program is itself known as the elegant program for that particular bitstring. Each bitstring has a unique elegant program. y" := arg min y |U (y)=x |y |. (2) All programs either terminate after a fixed amount of time, or never terminate. All the programs in question are known as prefix free, which means that no terminating program begins another terminating program. Algorithmic mutual information is the length of this pro- gram if we are also provided another bitstring as input, subtracted from the length if we are not provided the extra input bitstring. I (x : y) := K (y) # K (y |x). (3) Unfortunately, this basic definition of algorithmic mutual information is only symmetric under a logarithmic error, because we have to mark where one bitstring starts and the other ends. This requires a number of bits logarithmic on the size of the shortest bitstring, which is x in this case. I (x : y) # I (y : x) = O(log(x)). (4) We can improve the definition of algorithmic mutual infor- mation to be completely symmetric under a constant that is independent of the bitstrings we are looking at, which in other words means we don’t have to worry about the con- stant and the algorithmic mutual information is symmetric as far as we are concerned. This improvement is to use the elegant program of the input bitstring instead of the bitstring itself. I"(x : y) := K (y) # K (y |x"). (5) Since the elegant program halts once it has generated the input bistring, we know we can start on the next bitstring, so we avoid having to encode the bitstring length. This saves us from having to use the logarithimic term. I"(x : y) # I"(y : x) = O(1). (6) One final fascinating point on algorithmic information is that we can also use it to create a universal distribution. m(x) := 2#K (x) . (7) “Universal” means is that we have a distribution that pro- vides the highest probability for every bitstring possible, within a multiplicative constant, under the assumption that we are only dealing with computable generating sources for the bitstrings. m(x) $ p(x) "O(1). (8) The computable distribution assumption is a reasonable as- sumption for dealing with physical phenomena, since (as far as we know) everything physical can be modeled to theo- retically perfect accuracy with enough computational re- sources. Proving Levin’s Deterministic Law Alright, so now onto proving Levin’s law. We first start with a simple lemma, that providing more information can only decrease conditional algorithmic in- formation. In other words, the more we know about y, the less information we need to describe y. K (y |x) $ K (y |x, z) +O(1). (9) We now introduce another simple lemma that with a pro- gram to generate x, namely z which we execute with Turing machine U to generate x, x = U (z), (10) 34 Letters and Notes we can generate both x and z. Thus, the joint information is the same between z and x, z. K (z) = K (x, z) +O(1). (11) This also means to generate the triple {y, x, z} we only need y and z. K (y, x, z) = K (y, z) +O(1). (12) Since it is the case that K (y |x, z) = K (y, x, z) # K (x, z). (13) Then performing replacements to Equation 13 with Equa- tions 11 and 12, we get K (y |x, z) = K (y, z) # K (z) (14) = K (y |z). (15) Combining Equations 9 and 14 shows us that x can never tell us more about y than z. K (y |x) $ K (y |x, z) (16) = K (y |z). (17) We can then use Equation 16 to show running a program f on i does not increase mutual information with y. The notation U ( f .i) to mean we’ve run program f with input i using a universal Turing machine U. First we decompose the mutual information. I"( f (i) : y) = I"(U ( f .i) : y) (18) = K (y) # K (y |U ( f .i)). (19) (20) Now, we set z = f .i and x = U (z) = U ( f .i), and then apply Equation 16 to Equation 18. I"( f (i) : y) = I"(x : y) (21) = K (y) # K (y |x) (22) % K (y) # K (y |x, z) (23) = K (y) # K (y |z) (24) = I"(z : y) (25) = I"( f , i : y). (26) Giving the final concise result, I"( f (i) : y) % I"( f , i : y). (27) This Equation 27 states that executing function f on in- put i does not produce any more information about y than the function and input before they are executed. In other words, running a program doesn’t produce any information. Proving Levin’s Random Law Now with the deterministic version out of the way, we can move onto the random version. The random version asks, what if we generate f randomly, could that result in an information gain? This question is based on the fact that generating f randomly will result in an f with a lot of algorithmic information, since it will be incompressible. So, even though running U ( f .i) doesn’t give us anything new, the initial selection of f may start us o" with a good amount of information about y. Levin’s second step in proving the random law shows this intuition is false. To prove the second law, we will rely on the dominance property of the universal distribution in Equation 8. ! f p( f )I"( f , i : y) = ! f p( f ) log2 m( f , i |y) m( f , i) (28) % ! f p( f ) log2 m( f , i |y) m( f )m(i) (29) % log2 ! f p( f )m( f , i |y) m( f )m(i) (30) % log2 " f m( f , i |y) m(i) (31) = log2 m(i |y) m(i) (32) = K (i) # K (i |y) (33) = I"(i : y) (34) Volume 2, Issue 1 CrowdRank: A Simple Ranking Algorithm for Crowdsourced Rating Systems with Uneven Participation 35 Which gives us the result that randomly generating an f is not expected to provide any information about y. ! f p( f )I"( f , i : y) % I"(i : y). (35) To wrap up the independency conservation law, we apply Equation 27 to Equation 35. ! f p( f )I"( f (i) : y) % ! f p( f )I"( f , i : y) % I"(i : y). (36) Evolutionary Algorithms What sort of impact, if any, does the law of independency conservation in Equation 36 have on evolutionary algo- rithms? One of the simplest implications is that if there is a target area independently designated by y, then it is not possi- ble to randomly evolve population i towards y without any fitness information. However, there are also implications even if there is fitness information provided for the evolution of i. Let’s say that f represents one round of an evolutionary algorithm applied to i, which consists of the following steps: 1. crossover population 2. vary population 3. select population i is defined as a population of bitstrings selected at random. We then define y as the set of bitstrings rated at a certain level of fitness. Part of f stays constant, and another part is varied ran- domly, such as mutation and which bitstring sections are crossed. We denote the random part as r. This gives us a surprising result. ! r p(r)I"( f (i, r) : y) % I"( f , i : y). (37) Equation 37 states that each round of randomized evolution provides no further information about the fitness region y than already existed in the initial conditions of the original population i and the evolutionary algorithm f . Thus, this equation proves that evolutionary algorithms cannot gen- erate algorithmic mutual information, even in regards to regions specified according to fitness. Levin, Leonid A (1984). “Randomness conservation inequal- ities; information and independence in mathematical theories”. In: Information and Control 61.1, pp. 15–37. CrowdRank: A Simple Ranking Algorithm for Crowdsourced Rating Systems with Uneven Participation Jonathan Bartlett DOI: 10.33014/issn.2640-5652.2.1.bartlett.3 Introduction Public rating systems are di!cult to score well. Voting systems tend to simply favor what is already popular. Av- eraging systems tend to have significant variance if there are not enough people scoring. For instance, let’s say that I run a songwriting contest and have 100 entries. I then put it out to a public vote on the Internet to see who wins. Most people are not going to lis- ten to all 100 songs. If I do a simple “thumbs up” approach and count how many votes a song has, then whichever song- writer has the best existing following will simply tell their fans to vote for them, and it will simply devolve into a popularity contest. Let’s say instead I do a rating system where you can rate a song between 0 and 100. Now, songs by popular artists will actually be negatively weighted because they will have more visibility for negative ratings. It is not hard for a few votes to be all 100s, but it is hard for a thousand votes to be that way. Thus, those who have fewer ratings have an advantage.