CSE 547T (Fall 2014)

Course Information

This course examines the most fundmantal question that can be asked in computer science: what can (and cannot) be computed? We examine a sequence of computational models and show that each model can compute some things, while other things are beyond its power. The last model we examine is due to Turing, and is the best model we have for what the human brain can do. We show that there are many interesting things that the Turing machine model cannot compute.
Students taking this course should be familiar with topics in a standard computer science course covering discrete math and logic.
Ron K. Cytron
office: 525 Bryan Hall
email: cytron@wustl.edu
office hours: MW 3:00–4:00 PM
skype: wustl.cytron.ron
Teaching Assistants
Getting help
We will use this piazza page for the course. Please send your questions and comments to this page.
Introduction to Languages and the Theory of Computation, by John C. Martin, Fourth Edition
Online version apparently available here
What When Weight for final grade
Exams Three noncummulative exams will be given in class, approximately as indicated in the syllabus. Each is worth 25%
Homework Almost every week, 10 questions will be published. Four of those questions are your homework, and their solutions are due at the end of the class when you turn in your quiz (see below).

Homework will be examined and recorded during grading, and some comments may be made, but you get full credit for a homework assignment simply by submitting something (reasonable).

A solution for the homework problems will be published.

You may collaborate in solving the homework problems, but to receive credit, the written solution must be your own.
Average of homeworks is worth 3%
QuizzesOn the date a homework assignment is due, one of the 6 questions not given as homework will be randomly chosen for an in-class, closed-book quiz. Average of quizzes, after lowest-scored quiz is dropped, is worth 20%
  • Throughout the semester, questions will be posed during lecture, and you are invited to respond using WUTexter. A form will be distributed in the second lecture for you to identify the twitter account from which your credit should be awarded for participation.
    Your association with that twitter account will be kept secret until grades are assigned at the end of the semester.
  • Course evaluation
This is worth up to 2%

Academic Integrity
Anyone found cheating will on any graded assignment will receive an F for this course; other action may also be taken.

Syllabus (with references to Martin, 4th Edition)

Last modified 09:28:27 CDT 17 August 2014