An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a $\Pi _{1}^{0}$ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y ⊆ ω there is an X in P such that X ⩾wtt Y. We show that this is also equivalent to the $\Pi _{1}^{0}$ class's being large (...) in some sense. We give an example of how this result can be used in the study of scattered linear orders. (shrink)

This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible (...) ∃-theories. (shrink)

An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a Π₁⁰ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y⊆ω there is an X in P such that X≥wtt Y. We show that this is also equivalent to the Π₁⁰ class's being large in some sense. We give (...) an example of how this result can be used in the study of scattered linear orders. (shrink)

This paper continues the study of the metric topology on $2^{\mathbb {N}}$ that was introduced by S. Binns. This topology is induced by a directional metric where the distance from $Y\in2^{\mathbb {N}}$ to $X\in2^{\mathbb {N}}$ is given by \[\limsup_{n}\frac{C(X\upharpoonright n|Y\upharpoonright n)}{n}.\] This definition is closely related to the notions of effective Hausdorff and packing dimensions. Here we establish that this is a path-connected topology on $2^{\mathbb {N}}$ and that under it the functions $X\mapsto\operatorname{dim}_{\mathcal{H}}X$ and $X\mapsto\operatorname{dim}_{p}X$ are continuous. We also (...) investigate the scalar multiplication operation that was introduced by Binns. The multiplication of a real $X\in2^{\mathbb {N}}$ by an element $\alpha\in[0,1]$ represents a dilution of the information in $X$ by a factor of $\alpha$ . Our main result is to show that every regular real is the dilution of a real of Hausdorff dimension 1. That is, that the information in every regular real can be maximally compressed. (shrink)

We investigate the notion of hyperimmunity with respect to how it can be applied to Π{\sp 0}{\sb 1} classes and their Muchnik degrees. We show that hyperimmunity is a strong enough concept to prove the existence of Π{\sp 0}{\sb 1} classes with intermediate Muchnik degree—in contrast to Post's attempts to construct intermediate c.e. degrees.

As government pressure on major technology companies builds, both firms and legislators are searching for technical solutions to difficult platform governance puzzles such as hate speech and misinformation. Automated hash-matching and predictive machine learning tools – what we define here as algorithmic moderation systems – are increasingly being deployed to conduct content moderation at scale by major platforms for user-generated content such as Facebook, YouTube and Twitter. This article provides an accessible technical primer on how algorithmic moderation works; examines some (...) of the existing automated tools used by major platforms to handle copyright infringement, terrorism and toxic speech; and identifies key political and ethical issues for these systems as the reliance on them grows. Recent events suggest that algorithmic moderation has become necessary to manage growing public expectations for increased platform responsibility, safety and security on the global stage; however, as we demonstrate, these systems remain opaque, unaccountable and poorly understood. Despite the potential promise of algorithms or ‘AI’, we show that even ‘well optimized’ moderation systems could exacerbate, rather than relieve, many existing problems with content policy as enacted by platforms for three main reasons: automated moderation threatens to further increase opacity, making a famously non-transparent set of practices even more difficult to understand or audit, further complicate outstanding issues of fairness and justice in large-scale sociotechnical systems and re-obscure the fundamentally political nature of speech decisions being executed at scale. (shrink)

The ever-increasing application of algorithms to decision-making in a range of social contexts has prompted demands for algorithmic accountability. Accountable decision-makers must provide their decision-subjects with justifications for their automated system’s outputs, but what kinds of broader principles should we expect such justifications to appeal to? Drawing from political philosophy, I present an account of algorithmic accountability in terms of the democratic ideal of ‘public reason’. I argue that situating demands for algorithmic accountability within this justificatory framework enables us to (...) better articulate their purpose and assess the adequacy of efforts toward them. (shrink)

Decisions based on algorithmic, machine learning models can be unfair, reproducing biases in historical data used to train them. While computational techniques are emerging to address aspects of these concerns through communities such as discrimination-aware data mining and fairness, accountability and transparency machine learning, their practical implementation faces real-world challenges. For legal, institutional or commercial reasons, organisations might not hold the data on sensitive attributes such as gender, ethnicity, sexuality or disability needed to diagnose and mitigate emergent indirect discrimination-by-proxy, such (...) as redlining. Such organisations might also lack the knowledge and capacity to identify and manage fairness issues that are emergent properties of complex sociotechnical systems. This paper presents and discusses three potential approaches to deal with such knowledge and information deficits in the context of fairer machine learning. Trusted third parties could selectively store data necessary for performing discrimination discovery and incorporating fairness constraints into model-building in a privacy-preserving manner. Collaborative online platforms would allow diverse organisations to record, share and access contextual and experiential knowledge to promote fairness in machine learning systems. Finally, unsupervised learning and pedagogically interpretable algorithms might allow fairness hypotheses to be built for further selective testing and exploration. Real-world fairness challenges in machine learning are not abstract, constrained optimisation problems, but are institutionally and contextually grounded. Computational fairness tools are useful, but must be researched and developed in and with the messy contexts that will shape their deployment, rather than just for imagined situations. Not doing so risks real, near-term algorithmic harm. (shrink)

Let ${\mathcal{P}_s}$ be the lattice of degrees of non-empty ${\Pi_1^0}$ subsets of 2 ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in ${\mathcal{P}_s}$ . Cenzer and Hinman proved that ${\mathcal{P}_s}$ is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by (...) Cenzer and Hinman, we improve on the result of Binns and Simpson by showing that for any ${\mathcal{U} < _s \mathcal{V}}$ , we can lattice embed FD(ω) into ${\mathcal{P}_s}$ strictly between ${deg_s(\mathcal{U})}$ and ${deg_s({\mathcal V})}$ . We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made. (shrink)

The incredible achievements of modern scientific theories lead most of us to embrace scientific realism: the view that our best theories offer us at least roughly accurate descriptions of otherwise inaccessible parts of the world like genes, atoms, and the big bang. In Exceeding Our Grasp, Stanford argues that careful attention to the history of scientific investigation invites a challenge to this view that is not well represented in contemporary debates about the nature of the scientific enterprise. The historical record (...) of scientific inquiry, Stanford suggests, is characterized by what he calls the problem of unconceived alternatives. Past scientists have routinely failed even to conceive of alternatives to their own theories and lines of theoretical investigation, alternatives that were both well-confirmed by the evidence available at the time and sufficiently serious as to be ultimately accepted by later scientific communities. Stanford supports this claim with a detailed investigation of the mid-to-late 19th century theories of inheritance and generation proposed in turn by Charles Darwin, Francis Galton, and August Weismann. He goes on to argue that this historical pattern strongly suggests that there are equally well-confirmed and scientifically serious alternatives to our own best theories that remain currently unconceived. Moreover, this challenge is more serious than those rooted in either the so-called pessimistic induction or the underdetermination of theories by evidence, in part because existing realist responses to these latter challenges offer no relief from the problem of unconceived alternatives itself. Stanford concludes by investigating what positive account of the spectacularly successful edifice of modern theoretical science remains open to us if we accept that our best scientific theories are powerful conceptual tools for accomplishing our practical goals, but abandon the view that the descriptions of the world around us that they offer are therefore even probably or approximately true. (shrink)

The place of the emotions among the passions -- The analytic of the emotions I -- The analytic of the emotions II -- The dialectic of the emotions -- Pride, arrogance, and humility -- Shame, embarrassment, and guilt -- Envy -- Jealousy -- Anger -- Love -- Friendship -- Sympathy and empathy.

Let w and M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π1 0 subsets of 2ω, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of w . We show that many countable distributive lattices are lattice-embeddable below any non-zero element of M.

The property of smallness for Π01 classes is introduced and is investigated with respect to Medvedev and Muchnik degree. It is shown that the property of containing a small Π01 class depends only on the Muchnik degree of a Π01 class. A comparison is made with the idea of thinness for Π01 classesmsthm.

The property of smallness for Π0 1 classes is introduced and is investigated with respect to Medvedev and Muchnik degree. It is shown that the property of containing a small Π0 1 class depends only on the Muchnik degree of a Π0 1 class. A comparison is made with the idea of thinness for Π0 1 classesmsthm.

BackgroundIndividuals with mind-wandering experience their attention decoupling from their main task at hand while others with flow experience fully engage in their task with the optimum experience. There seems to be a negative relationship between mind-wandering and flow. However, it remains unclear to what extent mind-wandering exerts an impact on flow. And it is also elusive whether physical activity and mindfulness, which are as important factors that affected individuals’ attentional control and psychological health, are beneficial in explaining the association between (...) mind-wandering and flow. The current study investigated the relationship between mind-wandering and flow, and the potential mediation effects of physical activity and mindfulness in this association.MethodsA cross-sectional exploratory study design, including multiple scales such as the Mind-Wandering Questionnaire, the International Physical Activity Questionnaire Short Form, Mindfulness Attention and Awareness Scale, and the Short Dispositional Flow Scale was applied. Descriptive statistics and bivariate correlation coefficients were applied in the analysis of these data. A multiple mediation model was used to examine the relationships between mind-wandering, flow, physical activity, and mindfulness.ResultsMind-wandering was inversely associated with physical activity, mindfulness and flow, respectively; and flow was positively related to physical activity and mindfulness, respectively. Moreover, multiple mediation results demonstrated that physical activity and mindfulness, respectively, mediated the relationship between mind-wandering and flow.ConclusionThese findings are helpful to understand how our minds attend to the present moment, and the crucial roles of physical activity and mindfulness in the association between mind-wandering and flow. An implication of these is the possibility that the effective strategies aimed at enhancing both the levels of physical activity and mindfulness are needed to reduce the negative impact of mind-wandering on flow. (shrink)

We use the notions of effective dimension and Kolmogorov complexity to describe a geometry on the set of infinite binary sequences. Geometric concepts that we define and use include angle, projections and scalar multiplication. A question related to compressibility is addressed using these ideas.

The concept of normal is so familiar that it can be hard to imagine contemporary life without it. Yet the term entered everyday speech only in the mid-twentieth century. Before that, it was solely a scientific term used primarily in medicine to refer to a general state of health and the orderly function of organs. But beginning in the middle of the twentieth century, normal broke out of scientific usage, becoming less precise and coming to mean a balanced condition to (...) be maintained and an ideal to be achieved. In Normality, Peter Cryle and Elizabeth Stephens offer an intellectual and cultural history of what it means to be normal. They explore the history of how communities settle on any one definition of the norm, along the way analyzing a fascinating series of case studies in fields as remote as anatomy, statistics, criminal anthropology, sociology, and eugenics. Cryle and Stephens argue that since the idea of normality is so central to contemporary disability, gender, race, and sexuality studies, scholars in these fields must first have a better understanding of the context for normality. This pioneering book moves beyond binaries to explore for the first time what it does—and doesn’t—mean to be normal. (shrink)

We consider two axioms of second-order arithmetic. These axioms assert, in two different ways, that infinite but narrow binary trees always have infinite paths. We show that both axioms are strictly weaker than Weak König's Lemma, and incomparable in strength to the dual statement (WWKL) that wide binary trees have paths.

We divide the class of infinite computable trees into three types. For the first and second types, 0' computes a nontrivial self-embedding while for the third type 0'' computes a nontrivial self-embedding. These results are optimal and we obtain partial results concerning the complexity of nontrivial self-embeddings of infinite computable trees considered up to isomorphism. We show that every infinite computable tree must have either an infinite computable chain or an infinite Π01 antichain. This result is optimal and has connections (...) to the program of reverse mathematics. (shrink)

SummaryOn purely logical grounds, if hypothesis H can be eliminated, then so too must its logical complement, H', be confirmed. The Asymmetry Theory, if true, must therefore be not formal but substantial. This cannot be established by the “two‐tier” view which requires symmetrical generalisation of theory terms and observation data. Even singular observations before being usable require a theory of accidents, a theory of errors, already built in to them before they can falsify hypotheses. This explains the inconsistency of Popper's (...) Simplicity criterion and his notion of a priori probability. Conclusion: Falsificationists cannot condemn verifiability without condemning themselves at the same time. (shrink)

An Interdisciplinary Approach to Cognitive Modelling presents a new approach to cognition that challenges long-held views. It systematically develops a broad-based framework to model cognition, which is mathematically equivalent to the emerging 'quantum-like modelling' of the human mind. The book argues that a satisfactory physical and philosophical basis of such an approach is missing, a particular issue being the application of quantization to the mind for which there is no empirical evidence as yet. In response to this issue, the book (...) adopts a COM (classical optical modelling) approach, broad-based but mathematically equivalent to quantum-like modelling while avoiding its problematic features. It presents a philosophically informed and empirically motivated mathematical model of cognition, mainly concerning decision making processes. It also deals with applications to different areas of the social sciences. It will be of interest to scholars and research students interested in the mathematical modelling of cognition and decision making, and also interdisciplinary researchers interested in broader issues of cognition. (shrink)

This study concerns the ideas of one particular philosopher, Henri Bergson, whose views of time, intuition, and creativity have had a significant impact on art, literature, and the humanities, both in his time and in our own. Although it is generally recognized that Bergson's ideas have significantly impacted the arts and the humanities, it has not been recognized how they have also had a creative influence on the sciences as well. Nor has it been realized that this was one of (...) his most basic contentions. Bergson's conception of intuition--his fundamental insight into reality--was not limited to fugitive insights into human existence. By realizing previously unsuspected possibilities for research and discovery, his endeavors were also meant to make possible new advances in the sciences. If it enabled his cousin by marriage, Marcel Proust, to explore human memory in depth, it also inspired psychologists like Daniel Schachter to use Bergson's ideas to make real contributions to contemporary memory science. If his notion of creative evolution brought many thinkers to a belief in human creative freedom, it brought others (notably Alexis Carrel and Pierre Lecomte de Noüy) to a scientific study of biological time. Among his successful speculations was the theory of the Big Bang cosmology. 'Getting Bergson Straight' shows many points at which Bergson's ideas anticipated future developments in the sciences. This was seen clearly by the Nobel Prize-winning physicist Luis de Broglie who viewed Bergson's physics as presaging quantum physics. Thus, the text is well situated for arts, humanities, social science, and natural science classrooms studying creative thinking and/or intellectual history. (shrink)