http://home.gwu.edu/~harizanv/Logic%20Seminar%20F09.html
1:00–2:00p.m.
Speaker: Rumen Dimitrov, Western Illinois University
http://www.wiu.edu/users/rdd104/home.htm
Place: Monroe Hall
(2115 G Street), Room 267
1:00–2:00p.m.
Speaker: Scott Aaronson, MIT
Place: Government Hall, Room 101
Title: How Pervasive Is
Incompleteness?
Abstract:
I was asked to
give a ÒspeculativeÓ math talk. So, I'll discuss the question of just how
much Ònormal, finitaryÓ math the Gšdel incompleteness
phenomenon might infest. IÕll first survey the types of independence and undecidability results that are known, and explain why in
my view, none of them give a fully satisfactory
answer. IÕll then speculate about the question, which IÕm often asked, of
whether the P vs. NP problem might turn out to be formally undecidable.
Finally, IÕll discuss the Busy Beaver function, and its amazing ability to
ÒconcretizeÓ questions of mathematical logic. IÕll mention some ongoing work
with Adam Yedidia that aims to construct a small
Turing machine whose (non-)halting is provably
independent of the ZFC axioms.
At the American Math Society Meeting
at Georgetown University, Washington, DC, March 7–8, 2015, there will be
a Special Session on Computable Structure Theory.
Speakers include: W. Calvert, J. Chubb, B. Csima, D. Cenzer, D. Dzhafarov, K. Fokina, S. Goncharov, J. Knight,
K. Lange, C. Laskowski, A. Montalban,
A. Morozov, R. Solomon, A. Shlapentokh,
A. Soskova, M. Soskova.
Plenary
Special Session talk will be given by:
Sergey Goncharov,
Russian Academy of Sciences and Novosibirsk State U.
Definability and index sets of computable models.
Saturday, March 7
2:00–3:00
p.m.
Healy
Hall (37th and O St.), Room 103
2:30–3:30p.m.
Speaker: Hakim Walker GWU
Place: Government Hall, Room 101
2:30–3:30p.m.
Speaker: Trang Ha, GWU
Place: Government Hall, Room 101
2:30–3:30p.m.
Speaker: Leah Marshall, GWU
Place: Government Hall, Room 101
Abstract:
One way of
examining computability-theoretic complexity of various natural properties
(relations) of computable structures is to examine the complexity of the formulas
that define the properties. In this talk, we will discuss some examples of the
arithmetical complexity of various objects, pulling from the more standard and
classic examples, as well as describing some examples from current research. We
will review arithmetical hierarchy. The talk will be accessible to all
graduate students.
2:30–3:30p.m.
Speaker: Andrew Hirsch, Cornell University
http://www.cs.cornell.edu/~akhirsch/
Place: Government Hall, Room 101
Title: Strictness, laziness, and effects
Abstract: Computer scientists want to
be able to write down programs and have them correspond to a single
computation. Sadly, most programming languages don't allow this: a single
program might be read multiple ways. The standard strategies for fixing this,
strictness and laziness, have been used since the 1930s, but continue to be
poorly understood. The questions of why most languages have multiple readings,
and why strictness and laziness are the natural solutions, remain mostly
unanswered. We still lack even a formal definition of laziness that is not
language-dependent.
This talk focuses on recent
work that attempts to provide a formal definition and answer these questions.
We achieve this by looking through the lens of effects, which allow us to
classify computations in input-independent ways.
1:00–2:00p.m.
Speaker: Rumen Dimitrov, Western Illinois University
http://www.wiu.edu/users/rdd104/home.htm
Place: Monroe Hall
(2115 G Street), Room 250
Title: The rich structure of modular lattices arising from
computably enumerable vector spaces
Abstract: PostÕs problem
in computability theory, dating back to 1944, is whether there exist a computably enumerable (c.e.)
Turing degree that is neither computable nor the degree of the
halting problem. His strategy was to find a non-computable co-infinite c.e. set with a ÒthinÓ complement.
The original notion of thinness was calledÒsimplicity.Ó
A c.e. set the complement of
which is infinite but has no infinite c.e. subset is called simple. Different, ever-stronger, notions
of thinness were defined, but none of them gave a solution to PostÕs problem.
These notions, however, revealed some fascinating structural properties of the
lattice E of c.e. sets under
inclusion, and its factor lattice E* (E modulo finite sets). In the talk we
will introduce the lattice L of c.e. subspaces of the fully algorithmic infinite dimensional
vector space and its factor lattice L* (L modulo finite dimension). We will
explore some important similarities and differences between E* and L*.
3:45–5:00p.m.
Speaker: Rumen Dimitrov, Western Illinois University
Place: DuquŽs Hall, Room 362
Title: Standard
and nonstandard ways of constructing nonstandard structures
Abstract: In this talk we will start with some standard ways of
obtaining nonstandard structures. We will then introduce the notion of cohesive
power B of a computable structure A (see [1]) over a cohesive set R. We will prove certain connections
between satisfaction of different formulas and sentences in the original model A and its cohesive power B.
[1] R. D. Dimitrov, Cohesive powers of computable structures, Annuaire de lÕUniversitŽ de Sofia
ÒSt. Kliment Ohridski,Ó FacultŽ de MathŽmatiques et Informatique 99 (2009), pp. 193–201.
2:30–3:30p.m.
Speaker: Russell Miller, City University of New York
http://qcpages.qc.cuny.edu/~rmiller/
Place: Monroe Hall (2115 G Street), Room 267
Title: Effective classification of computable
structures
Abstract: Many
classes of computable structures can be enumerated computably. For example, one
readily gives a uniformly computable list of all computable linear orders,
simply by enumerating the c.e. subsets
of a single computable dense linear order. Of course, this list includes
infinitely many computable copies of each computable linear order. To give a
computable classification (up to isomorphism) of these linear orders would
require computing such a list so that no two linear orders on the list are
(classically) isomorphic to each other. This is known to be impossible.
The paradigm of a computable
classification was given by Friedberg, who produced a uniformly computable
listing of all c.e. sets,
with no set appearing more than once in the listing. That is, he gave a
computable classification of the c.e. sets up to equality. We apply his method to yield a
computable classification of the computable algebraic fields, up to (classical)
isomorphism. We also follow Goncharov and Knight in
showing that certain other classes have no computable classification.
Finally, we give a 0'-computable classification of the computable equivalence
structures. This result, which extends (and uses) more work of Goncharov and Knight, means that there is a uniformly 0'-computable listing of all computably
presentable equivalence structures, with no isomorphisms
between any two distinct structures on the list; however, the structures on the
list are only 0'-computable, not
necessarily computable. We conjecture that there is no computable
classification of the computable equivalence structures.
2:30–3:30p.m.
Speaker: Leah Marshall, GWU
Place: Monroe Hall
(2115 G Street), Room 267
Title: Computable isomorphisms between partial computable injection
structures
Abstract: A partial computable
injection structure is a mathematical structure consisting of a computable set
of natural numbers and a partial computable, injective (1-1) function.
The ÒshapeÓ of these structures is determined by the orbits
of the elements; that is, what happens when we apply our function to an
element repeatedly. These structures can therefore be completely
classified up to isomorphism by the numbers, types, and sizes of their orbits.
However, we know that isomorphisms alone do not
necessarily preserve the computability-theoretic properties of mathematical
structures. We examine partial computable injection structures with
computable isomorphisms, and we explain what goes
wrong in structures without such computable isomorphisms.
Additionally, we do the same for partial computable injection structures under
Δ2-isomorphisms and Δ3-isomorphisms.
2:30–3:30p.m.
Speaker: Jozef
Przytycki, GWU
http://home.gwu.edu/~przytyck/
Place: Monroe Hall
(2115 G Street), Room 267
Abstract: For the 30th anniversary of
the Homflypt polynomial of links, I propose a new
polynomial invariant of rooted trees. I will relate this to the Kauffman
bracket (version of the Jones polynomial) and to (pre)simplicial categories.