Fall 2010

This term we are holding two seminar series. On Tuesday we will have an introductory-level seminar teaching recursion/computability theory. On Wednesday we will have the research-level seminar. All are welcome to both.

Introduction to Recursion Theory

Tuesdays, 2-3 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 ith 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	S-m-n 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 (injury-free 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; many-one and Turing reduction; mutual relative computability of H (full halting problem) and K (diagonal halting problem); relativization and the fact that the s-m-n theorem still gives a primitive recursive function in the index.

Logic Seminar

Wednesdays, 2-3 pm, 28 Haldeman Center.

Date	Speaker	Title
Sep 29	Johanna Franklin Dartmouth College	Difference randomness What do you get if you generalize Martin-Löf tests from r.e. sets to n-r.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.