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