Computability and the Study of Formal Languages 2008 - 2009

Computability and the study of Formal Lanuages (CSFL for short!) is a year-long, 16 quarter hour coordinated studies program that has as its major objectives

1. Providing advanced work in mathematics, computer science, and philosophy through a rigorous investigation of computational models of formal systems.
2. Exploring the following questions in depth:
   • What are the strengths and limitations of formal systems?
   • To what extent do formal systems provide a foundation for knowledge?
   • What are the prospects for simulating significant aspects of human intelligence using a computer (Artificial Intelligence)?
   • In the pursuit of artificial intelligence what are the benefits of the empirical approach (as evidenced by artificial neural networks) as opposed to the rational approach (as evidenced by rule-based formal systems)?

3. Developing skills in working with formal systems (particularly those presented in formal language theory and mathematical logic). This activity includes both learning the "language of mathematics" in these domains as well as understanding strategies for solving problems cast in this language.
4. Gaining facility in working with problems from mathematical logic, discrete math, theory of computability, formal language theory, and advanced programming techniques. This specific expertise will be treated as valuable in itself, but also crucial to the understanding of larger themes of the program.
5. Developing an understanding of programming techniques through the use of (one or more of) the Curry, Prolog and the C++ programming languages.
6. Developing an in-depth understanding of complex formal systems through the study of operating systems techniques, system-level programming, and conccurrency.
7. Working on one or more significant programming projects connected to the program themes (such as compiler implementation, implementations of neural net architectures, concurrent programming, systems level programming).

IN ORDER TO REGISTER IN THE PROGRAM STUDENTS MUST FIRST TAKE A (TAKE-HOME) ENTRANCE QUESTIONNAIRE or write a 2-3 page paper. THE QUESTIONNAIRE WILL BE AVAILABLE FROM SHERRI's WEBPAGE: http://grace.evergreen.edu/~sherri.

NOTE! Seminar will be in the spring.

In the fall quarter the program will emphasize the nature of formal systems. Students will study the mathematical foundations of computer science, learn how to prove theorems, how to distinguish between valid and invalid arguments, learn the multi-paradigm programming language Curry and study programming language design.

Formal Logic (5 quarter hours). This part of the program will consist of a standard treatment of propositional and first-order logic. Particular emphasis will be placed on formal methods for proving the validity of valid arguments and for finding counterexamples for invalid ones.

Programming (6 quarter hours). This component will examine techniques for programming in Curry, combinng the features of a fuctional language and logic variable..

Programming Language Design (5 quarter hours) . This part of the program will study how languages are designed, what features we have to choose from and how those choices influence what we can say and how we can say it.