Andre Nies, "Computability and Randomness" (Chapters 1-3).
Measures and their Random Reals.
Randomness for continuous measures

• There has been considerable progress in the recursion theoretic study of randomness in the past several years. I will give a conceptual overview of the area and a more focused discussion of my joint work with Jan Reimann, in which we study the question, "For which infinite binary sequences X is there a (continuous) probability measure relative to which X is effectively random?" The investigation has a surprisingly meta-mathematical character, and necessarily so.

• Background material will be covered in the September 29 Workshop.

• Location: Science Center 309.

Andre Nies, "Computability and Randomness" (Chapter 1)
Soare, "Computability Theory and Applications" (Chapters 7, 9.1-2, 10.1) -- available by email. [Alternatively: Soare, Recursively Enumerable Sets and Degrees, Chapters 7 and 14.1.]

Soare, "Computability Theory and Applications" (Chapters 9.1-2, 10.1) -- available by email.

• Abstract: The Erdos-Renyi random graph construction can be seen as inducing a probability measure concentrated on the Rado graph (sometimes known as the countable "random graph") that is invariant under arbitrary permutations of the underlying set of vertices. The following question arises naturally: On which countable combinatorial structures is there such an invariant measure? Up until recent work of Petrov and Vershik (2010), it was not even known if Henson's universal countable triangle-free graph admitted an invariant measure.
We provide a complete characterization of countable structures admitting invariant measures, in terms of the model-theoretic notion of definable closure. This leads to a characterization for ultrahomogeneous structures, as well as new examples of invariant measures on graphs and other combinatorial structures.
Joint work with Nate Ackerman and Rehana Patel.

• Location: Science Center 113.

• Definability is one of the fundamental themes of computability theory. We examine the structure of the computably enumerable (c.e.) sets under set inclusion. The problem of which classes of degrees are definable in this structure has been an important topic of study in computability theory. In particular, it has been shown that all upward-closed jump classes (such as high, nonlow2, etc.) are definable except for the nonlow degrees, which are not definable. To show that the nonlow degrees are not definable, we use automorphisms, which we build on trees of strategies. We will discuss the history of the problem and some of the ideas of the proof.

• See R. Epstein, Invariance and automorphisms of the computably enumerable sets. [pdf]

• Background material will be covered in the in the October 13 and October 20 Workshop.

• Location: Science Center 309.

• The construction of uncountable models of certain infinitary theories via intransitive countable hulls.

• Background material will be covered in the in the Novermber 3 Workshop.

• Location: Science Center 309.

• The evident ubiquity of (formally) unsolvable problems in Set Theory argues for a re-examination of the conception of truth at least for Set Theory. The mathematical investigation of this apparently non-mathematical problem has led to a surprising series of mathematical conjectures, problems and successes. The stage is now set for either: (1) The validation of a single additional axiom which if added to the traditional ZFC axioms would entirely eliminate the phenomena of unsolvability based on Cohen's method of forcing while preserving the fundamental strong axioms of infinity; or (2) The refutation from the same strong axioms of infinity of any such possibility based on anything like that currently imagined. In other words, Set Theory is facing a critical dichotomy in possible futures.

• Location: Fong Auditorium, at Boylston Hall 110.

• Abstract: Over the past thirty-five years theoretical computer scientists invented new methods and notions of proofs for mathematical statements. These represent a departure from the classical notions of mathematical proofs going back to Euclid. Examples are proofs employing randomization, interactive proofs, zero-knowledge proofs, probabilistically checkable proofs, and computer generated proofs. The lecture will be self contained.

• Background material:

• M.O. Rabin Probabilistic Algorithm for Testing Primality, Journal of Number Theory, 12, 128-138, 1980.
• J.T. Schwartz, Fast probabilistic algorithm for verification of polynomial identities, Journal of the ACM, 27(4), 701-717, October 1980.
• S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, 18, 186-208, 1989.

• Location & Time: Science Center 309, 4pm.

• Abstract: A historical account of the achievements in logic of Jacques Herbrand (1908-1931), in particular the central result of his 1930 dissertation, often called Herbrand's Theorem (but nowadays often misdescribed); and the significant impact that the Theorem had in application to proof-theoretic questions in the 1930s and later.

• Location & Time: Science Center 309, 4pm.

• Abstract: We show the algorithmic unsolvability of a number of decision procedures in ordinary two dimensional Euclidean geometry, involving lines and integer points. We also consider formulations involving integral domains of characteristic 0, and ordered rings. The main tool is the solution to Hilbert's Tenth Problem. The limited number of facts used from recursion theory are isolated at the beginning.

• Location & Time: Science Center 309, 4pm.

• Abstract: I will discuss recent work of Koenigsmann, building on work of the speaker, showing that the complement of Z in Q is diophantine (or equivalently, defined by an existential formula). If Z itself were shown to be diophantine in Q, it would follow that there is no algorithm to decide whether a multivariable polynomial equation has a solution in rational numbers.

• Background material (in the order that they should be read):

• B. Poonen, Undecidability in number theory, Notices Amer. Math. Soc. 55 (2008), no. 3, 344-350. Online version at http://www-math.mit.edu/~poonen/papers/h10_notices.pdf.
• B. Poonen, Characterizing integers among rational numbers with a universal-existential formula, Amer. J. Math. 131 (2009), no. 3, 675-682. Online version at http://www-math.mit.edu/~poonen/papers/ae.pdf
• J. Koenigsmann, Defining Z in Q, preprint, http://arxiv.org/abs/1011.3424

• Location & Time: Science Center 309, 4pm.