050.371/671 -- Formal Methods in Cognitive Science: Inference
Spring 2000
MW 10:30 - 12:00
234 Krieger Hall
/courses/371

Robert Frank
233A Krieger Hall
rfrank@cog.jhu.edu
office hours: M 3:30-5:30

This course introduces a variety of techniques for modeling human cognition, with a special focus on deductive and inductive inference. We will discuss a wide range of mathematical structures and techniques and demonstrate their applications in theories of grammatical competence and performance. A major goal of this course is bringing students to a point where they can evaluate the strengths and weaknesses of existing formal theories of cognitive capacities, as well as profitably engage in such formalization, constructing precise and coherent definitions and rigorous proofs.

Course Requirements

In learning this material, it is absolutely crucial to work problems. To this end, there will be (roughly) weekly problem sets. These will in general be assigned on wednesday and will be due one week later. These problem sets will account for 60% of the grade. Twice during the course (precise dates to be announced), I will assign longer problem sets with broader coverage. Each of these will count for 20% of the grade. The remaining 10% of the grade will be given on the basis of constructive class participation.

I encourage/implore you to work together with your fellow students on the weekly problem sets (though not on the two longer ones). However, once you have finished your discussions, you must write up your answers on your own.

Reading

The reading for this course will be drawn from a number of different sources. The two primary texts will be the following:

Mathematical Methods in Linguistics, Barbara Partee, Alice ter Meulen and Robert Wall, Kluwer, 1993

Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Company, 1997.

The Sipser book covers material from the computability and complexity theory sections of the course in considerably more detail than the Partee et al. text. During the term, I may also assign other readings, in which case I will make them available in the Cognitive Science department reading room (Krieger 232).

(Tentative) Course Outline and (Partial) Reading List

This overly ambitious outline will almost certainly be revised depending upon our rate of progress. A partial reading list is provided for certain topics. More will be added during the course of the term. Numbers following PMW and Sip refer to chapters from the Partee et al. and Sipser texts respectively,

1.

Background - Sets, functions, relations, proofs S 1, PMW 1-4

2.

Computability Theory

(a)

Turing Machines and Church's Thesis PMW 19.1-19.4, S 3

(b)

Undecidability and the Halting Problem.

PMW 19.5-19.7, S 4

(c)

Reducibility S 5

(d)

Applications to learning theory: identification in the limit

3.

Complexity Theory

(a)

Measuring complexity - time and space S 7.1

(b)

The classes P and NP S 7.2-7.3

(c)

NP-completeness and Polynomial Reducibility S 7.4-7.5

4.

Logic

(a)

Propositional logic

PMW 6

(b)

Predicate Logic PMW 7

(c)

Efficient inference

(d)

Impossible Inference: Decidable and Undecidable Theories S 6.2, PMW 8 (esp. 8.5-8.6)