Fall 2010
This term we are holding two seminar series. On Tuesday we will have an introductorylevel seminar teaching recursion/computability theory. On Wednesday we will have the researchlevel seminar. All are welcome to both.
Introduction to Recursion Theory
Tuesdays, 23 pm, 110 Moore Hall.
Marcia Groszek will do an introductory level seminar on recursion theory and possibly, depending on interest, Hilbert's tenth problem. There are no logic prerequisites; this should be accessible to any graduate students, and any undergraduates who are ready for graduate level mathematics. Any graduate student thinking of doing a logic qual should be there. We will start at the beginning and do the details people usually skip about what "computable" really means.
Date  Topic 

Sep 28  Introduction; two possible ways to define "computable function": Turing machines and Σ_{1} formulas. 
Oct 5  Third definition of "computable function": (total) recursive functions; primitive recursive and partial recursive functions; universal functions; building arithmetic functions to show they are recursive; the pairing function 
Oct 12  Construction of: primitive recursive coding function for any sequence of n numbers; primitive recursive decoding functions giving the length of a sequence from its code or the i^{th} element of a sequence from its code; primitive recursive bounding function giving upper bound on possible codes of sequences of n numbers all ≤ n. 
Oct 19  Coding primitive recursive functions and computations; a single function incorporating all primitive recursive functions (though itself not primitive recursive); coding for partial recursive functions; a universal partial recursive function; unsolvability of the halting problem. 
Oct 26  Smn theorem, proof and applications. 
Nov 2  Fixed Point Theorem (Recursion Theorem) and applications. 
Nov 9  Additional application and proof of Fixed Point Theorem; examples of r.e. nonrecursive sets; construction of simple set (injuryfree priority argument). 
Nov 16  The infinite Ramsey theorem for pairs and Specker's theorem that the effective version fails (finite injury priority argument). 
Nov 23  No seminar. 
Nov 30  Term recap; manyone and Turing reduction; mutual relative computability of H (full halting problem) and K (diagonal halting problem); relativization and the fact that the smn theorem still gives a primitive recursive function in the index. 
Logic Seminar
Wednesdays, 23 pm, 28 Haldeman Center.
Date  Speaker  Title 

Sep 29 
Johanna Franklin
Dartmouth College

Difference randomness What do you get if you generalize MartinLöf tests from r.e. sets to nr.e. sets? There are at least two distinct ways to do so and we explore the associated randomness notions. Joint work with Keng Meng (Selwyn) Ng. 
Oct 6 
Johanna Franklin
Dartmouth College

Difference randomness, part 2 
Oct 13 
Johanna Franklin
Dartmouth College

Difference randomness, part 3 
Oct 20 
Marcia Groszek
Dartmouth College

Structural Ramsey theory for countably infinite structures This talk has no prerequisites and is of interest for combinatorial reasons as well as logical ones. 
Oct 27 
Marcia Groszek
Dartmouth College

Structural Ramsey theory, part 2 
Nov 3 
Marcia Groszek
Dartmouth College

Structural Ramsey theory, part 3 
Nov 10 
Jared Corduan
Dartmouth College

The Ramsey property for n=1 With a brief introduction to reverse mathematics. 
Nov 17 
Jared Corduan
Dartmouth College

The Ramsey property for n=1, part 2. 