The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure theinformation contentof sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question (...) is equivalent to: Given a computer with access to an oracle which will answer membership questions about a setA, can a program be written which will correctly compute the answers to all membership questions about a setB? If the answer is yes, then we say thatBisTuring reducibletoAand writeB≤TA. We say thatB≡TAifB≤TAandA≤TB. ≡Tis an equivalence relation, and ≤Tinduces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called thedegrees of unsolvability, and elements of this poset are calleddegrees.Post was particularly interested in computability from sets which are partially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer. (shrink)

We show that the Π 4 -theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.

We examine the sequences A that are low for dimension, i.e. those for which the effective dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf random sequence has effective dimension (...) 1 relative to A, and lowishness for K, namely, that the limit of KA/K is 1. We show that there is a perfect [Formula: see text]-class of low for dimension sequences. Since there are only countably many low for random sequences, many more sequences are low for dimension. Finally, we prove that every low for dimension is jump-traceable in order nε, for any ε > 0. (shrink)

Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove that there are no (...) deep degrees other than the recursive one. Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turning functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that $(W \bigoplus A)'$ is forced to disagree with Φ(-; A'). The conversion has some ambiguity; in particular, A cannot be found uniformly from W. We also show that there is a "moderately" deep degree: There is a low nonzero degree whose join with any other low degree is not high. (shrink)

The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory.We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. (...) A tower is maximal if there is no infinite computable set contained in all $G_n$. A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R, there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$. Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones.We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $\Delta ^0_2$ -set does so.We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. (shrink)

This paper considers reductions between types of numberings; these reductions preserve the Rogers Semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the k+1-r.e. numberings; all further reductions are obtained by (...) concatenating these reductions. (shrink)

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...) disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)

We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

In lieu of an abstract, here is a brief excerpt of the content:Reviewed by:Redeeming a Prison Society: A Liturgical and Sacramental Response to Mass Incarceration by Amy LevadLloyd SteffenRedeeming a Prison Society: A Liturgical and Sacramental Response to Mass Incarceration Amy Levad minneapolis: fortress press, 2014. 233 pp. $39.00.Amy Levad (University of St. Thomas) has added a theological voice to the national conversation that Michelle Alexander opened with her devastating critique of the American criminal justice system in The New Jim (...) Crow: Mass Incarceration in the Age of Colorblindness. Alexander showed how policies grounded in the war on drugs have disproportionately distressed racial and ethnic minorities—African Americans and Latinos—and the poor, destroying lives and communities. Incarceration in the United States is today a system that perpetuates what Alexander called a “caste” system from which escape is, especially among black males, virtually impossible. In this informed and well-presented study, Levad takes up Alexander’s social justice analysis, extending it in new directions, offering a creative theological contribution to the mass incarceration crisis in the world’s first “genuine prison society.”Levad observes that a limitation in the Christian response to mass incarceration is the “lack of Catholic voices” (47), which her book makes an effort to correct. She draws on core insights of Catholic tradition to address conditions that foster crime while also responding “to the ways in which the criminal justice crisis both reflects and sustains social injustices” (48). Her book offers a wonderfully clear analysis of mass incarceration and related issues such as recidivism strategies and policing policies. She advocates “pulling levers,” policing policies that aim at avoiding prison, versus harsh “window-breaking” policies that for deterrence reasons criminalize even minor offences. Levad addresses theories of punishment, proposes ideas for prison reform, and, while acknowledging a limited need for prisons, sets forth constructive suggestions for how best to decarcerate society through restorative justice and rehabilitation practices that reintegrate offenders into society.The study is a provocative interdisciplinary conversation between criminology and theology. Levad’s focus is on liturgy and sacrament, the central resources of Roman Catholic theology, finding in the Eucharist the theological [End Page 204] model for inviting the marginalized and dispossessed into the common fellowship of human dignity. She then argues that penance and reconciliation yield attitudes and behaviors that parallel secular restorative justice efforts. Advocating alternatives to prison while denying the effectiveness of punitive retribution, Levad critiques the approaches of the US Conference of Catholic Bishops and other Catholics. She highlights Kathryn Soltis as a Catholic scholar who uses theological resources to affirm the dignity of prisoners, attend to the common good, and seek ways to repair relationships between victims and offenders.Some of Levad’s ideas could be developed further. Pluralism, for instance, is mentioned as a contextual issue for her theological work but never thoroughly developed. Utilitarianism is denied a constructive ethics role, but Levad’s discussion of recidivism appeals to it as a marker of the common good (122). And Levad’s attention to the internal failures of the Church in confronting social justice issues leads one to wonder whether the decarcerated vision of society she desires is practicable.Levad speaks to the heart of the incarceration crisis in America, challenging the willingness of Americans to “throw people away” (198) through imprisonment—especially the young, the poor, and minorities. With her underlying question of “what kind of people we want to be and what we want our communities to be like” (43), Levad presents readers with a distinctive “vision of justice in God’s reign conveyed by liturgy and sacraments” (197). With that, she has accomplished what she set out to do: confront the social injustice of mass incarceration with the best insights of modern criminology but also with a theological perspective that embodies the struggle to realize an engaged Catholic praxis of justice.Lloyd SteffenLehigh UniversityCopyright © 2016 Society of Christian Ethics... (shrink)

R. Suszko’s Sentential Calculus with Identity \( SCI \) results from classical propositional calculus \( CPC \) by adding a new connective \(\equiv \) and axioms for identity \(\varphi \equiv \psi \) (which we interpret here as ‘propositional identity’). We reformulate the original semantics of \( SCI \) using Boolean prealgebras which, introduced in different ways, are known in the literature as structures for the modeling of (hyper-) intensional semantics. We regard intensionality here as a measure for the discernibility of (...) propositions (and hyperintensionality as a high degree of intensionality). As concrete examples of \( SCI \) -based intensional modeling, we review and study algebraic semantics of some Lewis-style modal logics in the vicinity of \( S3 \) and present conditions under which those modal systems can be restored, in a precise sense, as certain axiomatic extensions of \( SCI \). This generalizes work of Suszko which is focused on the modal systems \( S4 \) and \( S5 \). Our approach is particularly intended as a proposal to consider and to further study \( SCI \) (and its extensions) as a general framework for the modeling of (hyper-) intensional semantics. (shrink)

This dissertation is highly motivated by d.r.e. Nondensity Theorem, which is interesting in two perspectives. One is that it contrasts Sacks Density Theorem, and hence shows that the structures of r.e. degrees and d.r.e. degrees are different. The other is to investigate what other properties a maximal degree can have.In Chapter 1, we briefly review the backgrounds of Recursion Theory which motivate the topics of this dissertation.In Chapter 2, we introduce the notion of $$ -cupping degree. It is closely (...) related to the notion of maximal d.r.e. degree. In fact, a $$ -cupping degree is maximal d.r.e. degree. We then prove that there exists an isolated $$ -cupping degree by combining strategies for maximality and isolation with some efforts.Chapter 3 is part of a joint project with Steffen Lempp, Yiqun Liu, Keng Meng Ng, Cheng Peng, and Guohua Wu. In this chapter, we prove that any finite boolean algebra can be embedded into d.r.e. degrees as a final segment. We examine the proof of d.r.e. Nondensity Theorem and make developments to the technique to make it work for our theorem. The goal of the project is to see what lattice can be embedded into d.r.e. degrees as a final segment, as we observe that the technique has potential be developed further to produce other interesting results.prepared by Yong Liu.E-mail: [email protected]. (shrink)

In this paper, I take up the question to what extent and in which sense we can conceive of Johannes Baptista Van Helmont’s (1579-1644) style of experimenting as “modern”. Connected to this question, I shall reflect upon what Van Helmont’s precise contribution to experimental practice was. I will argue - after analysing some of Van Helmont's experiments such as his tree-experiment, ice-experiment, and thermoscope experiment - that Van Helmont had a strong preference to locate experimental designs in places wherein variables (...) can be more easily controlled (and in the limit, in relatively closed physical systems such as paradigmatically the vessel, globe or sphere (vas, globus, sphera)). After having reviewed some alternative candidates, I shall argue that Van Helmont’s usage of relatively isolated physical systems and a moderate degree of quantification, whereby mathematical procedures mainly refer to guaranteeing that quantities are conserved by roughly determining them, are the characteristics that best captures his contributions to “modern” experimentation. (shrink)

This article responds to critical reflections on my Beyond Presidentialism and Parliamentarism by Sarah Birch, Kevin J. Elliott, Claudia Landwehr and James L. Wilson. It discusses how different types of representative democracy, especially different forms of government (presidential, parliamentary or hybrid), can be justified. It clarifies, among other things, the distinction between procedural and process equality, the strengths of semi-parliamentary government, the potential instability of constitutional designs, and the difference that theories can make in actual processes of constitutional reform.

How fast? How strong? How many? So what? Why do numbers matter in biology? Chromatin binding proteins are forever in motion, exchanging rapidly between bound and free pools. How do regulatory systems whose components are in constant flux ensure stability and flexibility? This review explores the application of quantitative and mathematical approaches to mechanisms of epigenetic regulation. We discuss methods for measuring kinetic parameters and protein quantities in living cells, and explore the insights that have been gained by quantifying (...) and modelling dynamics of chromatin binding proteins. (shrink)

It is not an easy task to review two recently published books by and about the late Jewish scholar Francesca Yardenit Albertini, who passed away so suddenly in 2011 at the young age of thirty-six.Albertini was not only a dear colleague with whom one felt connected through a common aim and vision resulting from a shared Jewish and philosophical perspective. She was also an enthusiastic scholar and lecturer with whom one would have liked to work on projects of mutual (...) scholarly interest, such as the Wissenschaft des Judentums movement. In addition she was, and as her own writings and her biography so vividly demonstrate, clearly a rather complex personality and a woman of very strong.. (shrink)

We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a Σ03-condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n≥ 1 in ω, there exists a computable tree of finite height which is δ0n+1-categorical but (...) not δ0n-categorical. (shrink)

Volume 19, Issue 9, September 2019, Page W1-W2.

The two books discussed here make important contributions to our understanding of the role of spacetime concepts in physical theories and how that understanding has changed during the evolution of physics. Both emphasize what can be called a ‘dynamical’ account, according to which geometric structures should be understood in terms of their roles in the laws governing matter and force. I explore how the books contribute to such a project; while generally sympathetic, I offer criticisms of some historical claims concerning (...) Newton, and argue that the dynamical account does not undercut ontological issues as the books claim. *Received January 2009; revised March 2009. †To contact the author, please write to: Department of Philosophy, 1423 University Hall MC 267, University of Illinois at Chicago, 601 S. Morgan Street, Chicago, IL 60607; e‐mail: [email protected]. (shrink)