# CSC544 - Theory of Computation

Spring 2015

## Instructor:

Dr. Lutz Hamel
Tyler, Rm 251
Office Hours: Tues/Thurs 11am - noon
email: hamel@cs.uri.edu

## Announcements:

### Final due on Monday 5/11/15 @ noon in my office/mailbox

[4/21/15] posted assignment #5
[4/21/15] posted solutions for assignment #4
[4/16/15] posted solutions for assignment #4
[4/7/15] finally posted the hand out properly on the solutions page - I hope
[4/7/15] posted solutions to the midterm
[4/7/15] posted assignment #4
[4/2/15] ** no class today 4/2 ** - please leave your midterms in my mailbox.
[3/31/15] posted the book excerpt on mu-recursive functions on the solutions page.
[3/26/15] take a look at the lambda calc tutorial posted below
[3/26/15] ** Midterm, due Thursday 4/2/15 in class **
[3/11/15] posted assignment #3
[2/26/15] posted assignment #2
[2/19/15] ** no class today 2/19 **
[2/5/15] posted assignment #1
[1/21/15] Welcome!

## Description

Computation and algorithms seem to occur naturally in our daily lives. Consider counting change or following a recipe to make your favorite dish. The art of programming takes this to the limit by formally encoding computations and algorithms for a machine to follow. What are the limits of this algorithmic approach? Are there mathematical objects that cannot be computed by a machine via an algorithm? If we can express a computation via an algorithm how long would it take to compute? How much space would the computation consume?

In this course we will investigate many of these interesting questions. As our main tool we will use an idealized general purpose computer invented by Alan Turing: the Turing Machine. This idealized machine allows us to study the limits of computability and the complexity of computations without having to worry too much about actual hardware. We will also touch on an alternative formulation of computation based on recursive function applications. This approach was proposed by Alonso Church in the 1940's and is now known as the lambda-calculus. Church and Turing reached the same conclusions about computability using their models and we often refer to this central result as the "Church-Turing Thesis".

The goal of the course is that you are exposed to the terminology of the theory of computing and are familiar with some of the major results in computability and complexity theory. This course will allow you to understand current research in algorithmics, especially in the area of bioinformatics where computability and complexity are major concerns. The hope is that studying algorithms, computation, and complexity at this abstract level will provide you with some insights into your programming tasks and will provide perhaps a different vantage point of computing itself.

## Assignments:

In order to receive full credit for your assignments they have to be typewritten.  Hand drawn diagrams are acceptable. Email submissions are not acceptable.
• Assignment#1: problemsheet, due Thursday 2/12 in class.
• Assignment#2: Reading: Chaps 2,3; problemsheet, due Thursday 3/5 in class.
• Assignment#3: Reading: Chap 3,4; problemsheet, due Tuesday 3/24 in class.
• Assignment#4: Reading: Handout; problemsheet, due Tuesday 4/14 in class.
• Assignment#5: Reading: Chap 7; problemsheet, due Tuesday 4/28 in class.