Dartmouth Logic Seminar

## 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.

DateTopic
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.

DateSpeakerTitle
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.