Author: Damir Dzhafarov

Towards a diversified understanding of computability

Posted on by

Liesbeth De Mol

In this talk I will argue that we should care more for and be more careful with the history of computability making a plea for a more diverse and informed understanding. The starting point will be the much celebrated Turing machine model. Why is it that within the computability community, this model is often considered as the model? In the first part of this talk I review some of those reasons, showing how and why they are in need of a revision based, mostly, on historical arguments. On that basis I argue that, while surely, the Turing machine model is a basic one, part of its supposed superiority over other models is based on socio-historical forces. In part II then, I consider a number of historical, philosophical and technical arguments to support and elaborate the idea of a more diversified understanding of the history of computability. Central to those arguments will be the differentiation between, on the one hand, the logical equivalence between the different models with respect to the computable functions, and, on the other hand, some basic intensional differences between those very same models. To keep the argument clear, the main focus will be on the different models provided by Emil Leon Post but I will also include references to the work by Alonzo Church, Stephen C. Kleene and Haskell B. Curry.

Supported by the PROGRAMme project, ANR-17-CE38-0003-01.

Polynomial-time axioms of choice and polynomial-time cardinality

Posted on by

Josh Grochow

Many versions of the Axiom of Choice (AC), though equivalent in ZF set theory, are inequivalent from the computational point of view. When we consider polynomial-time analogues of AC, many of these different versions can be shown to be equivalent to other more standard questions about the relationship between complexity classes. We will use some of these formulations of AC to motivate several complexity questions that might otherwise seem a bit bespoke and unrelated from one another.

Next, as many versions of AC are about cardinals, in the second half of the talk we introduce a polynomial-time version of cardinality, in the spirit of polynomial-time model theory. As this is a new theory, we will discuss some of the foundational properties of polynomial-time cardinality, some of which may be surprising when contrasted with their set-theoretic counterparts. The talk will contain many open questions, and the paper contains even more! Based on arXiv:2301.07123 [cs.CC].

Interacting alternatives: referential indeterminacy and questions

Posted on by

Floris Roelofsen

One of the major challenges involved in developing semantic theories is that many constructions in natural language given rise to alternatives. Different sources of alternatives have been identified—e.g., questions, indeterminacy, focus, scalarity—and have been investigated in quite some depth. Less attention, however, has been given so far to the question how these different kinds of alternatives interact. I will focus in this talk one one such interaction, namely between referential indeterminacy and questions. Several formal semantic frameworks have been developed to capture referential indeterminacy (dynamic semantics, alternative semantics) and the content of questions (e.g., alternative semantics, structured meanings, partition semantics, inquisitive semantics). I will report on ongoing work with Jakub Dotlacil, which aims to merge dynamic and inquisitive semantics in a principled way. I will present a basic system and suggest some potential applications and extensions.

Logic Done as if Inference in Language Mattered

Posted on by

Larry Moss

Our topic is logical inference in natural language, as it is done by people and computers.
The first main topic will be monotonicity inference, arguably the best of the simple ideas
in the area. Monotonicity can be incorporated in running systems whereby one can take
parsed real-life sentences and see simple inferences in action. I will present some of the
theory, related to higher-order monotonicity and the syntax-semantics interface offered by
categorial grammar.

In a different direction, these days monotonicity inference can be done by machines as well
as humans. The talk also discusses this development along with some ongoing work on the
borderline of natural logic and machine learning.

The second direction in the talk will be an overview of the large number of logical systems for
various linguistic phenomena. This work begins as an updating of traditional syllogistic logic,
but with much greater expressive power.

Overall, the goal of the talk is to persuade you that the research program of “natural logic”
leads to a lively research area with connections to many areas both inside and outside of more
mainstream areas of logic.

Contextual analysis, epistemic probabilities, and paradoxes

Posted on by

Ehtibar Dzhafarov

Contextual analysis deals with systems of random variables. Each random variable within a system is labeled in two ways: by its content (that which the variable measures or responds to) and by its context (conditions under which it is recorded). Dependence of random variables on contexts is classified into (1) direct (causal) cross-influences and (2) purely contextual (non-causal) influences. The two can be conceptually separated from each other and measured in a principled way. The theory has numerous applications in quantum mechanics, and also in such areas as decision making and computer databases. A system of deterministic variables (as a special case of random variables) is always void of purely contextual influences. There are, however, situations when we know that a system is one of a set of deterministic systems, but we cannot know which one. In such situations we can assign epistemic (Bayesian) probabilities to possible deterministic systems, create thereby a system of epistemic random variables, and subject it to contextual analysis. In this way one can treat, in particular, such logical antinomies as the Liar paradox. The simplest systems of epistemic random variables describing the latter have no direct cross-influences and the maximal possible degree of purely contextual influences.

Brouwer, Plato, and classification

Posted on by

Sam Sanders

Classification is an essential part of all the exact sciences, including mathematical logic.
The program Reverse Mathematics classifies theorems of ordinary mathematics according
to the minimal axioms needed for a proof. We show that the current scale, based on
comprehension and discontinuous functions, is not satisfactory as it classifies many
intuitively weak statements, like the uncountability of $\mathbb{R}$ or properties of
the Riemann integral, in the same rather strong class. We introduce an alternative/
complimentary scale with better properties based on (classically valid) continuity
axioms from Brouwer’s intuitionistic mathematics. We discuss how these new
results provide empirical support for Platonism.

What Can Theoretical Computer Science Contribute to the Discussion of Consciousness?

Posted on by

Lenore Blum

We propose a mathematical model, which we call the Conscious Turing Machine (CTM), as a formalization of neuroscientist Bernard Baars’ Theater of Consciousness. The CTM is proposed for the express purpose of understanding consciousness. In settling on this model, we look not for complexity but simplicity, not for a complex model of the brain or cognition but a simple mathematical model sufficient to explain consciousness. Our approach, in the spirit of mathematics and theoretical computer science, proposes formal definitions to fix informal notions and deduce consequences. We are inspired by Alan Turing’s extremely simple formal model of computation that is a fundamental first step in the mathematical understanding of computation. This mathematical formalization includes a precise definition of chunk, a precise description of the competition that Long Term Memory (LTM) processors enter to gain access to Short Term Memory (STM)), and a precise definition of conscious awareness in the model. Feedback enables LTM processors to learn from their mistakes and successes and emerging links enable conscious processing to become unconscious. The reasonableness of the formalization lies in the breadth of concepts that the model explains easily and naturally. The model provides some understanding of the Hard Problem of consciousness, which we explore in the particular case of pain and pleasure. The understanding depends on the dynamics of the CTM, not on chemicals like serotonin, dopamine, and so on. We set ourselves the problem of explaining the feeling of consciousness in ways that apply as well to machines made of silicon and gold as to animals made of flesh and blood. With regard to suggestions for AI, the CTM is well suited to giving succinct explanations for whatever high level decisions it makes. This is because the chunk in STM either articulates an explanation or points to chunks that do.

Logic Group’s Statement on Black Lives Matter

Posted on by

The UConn Logic Group, as a founding and principal member of the Logic Supergroup, is a co-signatory on the Supergroup’s recent Statement on Black Lives Matter. The full statement appears below.

Statement from the Logic Supergroup organizers on Black Lives Matter

The killings of George Floyd and Breonna Taylor by police have resulted in deep sadness and outrage worldwide. This sadness and outrage has swept through academic communities as well. We members of the Logic Supergroup join our colleagues throughout academia in denouncing anti-Black violence in North America specifically, and systemic racism affecting Black, Indigenous, and People of Color generally. We are committed to working with our BIPOC colleagues in logic and with our colleagues in other fields to speak out against injustice and to work to make logic an inclusive community. Black Lives Matter.

In early 2020, logic groups around the world began to combine their meetings into an online Logic Supergroup as a reaction to the coronavirus pandemic. As part of #ShutDownSTEM, the Supergroup held 24 hours of Inclusive Logic on June 10, 2020 to build concrete actions against racism in logic.

Here are four concrete actions that we identified as important and have committed ourselves to immediately, and which we encourage our member groups to commit themselves to as well:

We commit to doing our small part to increase the diversity in logic, as a discipline, by first increasing the diversity represented in our speaker series. We acknowledge that we have, to this point, failed in this regard. We acknowledge, in fact, that we have failed to have a speaker series that even manages to be representative of the diversity that is present in logic, let alone one that contributes to increasing this diversity.Second, we commit to seeking funding from a broad range of sources in order to overcome barriers to participation in the supergroup, and in logic meetings and seminars more broadly. Such funding could be used, for example, in order to allow for graduate student travel stipends if the supergroup holds in-person events in the future, or to aid researchers who need equipment in order to participate in our virtual events now. This will remove some of the barriers faced by BIPOC students to entering and participating in the logic community.

Third, we commit to hosting periodic events to discuss, evaluate, and develop resources for logic education that are inclusive and that encourage participation in logic from a diverse audience. This includes setting regular Logic Supergroup meeting times to discuss further actions in support of inclusion. We recognize that addressing issues of inclusiveness and working in support of anti-racism within individuals and within academia require continued commitment and ongoing, sustained effort.

Fourth, we commit to developing, promoting, and enunciating guidelines and codes of conduct for our conferences, workshops and other events, as well as other events associated with our constituent organizations.