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)

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 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)

One of the predominant debates in AI Ethics is the worry and necessity to create fair, transparent and accountable algorithms that do not perpetuate current social inequities. I offer a critical analysis of Reuben Binns’s argument in which he suggests using public reason to address the potential bias of the outcomes of machine learning algorithms. In contrast to him, I argue that ultimately what is needed is not public reason per se, but an audit of the implicit moral assumptions (...) of societies within which algorithms are built and applied. Public justification is appealing since it offers us the possibility to align the decision-making outcomes of the algorithm with the core moral values of stakeholders within a constitutional democratic society. My concern is that the common moral principles that form the foundation of public reason are not necessarily neutral, as they still express specific moral ideals and normative standards even if there is moral agreement by society as a whole, or among different stakeholders within society. Appealing to such normative standards may thus still lead to algorithmic outcomes being biased as common moral values may very well still be discriminatory even though they are formed from a consensus, and even if public reason is applied as a kind of filter for potential algorithmic outcomes. Hence, I argue that these implicit moral norms within society that we take as a given in public reasoning, need to be audited from generation to generation in order to effectively mitigate potential algorithmic bias. (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.

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)

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)

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)

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 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.

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.

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)

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.

Now in a third edition, Introduction to Philosophy: Classical and Contemporary Readings is a highly acclaimed, topically organized collection that covers five major areas of philosophy--theory of knowledge, philosophy of religion, philosophy of mind, freedom and determinism, and moral philosophy. Editor Louis P. Pojman enhances the text's topical organization by arranging the selections into a pro/con format to help students better understand opposing arguments. He also includes accessible introductions to each chapter, subsection, and individual reading, a unique feature for an (...) anthology of this depth. While the book focuses on a compelling sampling of classical material--including selections from Plato, Aristotle, Descartes, Locke, Berkeley, Hume, and Kant--it also incorporates some of philosophy's best twentieth-century and contemporary work, featuring articles by Bertrand Russell, Richard Taylor, John Searle, Thomas Nagel, and others. This third edition contains an expanded glossary, more extensive section introductions, and twelve new selections: Karl Popper: "Epistemology without a Knowing Subject" Richard Rorty: "Dismantling Truth: Solidarity Versus Objectivity" Daniel Dennett: "Postmodernism and Truth" Bruce Russell: "The Problem of Evil: Too Much Suffering" David Chalmers: "Against Materialism: Can Consciousness Be Reductively Explained?" Baron Paul Henri d'Holbach: "A Defense of Determinism" Michael Levin: "A Compatibilist Defense of Moral Responsibility" Plato: Socratic Morality: "Crito" Herodotus: "Custom Is King" J. L. Mackie: "The Subjectivity of Values" Louis P. Pojman: "A Critique of Mackie's Theory of Moral Subjectivism" Thomas Nagel: "Moral Luck". (shrink)