Course overview
Welcome to CSC 54-844! The course is an introduction to the theory of information and computation as a physical phenomenon. The course covers standard formalizations of computational concepts and proofs of noteworthy implications of these formalizations. We will be defining what a "computer" is, and exploring what are some of the fundamental limits of different types of computers. In this course we will study the following topics:
- Formal languages and decision problems
- Deterministic and nondeterministic finite automata
- Regular expressions
- Non-regular languages
- Context free grammars
- Pushdown automata
- Non-context-free languages
- Turing machines
- Turing completeness
- Turing (un)decidabile and (un)recognizable languages
- Reducibility
This list is neither exhaustive nor set in stone.
Instructor
Name: Arjun Chandrasekhar
Email:
chandrasa@southwestern.edu
Lecture: Tuesday/Thursday 11:30 am - 12:45 pm in TBD
Student Hours: TBD from TBD - TBD in FJS 310 (the math/CS common room). If these times do not work for you, then email me to set up student hours by appointment.
(please fill out
this google form to let me know what times work for you to hold student hours).
Course Links