Place: Monroe Hall (
Speaker: Vitezslav Svejdar,
Title: Grzegorczyk’s Variant of Robinson Arithmetic
Abstract:
Q–
is a theory similar to Robinson arithmetic Q, but its addition and
multiplication are functions possibly non-total. The talk will briefly sketch a
proof that Q is interpretable in Q– and thus Q– is essentially undecidable. The proof uses Solovay’s method of shortening of inductive cuts, known
since 1976, but never published.
Place: Monroe Hall (
Speaker: Hunter Monroe,
International Monetary Fund
Title: Are There “Natural” Problems with No Fastest Algorithm?
Abstract:
Some suspect that several familiar
problems such as integer multiplication and matrix multiplication have speedup,
i.e., no fastest algorithm. In fact, there is no optimal Strassen-type
identity for matrix multiplication (Coppersmith and Winograd).
However, no natural problem—one requiring at least linear time—is known to have
speedup on Turing machines. We identify several properties of problems that
seem to imply speedup under two definitions (Blum's definition is not
applicable). However, identifying a natural problem with speedup would imply P≠NP. Speedup can be seen as a weak form of non-computability, i.e.,
the property “has no fastest algorithm” is a weak version of “has no algorithm
at all”. Therefore, computability theory might illuminate speedup and open
problems.
Speaker: Joe Mourad,
Place: Monroe Hall (
Title: Well
Founded Trees and Constructing Reals
Speaker: Michael Moses, GWU
Place: Monroe Hall (
Title: Intrinsically
Complete Properties in Linear Orders
Speaker: Sarah Pingrey, GWU
http://home.gwu.edu/%7Espingrey/
Place: Monroe Hall (
Title: Complexity
of Relations on Computable Structures, Part III
12:00noon–1:00 p.m.
Speaker: Sarah Pingrey, GWU
http://home.gwu.edu/%7Espingrey/
Place: Monroe Hall (
Title: Complexity
of Relations on Computable Structures: Using Interval Trees, Part II
Abstract: We
will continue our talk from last week and show our main theorem, that for every
limit computable set C, there is a computable linear ordering L
of order type w+w* such that C ≤T
w(L) ≤tt C. Then, we will extend our first
application of interval trees to show that if we assume that C is
computably enumerable, then so is w(L). We will also show that the main theorem does not
hold when Turing reducibility is replaced by weak truth-table reducibility. We
will also give a strengthened version of this result: that C is also not
weak truth-table reducible to any computable scattered linear ordering.
Speaker: Sarah Pingrey, GWU
http://home.gwu.edu/%7Espingrey/
Place: Monroe Hall (
Title: Complexity
of Relations on Computable Structures: Using Interval Trees
Abstract: Let A be a computable structure and R
be an additional relation on A. The Turing degree spectrum of R
on A is the set of all Turing degrees of the images of R under
all isomorphisms from A to computable models. The
Turing degree spectrum of the w-part of a linear ordering of type
w+w* is all of the limit computable
Turing degrees. This is not the case for tt-degrees,
and we will show the best possible positive result: for every limit computable
set C, there is computable linear ordering L of order type w+w* such that C ≤T w(L) ≤tt C. We will show this result by
defining a new technique of finding the interval tree of a linear
ordering. This is joint work with J. Chisholm, J. Chubb, V. Harizanov,
D. Hirschfeldt, C. Jockusch,
and T. McNicholl.
Speaker: Jennifer Chubb, GWU
http://home.gwu.edu/%7Ejchubb/
Place: Monroe Hall (
Title: Degree
Spectra of the Successor Relation
Abstract: We consider a computable linear ordering L,
and ask what Turing degrees the successor relation can have in computable
copies of L (this is the degree spectrum of the successor relation of L).
We show that for a large class of linear orderings, the degree spectrum of
successor is closed upwards within the c.e.
Turing degrees. As a consequence, we will see that every upper cone of c.e. Turing degrees is the degree
spectrum of the successor relation of some computable linear ordering. This is
from joint work with A. Frolov and V. Harizanov.
OTHER LOGIC TALKS
Conference:
Knots in
http://home.gwu.edu/~przytyck/knots/knotsinwashington25.htm
Speaker: Jennifer Chubb, GWU
http://home.gwu.edu/%7Ejchubb/
Place: Media and
Title: Effectively Closed Sets and Orderings on Groups
Abstract: A countable group G is computable if there is an algorithm
to determine membership in G as a set, and an algorithm for
multiplication on the group. G is left-orderable (bi-orderable) if there
is a linear ordering of the elements of the group that is left-invariant (both
left- and right-invariant). I will describe how the orderings of a countable
group may be viewed as infinite paths through a binary tree, and how the
orderings of a computable group correspond to paths in a computable binary
tree. Taking the usual topology induced on the paths, we see that these sets
are closed subsets of Cantor space, and in the computable case, we can think of
them as effectively closed. The effectively closed sets have been extensively
studied in computability theory, and I will describe some of the computability
theoretic consequences for the spaces of orderings on groups.
Speaker: Sarah Pingrey, GWU
http://home.gwu.edu/%7Espingrey/
Place: Media and
Title: Orders on Computable Torsion-Free Abelian
Groups
Abstract: A countable group is computable if its domain is a computable set
and its group theoretic operation is computable. We examine complexity of
orders on a computable torsion-free abelian (hence
orderable) group G, using Turing degrees as a complexity measure. There
are continuum many Turing degrees and they form an upper semilattice
under Turing reducibility. All computable sets have Turing degree zero. It is
easy to see that if G is of rank 1, then G has exactly two orders
and they are computable. Solomon showed that if G has a finite rank greater
than 1, then G has an order in every Turing degree. On the other hand,
if G is of infinite rank, then G does not necessarily have a computable
order, as shown by
Mathematics
Colloquium
Place: Monroe Hall (
Speaker: Martin Davis, Courant Institute
http://cs.nyu.edu/cs/faculty/davism/
Title: Unsolvability and Undecidability in the
Diophantine Realm
Abstract: The work on the negative solution of Hilbert's 10th
problem will be surveyed with emphasis on applications, recent work, and open
problems.
Graduate
Student Seminar
Place: Monroe Hall (
Speaker: Michael Moses, GWU
Title: Compactness in Mathematical Logic
Abstract: Two well known mathematical languages,
the classical one of Aristotelian Logic and the everyday one of First Order
Logic, are ‘compact’ in that, for any (infinite) collection of sentences in
these languages, if every finite sub-collection 'is satisfiable',
then so is the whole collection. It is surprisingly easy to see why these
languages are compact. Even more surprising are the ramifications of their
compactness, in all areas of mathematics, from classical analysis to modern combinatorics and, most especially, in mathematical logic,
where it has some unsettling things to say about the mathematical languages
that we employ, and the mathematical proofs that we seek. I will begin this
talk with an historical exploration of compactness and its connection with the
corresponding topological concept from which it gets its name, follow this with
examples of the use of compactness in the ‘non-standard analysis’ of Abraham
Robinson and the ‘probabilistic method’ of Paul Erdos,
and close with a brief discussion of what compactness says about mathematical
languages and proofs.
Place: Monroe Hall (
Speaker: Sarah Pingrey, GWU
http://home.gwu.edu/%7Espingrey/
Title: Computability and the Halting Problem
Abstract: Computability theory was invented in the
1930’s by Turing, Gödel, Church, and Kleene, among
others, who gave formal definitions of a computable function. All of these
definitions turned out to be equivalent. The Church-Turing Thesis, generally
accepted by all computability theorists, says that the formal notion of a
computable function captures the intuitive idea of a computable function. I
will discuss what it means for a function, set, and relation to be computable,
and computably enumerable and then define the Turing degrees. The Turing degree
of a set says how uncomputable a set is. Then, we
will discuss the halting problem, which is a natural example of a set that is
computably enumerable but not computable. This talked is aimed at
undergraduates.
Place: Monroe Hall (
Speaker: Michele Friend, Department of Philosophy, GWU
Title:
An Introduction to the Realist and
Constructivist Philosophies of Mathematics
Abstract: I shall be outlining the basic positions
which fall under “realism” and “constructivism” in logic/mathematics.
I shall also be giving a quick set of indicators, so you can tell which one you
are talking to! I'll then outline some of the motivations for both positions
and examine some contentious formal arguments.
Place: Monroe Hall (
Speaker: Jennifer Chubb, GWU
http://home.gwu.edu/%7Ejchubb/
Title: An Algorithmic Approach to Linear
Orderings
Abstract: Starting with first principles, I’ll talk
about properties of linear orderings and relations on linear orderings in the context
of computability theory. After some examples and a brief survey of research in
this area, I’ll explain some new results.