We apply recent ideas about complexity and randomness to the philosophy of laws and chances. We develop two ways to use algorithmic randomness to characterize probabilistic laws of nature. The first, a generative chance* law, employs a nonstandard notion of chance. The second, a probabilistic* constraining law, impose relative frequency and randomness constraints that every physically possible world must satisfy. The constraining notion removes a major obstacle to a unified governing account of non-Humean laws, on which (...) laws govern by constraining physical possibilities; it also provides independently motivated solutions to familiar problems for the Humean best-system account (the Big Bad Bug and the zero-fit problem). On either approach, probabilistic laws are tied more tightly to corresponding sets of possible worlds: some histories permitted by traditional probabilistic laws are now ruled out as physically impossible. Consequently, the framework avoids one variety of empirical underdetermination while bringing to light others that are typically overlooked. (shrink)

We introduce a framework uniting algorithmic randomness with exchangeable credences to address foundational questions in philosophy of probability and philosophy of science. To demonstrate its power, we show how one might use the framework to derive the Principal Principle---the norm that rational credence should match known objective chance---without circularity. The derivation brings together de Finetti's exchangeability, Martin-Löf randomness, Lewis's and Skyrms's chance-credence norms, and statistical constraining laws (arXiv:2303.01411). Laws that constrain histories to algorithmically random sequences naturally pair (...) with exchangeable credences encoding inductive symmetries. Using the de Finetti representation theorem, we show that this pairing directly entails the Principal Principle of this framework. We extend the proof to partial exchangeability and provide finite-history bounds that vanish in the infinite limit. The Principal Principle thus emerges as a mathematical consequence of the alignment between nomological constraints and inductive learning. This reveals how algorithmic randomness and exchangeability can illuminate foundational questions about chance, frequency, and rational belief. (shrink)

According to a traditional view, scientific laws and theories constitute algorithmic compressions of empirical data sets collected from observations and measurements. This article defends the thesis that, to the contrary, empirical data sets are algorithmically incompressible. The reason is that individual data points are determined partly by perturbations, or causal factors that cannot be reduced to any pattern. If empirical data sets are incompressible, then they exhibit maximal algorithmic complexity, maximal entropy and zero redundancy. They are therefore maximally (...) efficient carriers of information about the world. Since, on algorithmic information theory, a string is algorithmically random just if it is incompressible, the thesis entails that empirical data sets consist of algorithmically random strings of digits. Rather than constituting compressions of empirical data, scientific laws and theories pick out patterns that data sets exhibit with a certain noise. (shrink)

Lévy's Upward Theorem says that the conditional expectation of an integrable random variable converges with probability one to its true value with increasing information. In this paper, we use methods from effective probability theory to characterise the probability one set along which convergence to the truth occurs, and the rate at which the convergence occurs. We work within the setting of computable probability measures defined on computable Polish spaces and introduce a new general theory of effective disintegrations. We use this (...) machinery to prove our main results, which (1) identify the points along which certain classes of effective random variables converge to the truth in terms of certain classes of algorithmically random points, and which further (2) identify when computable rates of convergence exist. Our convergence results significantly generalize earlier results within a unifying novel abstract framework, and there are no precursors of our results on computable rates of convergence. Finally, we make a case for the importance of our work for the foundations of Bayesian probability theory. (shrink)

We analyze the pointwise convergence of a sequence of computable elements of L1 in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA0, each is equivalent to the assertion that every Gδ subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Königʼs lemma relativized to the Turing jump of any set. It is also equivalent (...) to the conjunction of the statement asserting the existence of a 2-random relative to any given set and the principle of Σ2 collection. (shrink)

We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}$ of continuous functions on ${2^{\mathbb N}}$. A probability measure is given and a version of the Martin-Löf test for randomness is defined. Random ${\Delta^0_2}$ continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any ${y \in 2^{\mathbb N}}$, (...) there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. (shrink)

The study of Martin‐Löf randomness on a computable metric space with a computable measure has seen much progress recently. In this paper we study Martin‐Löf randomness on a more general space, that is, a computable topological space with a computable measure. On such a space, Martin‐Löf randomness may not be a natural notion because there is no universal test, and Martin‐Löf randomness and complexity randomness (defined in this paper) do not coincide in general. We show (...) that SCT3 is a sufficient condition for the existence and coincidence, and study how much we can weaken this condition. (shrink)

We introduce martingales defined by probabilistic strategies, in which randomness is used to decide whether to bet. We show that different criteria for the success of computable probabilistic strategies can be used to characterize ML-randomness, computable randomness, and partial computable randomness. Our characterization of ML-randomness partially addresses a critique of Schnorr by formulating ML randomness in terms of a computable process rather than a computably enumerable function.

We study the phenomenon of merging of opinions for computationally limited Bayesian agents from the perspective of algorithmic randomness. When they agree on which data streams are algorithmically random, two Bayesian agents beginning the learning process with different priors may be seen as having compatible beliefs about the global uniformity of nature. This is because the algorithmically random data streams are of necessity globally regular: they are precisely the sequences that satisfy certain important statistical laws. By virtue of (...) agreeing on what data streams are algorithmically random, two Bayesian agents can thus be taken to concur on what global regularities they expect to see in the data. We show that this type of compatibility between priors suffices to ensure that two computable Bayesian agents will reach inter-subjective agreement with increasing information. In other words, it guarantees that their respective probability assignments will almost surely become arbitrarily close to each other as the number of observations increases. Thus, when shared by computable Bayesian learners with different subjective priors, the beliefs about uniformity captured by algorithmic randomness provably lead to merging of opinions. (shrink)

Nies and Scholz formalized the notion of an infinite qubitstring and referred to it as a ‘state’. They defined ‘quantum Martin-Löf randomness’ for states. We give a notion of measurement of a state in a computable basis and introduce ‘quantum measurement randomness’, a randomness notion for states. A state is quantum measurement random if measuring it in any computable basis yields a Martin-Löf random bitstring with probability one. Our main result is that quantum Martin-Löf randomness strictly (...) implies quantum measurement randomness. This uses the construction of a quantum measurement random state which is not quantum Martin-Löf random. We prove two general results on which this construction relies: The first concerns Martin-Löf randomness relative to computable measures and extends a result of V. Vovk. The second is a combinatorial result about Kronecker products. (shrink)

A seminal theorem due to Weyl [14] states that if $(a_n)$ is any sequence of distinct integers, then, for almost every $x \in \mathbb{R}$, the sequence $(a_n x)$ is uniformly distributed modulo one. In particular, for almost every $x$ in the unit interval, the sequence $(a_n x)$ is uniformly distributed modulo one for every computable sequence $(a_n)$ of distinct integers. Call such an $x$ UD random. Here it is shown that every Schnorr random real is UD random, but there are (...) Kurtz random reals that are not UD random. On the other hand, Weyl's theorem still holds relative to a particular effectively closed null set, so there are UD random reals that are not Kurtz random. (shrink)

The hybridization of two or more energy sources into a single power station is one of the widely discussed solutions to address the demand and supply havoc generated by renewable production, heating power, and cooling power) and its energy storage issues. Hybrid energy sources work based on the complementary existence of renewable sources. The combined cooling, heating, and power is one of the significant systems and shows a profit from its low environmental impact, high energy efficiency, low economic investment, and (...) sustainability in the industry. This paper presents an economic model of a microgrid system containing the CCHP system and energy storage considering the energy coupling and conversion characteristics, the effective characteristics of each microsource, and energy storage unit is proposed. The random forest regression model was optimized by the gravitational search algorithm. The test results show that the GSA-RFR model improves prediction accuracy and reduces the generalization error. The detail of the MG network and the energy storage architecture connected to the other renewable energy sources is discussed. The mathematical formulation of energy coupling and energy flow of the MG network including wind turbines, photovoltaic, CCHP system, fuel cell, and energy storage devices are presented. The testing system has been analysed under load peak cutting and valley filling of energy utilization index, energy utilization rate, the heat pump, the natural gas consumption of the microgas turbine, and the energy storage unit. The energy efficiency costs were observed as 88.2% and 86.9% with heat pump and energy storage operation comparing with GSA-RFR-based operation costs as 93.2% and 93% in summer and winter season, respectively. The simulation results extended the rationality and economy of the proposed model. (shrink)

In this paper, I evaluate the claim that the equivalence of multiple intensionally distinct definitions of random sequence provides evidence for the claim that these definitions capture the intuitive conception of randomness, concluding that the former claim is false. I then develop an alternative account of the significance of randomness-theoretic equivalence results, arguing that they are instances of a phenomenon I refer to as schematic equivalence. On my account, this alternative approach has the virtue of providing the plurality (...) of definitions of randomness with conceptual unity and a rationale for certain investigations that are carried out in the field. (shrink)

The $\Omega $ numbers—the halting probabilities of universal prefix-free machines—are known to be exactly the Martin-Löf random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-Löf random left-c.e. real $\alpha $, a universal prefix-free machine U whose halting probability is $\alpha $. We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real $\alpha $, one cannot uniformly produce a left-c.e. real $\beta $ such that $\alpha - \beta $ is neither left-c.e. (...) nor right-c.e. (shrink)

Although information content is invariant up to an additive constant, the range of possible additive constants applicable to programming languages is so large that in practice it plays a major role in the actual evaluation of K(s), the Kolmogorov complexity of a string s. We present a summary of the approach we've developed to overcome the problem by calculating its algorithmic probability and evaluating the algorithmic complexity via the coding theorem, thereby providing a stable framework for Kolmogorov complexity (...) even for short strings. We also show that reasonable formalisms produce reasonable complexity classifications. (shrink)

The Art of Randomness teaches readers to harness the power of randomness (and Python code) to solve real-world problems in programming, science, and art through hands-on experiments-from simulating evolution to encrypting messages to making machine-learning algorithms. Each chapter describes how randomness plays into the given topic area, then proceeds to demonstrate its problem-solving role with hands-on experiments to work through using Python code.

Evolutionary computation (EC) refers to a family of population-based optimisation algorithms that iteratively modify candidate solutions through selection, variation, and fitness-guided search. EC is often presented as an in silico analogue of natural selection, yet its representational status remains unsettled. This raises not only technical questions but also philosophical concerns about how metaphors mediate our understanding of computation and shape societal imaginaries of AI. We reassess EC by integrating model theory, accounts of emergence, and the philosophy of algorithmicity, and by (...) situating its evolutionary language alongside Artificial Life and the existential risk discourse in AI. We argue that EC is best understood as an algorithmic metaphor and a mediating model: representationally modest yet instrumentally powerful for optimisation. The novelty it produces is task-bounded and exemplifies weak emergence arising from high-dimensional search, deceptive fitness landscapes, and interactions among operators and hyperparameters. Randomness in EC is engineered through seeds, distributions, and stopping criteria, which supports auditability and responsibility while introducing epistemic opacity for explanation and communication. Building on these results, we propose a three-axis framework that maps EC and neighbouring traditions by representational commitment, emergence scope, and randomness governance. The framework yields practical communication guidelines, including explicit boundary statements about what is and is not being modelled, audience signalling for public-facing contexts, reproducibility disclosures, and reframing from “evolution” to “population-based search” where appropriate. In this way, EC contributes methodological insight without overclaiming biological equivalence and supports responsible discourse. At the same time, we show how evolutionary metaphors shape public perceptions of inevitability in AI, underscoring the need for careful boundary-setting in both expert and societal communication. (shrink)

Recently, certain philosophers of mathematics (Fallis [1997]; Womack and Farach [(1997]) have argued that there are no epistemic considerations that should stop mathematicians from using probabilistic methods to establish that mathematical propositions are true. However, mathematicians clearly should not use methods that are unreliable. Unfortunately, due to the fact that randomized algorithms are not really random in practice, there is reason to doubt their reliability. In this paper, I analyze the prospects for establishing that randomized algorithms are reliable. I end (...) by arguing that it would be inconsistent for mathematicians to suspend judgement on the truth of mathematical propositions on the basis of worries about the reliability of randomized algorithms. (shrink)

Algorithmic randomness was originally defined for Cantor space with the fair-coin measure. Recent work has examined algorithmic randomness in new contexts, in particular closed subsets of 2ɷ ([2] and [8]). In this paper we use the probability theory of closed set-valued random variables (RACS) to extend the definition of Martin-Löf randomness to spaces of closed subsets of locally compact, Hausdorff, second countable topological spaces. This allows for the study of Martin-Löf randomness in many new (...) spaces, but also gives a new perspective on Martin-Löf randomness for 2ɷ and on the algorithmically random closed sets of [2] and [8]. The first half of this paper is devoted to developing the machinery of Martin-Löf randomness for general spaces of closed sets. We then prove some general results and move on to show how the algorithmically random closed sets of [2] and [8] fit into this new framework. (shrink)

Algorithms have become a widespread trope for making sense of social life. Science, finance, journalism, warfare, and policing—there is hardly anything these days that has not been specified as “algorithmic.” Yet, although the trope has brought together a variety of audiences, it is not quite clear what kind of work it does. Often portrayed as powerful yet inscrutable entities, algorithms maintain an air of mystery that makes them both interesting and difficult to understand. This article takes on this problem (...) and examines the role of algorithms not as techno-scientific objects to be known, but as a figure that is used for making sense of observations. Following in the footsteps of Harold Garfinkel’s tutorial cases, I shall illustrate the implications of this view through an experiment with algorithmic navigation. Challenging participants to go on a walk, guided not by maps or GPS but by an algorithm developed on the spot, I highlight a number of dynamics typical of reasoning with running code, including the ongoing respecification of rules and observations, the stickiness of the procedure, and the selective invocation of the algorithm as an intelligible object. The materials thus provide an opportunity to rethink key issues at the intersection of the social sciences and the computational, including popular concerns with transparency, accountability, and ethics. (shrink)

I will propose the notion that the universe is digital, not as a claim about what the universe is made of but rather about the way it unfolds. Central to the argument will be the concepts of symmetry breaking and algorithmic probability, which will be used as tools to compare the way patterns are distributed in our world to the way patterns are distributed in a simulated digital one. These concepts will provide a framework for a discussion of the (...) informational nature of reality. I will argue that if the universe were analog, then the world would likely be random, making it largely incomprehensible. The digital model has, however, an inherent beauty in its imposition of an upper limit and in the convergence in computational power to a maximal level of sophistication. Even if deterministic, that it is digital doesnít mean that the world is trivial or predictable, but rather that it is built up from operations that at the lowest scale are very simple but that at a higher scale look complex and even random, though only in appearance. (shrink)

The probability ranking conclusion is an extension of the absolute form evaluation conclusion. Firstly, the random simulation evaluation model is introduced; then, the general idea of converting the traditional evaluation method to the random simulation evaluation model is analyzed; on this basis, based on the rule of “further ensuring the stability of the ranking chain on the basis of increasing the possibility of the ranking chain,” two methods of solving the probability ranking conclusion are given. Based on the rule of (...) “further guaranteeing the stability of the ranking chain on the basis of improving the likelihood of the ranking chain,” two methods are given to solve the likelihood conclusion. This paper argues that this absolute form of conclusion hinders the approximation of the theory to the essence of the actual problem and is an important reason for the problem of “non-consistency of multi-evaluation conclusions.” To address this problem, a stochastic simulation-based comprehensive evaluation solution algorithm based on the idea of “Monte Carlo simulation” is proposed, and the corresponding ranking method is investigated, which is characterized by generating evaluation conclusions with probability information, and thus has more advantages than the absolute conclusion form in terms of problem interpretability. The method is characterized by the generation of evaluation conclusions with probabilistic information and thus has more advantages than the absolute conclusion form in terms of problem interpretation. Because of the independence of the stochastic simulation solution method, it is applied to the “bottom-up” evaluation model as an example, and a novel autonomous evaluation method is constructed. Finally, the application of the stochastic simulation evaluation model is illustrated by an example and compared with the absolute form evaluation. The evaluation model is an extension of the traditional evaluation model, which can further broaden the practical application of comprehensive evaluation theory. (shrink)

Recently, a connection has been established between two branches of computability theory, namely between algorithmic randomness and algorithmic learning theory. Learning-theoretical characterizations of several notions of randomness were discovered. We study such characterizations based on the asymptotic density of positive answers. In particular, this note provides a new learning-theoretic definition of weak 2-randomness, solving the problem posed by (Zaffora Blando, Rev. Symb. Log. 2019). The note also highlights the close connection between these characterizations and the (...) problem of convergence on random sequences. (shrink)

Numerous learning tasks can be described as the process of extrapolating patterns from observed data. One of the driving intuitions behind the theory of algorithmic randomness is that randomness amounts to the absence of any effectively detectable patterns: it is thus natural to regard randomness as antithetical to inductive learning. Osherson and Weinstein [11] draw upon the identification of randomness with unlearnability to introduce a learning-theoretic framework (in the spirit of formal learning theory) for modelling (...) algorithmic randomness. They define two success criteria—specifying under what conditions a pattern may be said to have been detected by a computable learning function—and prove that the collections of data sequences on which these criteria cannot be satisfied respectively correspond to the set of weak 1-randoms and the set of weak 2-randoms. This learning-theoretic approach affords an intuitive perspective on algorithmic randomness, and it invites the question of whether restricting attention to learning-theoretic success criteria comes at an expressivity cost. In other words, is the framework expressive enough to capture most core algorithmic randomness notions and, in particular, Martin-Löf randomness—arguably, the most prominent algorithmic randomness notion in the literature? In this paper, we answer the latter question in the affirmative by providing a learning-theoretic characterisation of Martin-Löf randomness. We then show that Schnorr randomness, another central algorithmic randomness notion, also admits a learning-theoretic characterisation in this setting. (shrink)

This work contributes to the program of studying effective versions of “almost-everywhere” theorems in analysis and ergodic theory via algorithmic randomness. Consider the setting of Cantor space {0,1}N with the uniform measure and the usual shift. We determine the level of randomness needed for a point so that multiple recurrence in the sense of Furstenberg into effectively closed sets P of positive measure holds for iterations starting at the point. This means that for each k∈N there is (...) an n such that n,2n,…,kn shifts of the point all end up in P. We consider multiple recurrence into closed sets that possess various degrees of effectiveness: clopen, Π10 with computable measure, and Π10. The notions of Kurtz, Schnorr, and Martin-Löf randomness, respectively, turn out to be sufficient. We obtain similar results for multiple recurrence with respect to the k commuting shift operators on {0,1}Nk. (shrink)

A semimeasure is a generalization of a probability measure obtained by relaxing the additivity requirement to superadditivity. We introduce and study several randomness notions for left-c.e. semimeasures, a natural class of effectively approximable semimeasures induced by Turing functionals. Among the randomness notions we consider, the generalization of weak 2-randomness to left-c.e. semimeasures is the most compelling, as it best reflects Martin-Löf randomness with respect to a computable measure. Additionally, we analyze a question of Shen, a positive (...) answer to which would also have yielded a reasonable randomness notion for left-c.e. semimeasures. Unfortunately, though, we find a negative answer, except for some special cases. (shrink)

Early work on the frequency theory of probability made extensive use of the notion of randomness, conceived of as a property possessed by disorderly collections of outcomes. Growing out of this work, a rich mathematical literature on algorithmic randomness and Kolmogorov complexity developed through the twentieth century, but largely lost contact with the philosophical literature on physical probability. The present chapter begins with a clarification of the notions of randomness and probability, conceiving of the former as (...) a property of a sequence of outcomes, and the latter as a property of the process generating those outcomes. A discussion follows of the nature and limits of the relationship between the two notions, with largely negative verdicts on the prospects for any reduction of one to the other, although the existence of an apparently random sequence of outcomes is good evidence for the involvement of a genuinely chancy process. (shrink)

We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅. We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C ≥ |x|-c. The ‘only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we (...) prove some results on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. (shrink)

This article explores the connection between objective chance and the randomness of a sequence of outcomes. Discussion is focussed around the claim that something happens by chance iff it is random. This claim is subject to many objections. Attempts to save it by providing alternative theories of chance and randomness, involving indeterminism, unpredictability, and reductionism about chance, are canvassed. The article is largely expository, with particular attention being paid to the details of algorithmic randomness, a topic (...) relatively unfamiliar to philosophers. (shrink)

The book is intended to explain the larger and intuitive concept of randomness by means of computation, particularly through algorithmic complexity and recursion theory. It also includes the transcriptions (by A. German) of two panel discussion on the topics: Is The Universe Random?, held at the University of Vermont in 2007; and What is Computation? (How) Does Nature Compute?, held at the University of Indiana Bloomington in 2008. The book is intended to the general public, undergraduate and graduate (...) students in math, computer science, physics and other sciences, but also to philosophers of science and researchers. (shrink)

Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not (...) Martin-Löf random, and provide a new characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-Löf random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of "Schnorr reducibility" which allows us to calibrate the Schnorr complexity of reals. We define the class of "Schnorr trivial" reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members. (shrink)

In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle . The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ . While the Hippocratic approach is in general much more restrictive, (...) there are cases where the two coincide. The first author showed in 2010 that in the particular case where the notion of randomness considered is Martin-Löf randomness and the measure λ is a Bernoulli measure, classical randomness and Hippocratic randomness coincide. In this paper, we prove that this result no longer holds for other notions of randomness, namely computable randomness and stochasticity. (shrink)

Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is possible. What estimators are good for this? In this work, we consider estimators given by a familiar notion of universal coding for stationary ergodic measures, while working in the framework of algorithmic randomness, i.e., we are particularly interested in (...) prediction of Martin-Löf random points. We outline the general theory and exhibit some counterexamples. Completing a result of Ryabko from 2009 we also show that universal probability measure in the sense of universal coding induces a universal predictor in the prequential sense. Surprisingly, this implication holds true provided the universal measure does not ascribe too low conditional probabilities to individual symbols. As an example, we show that the Prediction by Partial Matching measure satisfies this requirement with a large reserve. (shrink)

This book constitutes the refereed proceedings of the 14th International Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014, held in Copenhagen, Denmark, in July 2014. The 33 papers were carefully reviewed and selected from a total of 134 submissions. The papers present original research and cover a wide range of topics in the field of design and analysis of algorithms and data structures including but not limited to approximation algorithms, parameterized algorithms, computational biology, computational geometry and topology, distributed algorithms, (...) external-memory algorithms, exponential algorithms, graph algorithms, online algorithms, optimization algorithms, randomized algorithms, streaming algorithms, string algorithms, sublinear algorithms and algorithmic game theory. (shrink)

In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$, $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated (...) with this ordering, the Levin–V’yugin degrees, can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin–V’yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V’yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide two examples of the use of this technique by explicating a result of V’yugin’s about the LV-degree of the collection of Martin-Löf random sequences and extending the result to the LV-degree of the collection of sequences of DNC degree. (shrink)

The multimedia technology and computer technology supported by the development of modern science and technology provide an important platform for the development of college physical education teaching activities. To better play the role of network auxiliary teaching platform in college sports teaching and improve the effectiveness of college sports teaching, the construction method of multimedia auxiliary teaching effect evaluation model based on the random number forest algorithm is proposed. Through the specification of the random forest algorithm and the optimization of (...) the teaching quality evaluation index, the auxiliary teaching level of the college physical education network is analyzed, and the evaluation of the multimedia auxiliary teaching effect of the physical education courses is completed. The experimental results verify the effectiveness of the evaluation model designed in this article, with a user satisfaction of 72%. Teachers and students can use the evaluation model to improve the teaching quality and teaching efficiency, improve the management work, and promote the scientific, standardization, and specialization of physical education teaching management in colleges and universities. (shrink)

With the continuous development of the stock market, designing a reasonable risk identification tool will help to solve the irrational problem of investors. This paper first selects the stocks with the most valuable investment value in the future through the random forest algorithm in the nine-factor model and then analyzes them by using the higher-order moment model to find that different investors’ preferences will make the weight of the portfolio change accordingly, which will eventually make the optimal return and risk (...) set of the composition of the portfolio change. The risk identification system designed in this paper can provide an effective risk identification tool for investors and help them make rational judgments. (shrink)

We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$-random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C-incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable (...) randoms is equivalent to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-Löf randoms, and we describe a sense in which this result is nearly optimal. (shrink)

We study the sets that are computable from both halves of some (Martin–Löf) random sequence, which we call 1/2-bases. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.e. elements. It is a proper subideal of the K-trivial sets. We characterize 1/2-bases as the sets computable from both halves of Chaitin’s Ω, and as the sets that obey the cost function c(x,s)=Ωs−Ωx−−−−−−−√. Generalizing these results yields a dense hierarchy of (...) subideals in the K-trivial degrees: For k<n, let Bk/n be the collection of sets that are below any k out of n columns of some random sequence. As before, this is an ideal generated by its c.e. elements and the random sequence in the definition can always be taken to be Ω. Furthermore, the corresponding cost function characterization reveals that Bk/n is independent of the particular representation of the rational k/n, and that Bp is properly contained in Bq for rational numbers p<q. These results are proved using a generalization of the Loomis–Whitney inequality, which bounds the measure of an open set in terms of the measures of its projections. The generality allows us to analyze arbitrary families of orthogonal projections. As it turns out, these do not give us new subideals of the K-trivial sets; we can calculate from the family which Bp it characterizes. We finish by studying the union of Bp for p<1; we prove that this ideal consists of the sets that are robustly computable from some random sequence. This class was previously studied by Hirschfeldt [D. R. Hirschfeldt, C. G. Jockusch, R. Kuyper and P. E. Schupp, Coarse reducibility and algorithmic randomness, J. Symbolic Logic81(3) (2016) 1028–1046], who showed that it is a proper subclass of the K-trivial sets. We prove that all such sets are robustly computable from Ω, and that they form a proper subideal of the sets computable from every (weakly) LR-hard random sequence. We also show that the ideal cannot be characterized by a cost function, giving the first such example of a Σ03 subideal of the K-trivial sets. (shrink)

Purpose The purpose of this paper is to report on empirical work conducted to open up algorithmic interpretability and transparency. In recent years, significant concerns have arisen regarding the increasing pervasiveness of algorithms and the impact of automated decision-making in our lives. Particularly problematic is the lack of transparency surrounding the development of these algorithmic systems and their use. It is often suggested that to make algorithms more fair, they should be made more transparent, but exactly how this (...) can be achieved remains unclear. Design/methodology/approach An empirical study was conducted to begin unpacking issues around algorithmic interpretability and transparency. The study involved discussion-based experiments centred around a limited resource allocation scenario which required participants to select their most and least preferred algorithms in a particular context. In addition to collecting quantitative data about preferences, qualitative data captured participants’ expressed reasoning behind their selections. Findings Even when provided with the same information about the scenario, participants made different algorithm preference selections and rationalised their selections differently. The study results revealed diversity in participant responses but consistency in the emphasis they placed on normative concerns and the importance of context when accounting for their selections. The issues raised by participants as important to their selections resonate closely with values that have come to the fore in current debates over algorithm prevalence. Originality/value This work developed a novel empirical approach that demonstrates the value in pursuing algorithmic interpretability and transparency while also highlighting the complexities surrounding their accomplishment. (shrink)

William Dembski claims to have established a decision process to determine when highly unlikely events observed in the natural world are due to Intelligent Design. This article argues that, as no implementable randomness test is superior to a universal Martin-Löf test, this test should be used to replace Dembski's decision process. Furthermore, Dembski's decision process is flawed, as natural explanations are eliminated before chance. Dembski also introduces a fourth law of thermodynamics, his “law of conservation of information,” to argue (...) that information cannot increase by natural processes. However, this article, using algorithmic information theory, shows that this law is no more than the second law of thermodynamics. The article concludes that any discussions on the possibilities of design interventions in nature should be articulated in terms of the algorithmic information theory approach to randomness and its robust decision process. (shrink)