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

## Documents of Interest:

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