2008-09 Catalog

Decorative graphic

Program Description

Computability and Language Theory

Revised Last Updated: 02/06/2009

Fall, Winter and Spring quarters

Faculty: Sheryl Shulman computer science

Faculty Signature Required: Interested students should contact Sherri Shulman, at sherri@evergreen.edu or 360-867-6721, or at the academic fair to obtain a signature. Qualified students will be accepted until the program fills.

Major areas of study include mathematical logic, formal language theory, computability theory and programming language design. Upper division credit will be awarded for upper division work.

Class Standing: Sophomores or above; transfer students welcome.

Accepts Spring Enrollment: This program will accept new students who are qualified to work on an independent project and have a background in formal languages and logic. Interested students should contact the faculty.

Prerequisites: Students should know at least one programming language before entering the program and have the equivalent of Computer Science Foundations. For transfer students, preparatory coursework should include one full year of programming, Discrete Mathematics, Data Structures, and/or Computer Architecture. Students with a strong mathematical background and interest in formal computer science will also be considered. If you have questions about prerequisites, please contact Sherri Shulman (sherri@evergreen.edu).

The computer is a tremendously useful tool. Is there anything it can't do? By studying topics in advanced computer science, this program will explore what computers can do, how we get them to do it, and what computers still can't do. This program is designed for advanced computer science students and students with an interest in both mathematics and computer science.

Topics covered will include formal computer languages, formal logic, computability theory, alternative logic theories and programming language design. Students will also study Curry, a formal language combining both the functional and logic programming paradigms. Students will learn the theoretical basis of programming languages such as Curry. We will also do an in-depth comparison of the properties and capabilities of languages in the four paradigms: functional, logic, imperative, and object-oriented. Program seminars will include current literature on selected topics such as type theory and programming language semantics.

The four threads in this program each span all three quarters. In the Programming Language thread we will study the basis for programming language definitions and compare language definitions from several different paradigms. The thread will conclude with a project completing a full interpretion of a user defined language. The Logic thread will cover traditional logic systems and their limits, and will conclude with some non-traditional logic systems and their applications to computer science. The Formal Language thread will cover the theoretical basis of language definitions, concluding with a study of what is computable. In the fourth thread we will study Curry for the first half of the year, including a study of the theoretical and implementation techniques required. During the second half of the year we will also read technical papers relating to current language design challenges.

Credits: 16 per quarter

Enrollment: 25

Books: www.tescbookstore.com

Program is preparatory for careers and future studies in computer science and mathematics.

Planning Units: Scientific Inquiry

Program Revisions

Date Revision
February 6th, 2009 Spring Enrollment field utilized; signature field updated.