The weakly random reals contain not only the Schnorr random reals as a subclass but also the weakly 1-generic reals and therefore the n -generic reals for every n . While the class of Schnorr random reals does not overlap with any of these classes of generic reals, their degrees may. In this paper, we describe the extent to which this is possible for the Turing, weak truth-table, and truth-table degrees and then extend our analysis to the Schnorr random (...) and hyperimmune reals. (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)

Demuth tests generalize Martin-Löf tests in that one can exchange the m-th component a computably bounded number of times. A set fails a Demuth test if Z is in infinitely many final versions of the Gm. If we only allow Demuth tests such that GmGm+1 for each m, we have weak Demuth randomness.We show that a weakly Demuth random set can be high and , yet not superhigh. Next, any c.e. set Turing below a Demuth random set is (...) strongly jump-traceable.We also prove a basis theorem for non-empty classes P. It extends the Jockusch–Soare basis theorem that some member of P is computably dominated. We use the result to show that some weakly 2-random set does not compute a 2-fixed point free function. (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 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 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.

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, (...) respectively. We focus on the countable distributive lattices P w and P s of weak and strong degrees of mass problems given by nonempty Π 1 0 subsets of 2 ω . Using an abstract Gödel/Rosser incompleteness property, we characterize the Π 1 0 subsets of 2 ω whose associated mass problems are of top degree in P w and P s , respectively. Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within P w . Namely, we characterize r as the unique largest weak degree of a Π 1 0 subset of 2 ω of positive measure. Within P w we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect Π 1 0 subsets of 2 ω . In addition, we present other natural examples of intermediate degrees in P w . We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory. (shrink)

An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL- (...) class='Hi'>randomness. Our first main result states that KL-random sequences are close to Martin-Löf random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Löf random. A key lemma in the proof of this result is that for every effective split of a KL-random sequence at least one of the halves is Martin-Löf random. However, this splitting property does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Löf random and, second, for any computable, nondecreasing, and unbounded function g and almost all n, the prefix of A of length n has prefix-free Kolmogorov complexity at least n−g. Again, the latter property does not characterize KL-randomness, even when restricted to left-r.e. sequences; we construct a left-r.e. sequence that has this property but is not KL-stochastic and, in fact, is not even Mises–Wald–Church stochastic.Turning our attention to KL-stochasticity, we construct a non-empty class of KL-stochastic sequences that are not weakly 1-random; by the usual basis theorems we obtain such sequences that in addition are left-r.e., are low, or are of hyperimmune-free degree.Our second main result asserts that every KL-stochastic sequence has effective dimension 1, or equivalently, a sequence cannot be KL-stochastic if it has infinitely many prefixes that can be compressed by a factor of α<1. This improves on a result by Muchnik, who has shown that were they to exist, such compressible prefixes could not be found effectively. (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)

We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity. We also consider Low(M, Kurtz), the class of degrees a such that every element of M is a-Kurtz random. These are characterised when M is the class of Martin-Löf random, computably random, or Schnorr (...) random reals. We show that Low(ML, Kurtz) coincides with the non-DNR degrees, while both Low(CR, Kurtz) and Low(Schnorr, Kurtz) are exactly the non-high, non-DNR degrees. (shrink)

We investigate the role of continuous reductions and continuous relativization in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to van Lambalgen’s theorem and the Miller–Yu/Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterizations of lowness for Martin-Löf randomness. We also characterize computing higher [Formula: see (...) text]-trivial sets by higher random sequences. We give a separation between higher notions of randomness, in particular between higher weak 2-randomness and [Formula: see text]-randomness. To do so we investigate classes of functions computable from Kleene’s [Formula: see text] based on strong forms of the higher limit lemma. (shrink)

We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.

We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f$ is R-random, then x is R-random as well. (...) If additionally f is known to have bounded variation, then we show f has Luzin’s if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset '$ -Kurtz randomness. This links classical real analysis with algorithmic randomness. (shrink)

We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f$ is R-random, then x is R-random as well. (...) If additionally f is known to have bounded variation, then we show f has Luzin’s if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset '$ -Kurtz randomness. This links classical real analysis with algorithmic randomness. (shrink)

Let ${2-\textsf{RAN}}$ be the statement that for each real X a real 2-random relative to X exists. We apply program extraction techniques we developed in Kreuzer and Kohlenbach (J. Symb. Log. 77(3):853–895, 2012. doi:10.2178/jsl/1344862165), Kreuzer (Notre Dame J. Formal Log. 53(2):245–265, 2012. doi:10.1215/00294527-1715716) to this principle. Let ${{\textsf{WKL}_0^\omega}}$ be the finite type extension of ${\textsf{WKL}_0}$ . We obtain that one can extract primitive recursive realizers from proofs in ${{\textsf{WKL}_0^\omega} + \Pi^0_1-{\textsf{CP}} + 2-\textsf{RAN}}$ , i.e., if ${{\textsf{WKL}_0^\omega} + \Pi^0_1-{\textsf{CP}} + 2-\textsf{RAN} (...) \, {\vdash} \, \forall{f}\, {\exists}{x} A_{qf}(f,x)}$ then one can extract from the proof a primitive recursive term t(f) such that ${A_{qf}(f,t(f))}$ . As a consequence, we obtain that ${{\textsf{WKL}_0}+ \Pi^0_1 - {\textsf{CP}} + 2-\textsf{RAN}}$ is ${\Pi^0_3}$ -conservative over ${\textsf{RCA}_0}$. (shrink)

The Contextuality-by-Default approach to determining and measuring the (non)contextuality of a system of random variables requires that every random variable in the system be represented by an equivalent set of dichotomous random variables. In this paper we present general principles that justify the use of dichotomizations and determine their choice. The main idea in choosing dichotomizations is that if the set of possible values of a random variable is endowed with a pre-topology (V-space), then the allowable dichotomizations split the space (...) of possible values into two linked subsets (“linkedness” being a weak form of pre-topological connectedness). We primarily focus on two types of random variables most often encountered in practice: categorical and real-valued ones (including continuous random variables, greatly underrepresented in the contextuality literature). A categorical variable (one with a finite number of unordered values) is represented by all of its possible dichotomizations. If the values of a random variable are real numbers, then they are dichotomized by intervals above and below a variable cut point. (shrink)

We define $\Psi $ -autoreducible sets given an autoreduction procedure $\Psi $. Then, we show that for any $\Psi $, a measurable class of $\Psi $ -autoreducible sets has measure zero. Using this, we show that classes of cototal, uniformly introenumerable, introenumerable, and hyper-cototal enumeration degrees all have measure zero. By analyzing the arithmetical complexity of the classes of cototal sets and cototal enumeration degrees, we show that weakly 2-random sets cannot be cototal and weakly 3-random sets cannot be of (...) cototal enumeration degree. Then, we see that this result is optimal by showing that there exists a 1-random cototal set and a 2-random set of cototal enumeration degree. For uniformly introenumerable degrees and introenumerable degrees, we utilize $\Psi $ -autoreducibility again to show the optimal result that no weakly 3-random sets can have introenumerable enumeration degree. We also show that no 1-random set can be introenumerable. (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)

We call A weakly low for K if there is a c such that $K^A(\sigma)\geq K(\sigma)-c$ for infinitely many σ; in other words, there are infinitely many strings that A does not help compress. We prove that A is weakly low for K if and only if Chaitin's Ω is A-random. This has consequences in the K-degrees and the low for K (i.e., low for random) degrees. Furthermore, we prove that the initial segment prefix-free complexity of 2-random reals is infinitely (...) often maximal. This had previously been proved for plain Kolmogorov complexity. (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)

In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence. We strengthen these results by showing that every Demuth random sequence computes a 1-generic sequence and that every Demuth random sequence forms a minimal pair with every pb-generic sequence. Moreover, we prove that for every (...) comeager${\cal G} \subseteq {2^\omega }$, there is some weakly 2-random sequenceXthat computes some$Y \in {\cal G}$, a result that allows us to provide a fairly complete classification as to how various notions of effective randomness interact in the Turing degrees with various notions of effective genericity. (shrink)

This paper presents the results of an experiment on mutual versus common knowledge of advice in a two-player weak-link game with random matching. Our experimental subjects play in pairs for thirteen rounds. After a brief learning phase common to all treatments, we vary the knowledge levels associated with external advice given in the form of a suggestion to pick the strategy supporting the payoff-dominant equilibrium. Our results are somewhat surprising and can be summarized as follows: in all our treatments (...) both the choice of the efficiency-inducing action and the percentage of efficient equilibrium play are higher with respect to the control treatment, revealing that even a condition as weak as mutual knowledge of level 1 is sufficient to significantly increase the salience of the efficient equilibrium with respect to the absence of advice. Furthermore, and contrary to our hypothesis, mutual knowledge of level 2 induces, under suitable conditions, successful coordination more frequently than common knowledge. (shrink)

We present a comparatively simple way to construct Martin-Löf random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of Gács and Kučera, for any given set X we construct a Martin-Löf random set from which X can be decoded effectively. By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-Löf random sets that are computably enumerable self-reducible. (...) The two latter results complement the known facts that no rec-random set is truth-table autoreducible and that no Martin-Löf random set is Turing-autoreducible [8, 24]. (shrink)

Given a countable graph, we say a set A of its vertices is universal if it contains every countable graph as an induced subgraph, and A is weakly universal if it contains every finite graph as an induced subgraph. We show that, for almost every graph on, (1) every set of positive upper density is universal, and (2) every set with divergent reciprocal sums is weakly universal. We show that the second result is sharp (i.e., a random graph on will (...) almost surely contain non‐universal sets with divergent reciprocal sums) and, more generally, that neither of these two results holds for a large class of partition regular families. (shrink)

Chaos in nervous system is a fascinating but controversial field of investigation. To approach the role of chaos in the real brain, we theoretically and numerically investigate the occurrence of chaos inartificial neural networks. Most of the time, recurrent networks (with feedbacks) are fully connected. This architecture being not biologically plausible, the occurrence of chaos is studied here for a randomly diluted architecture. By normalizing the variance of synaptic weights, we produce a bifurcation parameter, dependent on this variance and on (...) the slope of the transfer function, that allows a sustained activity and the occurrence of chaos when reaching a critical value. Even for weak connectivity and small size, we find numerical results in accordance with the theoretical ones previously established for fully connected infinite sized networks. The route towards chaos is numerically checked to be a quasi-periodic one, whatever the type of the first bifurcation is. Our results suggest that such high-dimensional networks behave like low-dimensional dynamical systems. (shrink)

Sub-Saharan emerging countries experience electrical shortages resulting in power rationing, which ends up hampering economic activities. This paper proposes an approach for very short-term blackout forecast in grid-tied PV systems operating in low reliability weak electric grids of emerging countries. A pilot project was implemented in Arusha-Tanzania; it mainly comprised of a PV-inverter and a lead-acid battery bank connected to the local electricity utility company, Tanzania Electric Supply Company Limited. A very short-term power outage prediction model framework based on (...) a hybrid random forest algorithm was developed using open-source Python machine learning libraries and using a dataset generated from the pilot project’s experimental microgrid. Input data sampled at a 15-minute interval included day of the month, weekday, hour, supply voltage, utility line frequency, and previous days’ blackout profiles. The model was composed of an adaptive similar day module that predicts 15 minutes ahead from a sliding window lookup table spanning 2 weeks prior to the prediction target day, after which ASD prediction was fused with RF prediction, giving a final optimised RF-ASD blackout prediction model. Furthermore, the efficacy analysis of the short-term blackout prediction of the formulated RF, ASD, and RF-ASD regression and classification algorithms was compared. Considering the stochastic nature of blackouts, their performance was found to be fair in short-term blackout predictions of the test site’s weak grid using limited input data from the point of coupling of the user. The models developed were only able to predict blackouts if they occurred frequently and contiguously, but they performed poorly if they were sparse or dispersed. (shrink)

We study inversions of the jump operator on ${\mathrm{\Pi }}_{1}^{0}$ classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. (...) A further application is the complete solution of [24, Problem 3.6.9]: one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails. Finally we discuss various techniques for coding information into incomplete randoms. Using these techniques we give a negative answer to [24, Problem 8.2.14]: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable. (shrink)

We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event [Formula: see text] such that if [Formula: see text] then X has an infinite subset Y such that no element of [Formula: see text] is Turing computable from Y.

An illustrated exploration of fandom that combines academic essays with artist pages and experimental texts. Fandom as Methodology examines fandom as a set of practices for approaching and writing about art. The collection includes experimental texts, autobiography, fiction, and new academic perspectives on fandom in and as art. Key to the idea of “fandom as methodology” is a focus on the potential for fandom in art to create oppositional spaces, communities, and practices, particularly from queer perspectives, but also through transnational, (...) feminist and artist-of-color fandoms. The book provides a range of examples of artists and writers working in this vein, as well as academic essays that explore the ways in which fandom can be theorized as a methodology for art practice and art history. Fandom as Methodology proposes that many artists and art writers already draw on affective strategies found in fandom. With the current focus in many areas of art history, art writing, and performance studies around affective engagement with artworks and imaginative potentials, fandom is a key methodology that has yet to be explored. Interwoven into the academic essays are lavishly designed artist pages in which artists offer an introduction to their use of fandom as methodology. Contributors Taylor J. Acosta, Catherine Grant, Dominic Johnson, Kate Random Love, Maud Lavin, Owen G. Parry, Alice Butler, SooJin Lee, Jenny Lin, Judy Batalion, Ika Willis. Artists featured in the artist pages Jeremy Deller, Ego Ahaiwe Sowinski, Anna Bunting-Branch, Maria Fusco, Cathy Lomax, Kamau Amu Patton, Holly Pester, Dawn Mellor, Michelle Williams Gamaker, The Women of Colour Index Reading Group, Liv Wynter, Zhiyuan Yang. (shrink)

The strong weak truth table (sw) reducibility was suggested by Downey, Hirschfeldt, and LaForte as a measure of relative randomness, alternative to the Solovay reducibility. It also occurs naturally in proofs in classical computability theory as well as in the recent work of Soare, Nabutovsky, and Weinberger on applications of computability to differential geometry. We study the sw-degrees of c.e. reals and construct a c.e. real which has no random c.e. real (i.e., Ω number) sw-above it.

We develop arithmetical measure theory along the lines of Lutz [10]. This yields the same notion of measure 0 set as considered before by Martin-Löf, Schnorr, and others. We prove that the class of sets constructible by r.e.-constructors, a direct analogue of the classes Lutz devised his resource bounded measures for in [10], is not equal to RE, the class of r.e. sets, and we locate this class exactly in terms of the common recursion-theoretic reducibilities below K. We note that (...) the class of sets that bounded truth-table reduce to K has r.e.-measure 0, and show that this cannot be improved to truth-table. For Δ2-measure the borderline between measure zero and measure nonzero lies between weak truth-table reducibility and Turing reducibility to K. It follows that there exists a Martin-Löf random set that is tt-reducible to K, and that no such set is btt-reducible to K. In fact, by a result of Kautz, a much more general result holds. (shrink)

We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.

I discuss here a number of different kinds of diachronic emergence, noting that they differ in important ways from synchronic conceptions. I argue that Bedau’s weak emergence has an essentially historical aspect, in that there can be two indistinguishable states, one of which is weakly emergent, the other of which is not. As a consequence, weak emergence is about tokens, not types, of states. I conclude by examining the question of whether the concept of weak emergence is (...) too weak and note that there is at present no unifying account of diachronic and synchronic concepts of emergence. (shrink)

For given Boolean algebras$\mathbb {A}$and$\mathbb {B}$we endow the space$\mathcal {H}(\mathbb {A},\mathbb {B})$of all Boolean homomorphisms from$\mathbb {A}$to$\mathbb {B}$with various topologies and study convergence properties of sequences in$\mathcal {H}(\mathbb {A},\mathbb {B})$. We are in particular interested in the situation when$\mathbb {B}$is a measure algebra as in this case we obtain a natural tool for studying topological convergence properties of sequences of ultrafilters on$\mathbb {A}$in random extensions of the set-theoretical universe. This appears to have strong connections with Dow and Fremlin’s result stating (...) that there are Efimov spaces in the random model. We also investigate relations between topologies on$\mathcal {H}(\mathbb {A},\mathbb {B})$for a Boolean algebra$\mathbb {B}$carrying a strictly positive measure and convergence properties of sequences of measures on$\mathbb {A}$. (shrink)

We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the class $superhigh^\diamond$ and show that it contains some, but not all, of the noncomputable K-trivial sets.

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoning is the bounded arithmetic theory [math] of [E. Jeřábek, Approximate counting by hashing in bounded arithmetic, J. Symb. Log. 74(3) (2009) 829–860]. In particular, the Ramsey and weak pigeonhole search problems lie in the new class. We give a purely (...) computational characterization of this class and show that, relative to an oracle, it does not contain the problem CPLS, a strengthening of PLS. As CPLS is provably total in the theory [math], this shows that [math] does not prove every [math] sentence which is provable in bounded arithmetic. This answers the question posed in [S. Buss, L. A. Kołodziejczyk and N. Thapen, Fragments of approximate counting, J. Symb. Log. 79(2) (2014) 496–525] and represents some progress in the program of separating the levels of the bounded arithmetic hierarchy by low-complexity sentences. Our main technical tool is an extension of the “fixing lemma” from [P. Pudlák and N. Thapen, Random resolution refutations, Comput. Complexity, 28(2) (2019) 185–239], a form of switching lemma, which we use to show that a random partial oracle from a certain distribution will, with high probability, determine an entire computation of a [math] oracle machine. The introduction to the paper is intended to make the statements and context of the results accessible to someone unfamiliar with NP search problems or with bounded arithmetic. (shrink)

The thesis of instrumental convergence holds that a wide range of ends have common means: for instance, self preservation, desire preservation, self improvement, and resource acquisition. Bostrom contends that instrumental convergence gives us reason to think that "the default outcome of the creation of machine superintelligence is existential catastrophe". I use the tools of decision theory to investigate whether this thesis is true. I find that, even if intrinsic desires are randomly selected, instrumental rationality induces biases towards certain kinds of (...) choices. Firstly, a bias towards choices which leave less up to chance. Secondly, a bias towards desire preservation, in line with Bostrom's conjecture. And thirdly, a bias towards choices which afford more choices later on. I do not find biases towards any other of the convergent instrumental means on Bostrom's list. I conclude that the biases induced by instrumental rationality at best weakly support Bostrom's conclusion that machine superintelligence is likely to lead to existential catastrophe. (shrink)

The so-called ergodic hierarchy (EH) is a central part of ergodic theory. It is a hierarchy of properties that dynamical systems can possess. Its five levels are egrodicity, weak mixing, strong mixing, Kolomogorov, and Bernoulli. Although EH is a mathematical theory, its concepts have been widely used in the foundations of statistical physics, accounts of randomness, and discussions about the nature of chaos. We introduce EH and discuss its applications in these fields.

This chapter focuses on one of the common fallacies in Western philosophy called ' proof by verbosity (PVB)'. PVB is a favorite device among conspiracy theorists who utilize it to obfuscate the weakness of their case. By supporting their theories with so much random information (and misinformation), it gives the impression that their position is superficially well researched and supported by an avalanche of evidence. Sometimes PVB takes the form of a proof by intimidation, especially when an argument is made (...) using sophisticated insider jargon, or when a complex and long‐winded argument is made by an eminent scholar in the field. In the spirit of overwhelming the opposition, a PVB can be committed by employing a litany of numbers and statistics. Articulating your arguments in a clear and concise fashion and substantiating the position with well‐founded and mutually intelligible premises is the key to avoiding a proof by verbosity. (shrink)

We consider random choice rules that, by satisfying a weak form of Luce’s choice axiom, embody a form probabilistic rationality. We show that for this important class of stochastic choices, the law of demand for normal goods—arguably the main result of traditional consumer theory—continues to hold on average when strictly dominated alternatives are dismissed.