Project 125%
Adopt a Machine
Pick one small job, draw its honest machine, write it as the Notes 02 dict plus the ten-line runner, and show six correct verdicts. One file and one drawing — no report.
Full specification: Adopt a Machine →Fall 2026 · Section 001 · Class #2021 · 3 credits
AI 232
Theory of Computation
This course examines what can be computed, what cannot, and what can be computed efficiently. Students study finite automata, context-free grammars, pushdown automata, and Turing machines as progressively more powerful models of computation, and then confront the limits of computation itself through decidability and complexity. The course is taught constructively: rather than treating these models as abstractions on a page, students implement them as working simulators and use them to answer concrete questions about real languages and real programs.
Tue & Thu 6:00 – 7:50 PM
Online — all sessions live on Google Meet
Room of record: Library Learning 4FL B
Dial in: +1 585-969-5075 · PIN 894 153 012# · more numbers
Lecture notes
Session Notes
Posted before the session they're used in and kept available all term. Each set is a self-contained page — read it, work the examples, and bring questions.
01
What Is a Computation?
WEEK 1 · S1 · SEP 3 02 The Simplest Machine
WEEK 2 · S2–S3 · SEP 8, SEP 10 03 The Machine That Guesses
WEEK 3 · S4–S5 · SEP 15, SEP 17 04 Patterns and Machines
WEEK 4 · S6–S7 · SEP 22, SEP 24 05 Where Patterns End
WEEK 5 · S8–S9 · SEP 29, OCT 1 06 Rules That Build Strings
WEEK 6 · S10–S11 · OCT 6, OCT 8 07 Machines With a Stack
WEEK 7 · S12–S13 · OCT 13, OCT 15 08 Pumping Trees, Real Parsers
WEEK 8 · S14–S15 · OCT 20, OCT 22 09 The Machine With Paper
WEEK 9 · S16–S17 · OCT 27, OCT 29 10 One Machine to Rule Them All
WEEK 10 · S18–S19 · NOV 3, NOV 5 11 The Question No Machine Can Answer
WEEK 11 · S20–S21 · NOV 10, NOV 12 12 The Impossibility Photocopier
WEEK 12 · S22–S23 · NOV 17, NOV 19
WEEK 1 · S1 · SEP 3 02 The Simplest Machine
WEEK 2 · S2–S3 · SEP 8, SEP 10 03 The Machine That Guesses
WEEK 3 · S4–S5 · SEP 15, SEP 17 04 Patterns and Machines
WEEK 4 · S6–S7 · SEP 22, SEP 24 05 Where Patterns End
WEEK 5 · S8–S9 · SEP 29, OCT 1 06 Rules That Build Strings
WEEK 6 · S10–S11 · OCT 6, OCT 8 07 Machines With a Stack
WEEK 7 · S12–S13 · OCT 13, OCT 15 08 Pumping Trees, Real Parsers
WEEK 8 · S14–S15 · OCT 20, OCT 22 09 The Machine With Paper
WEEK 9 · S16–S17 · OCT 27, OCT 29 10 One Machine to Rule Them All
WEEK 10 · S18–S19 · NOV 3, NOV 5 11 The Question No Machine Can Answer
WEEK 11 · S20–S21 · NOV 10, NOV 12 12 The Impossibility Photocopier
WEEK 12 · S22–S23 · NOV 17, NOV 19
Fifteen weeks
Weekly Schedule
The schedule is aligned to the LIU Brooklyn academic calendar; any session affected by a University holiday or closure is adjusted and announced in class and on Brightspace. The current week is highlighted.
| Week | Sessions | Topic | Materials | To do |
|---|---|---|---|---|
| WK 1 | S1 · Sep 3 | Course overview. Sets, proofs, strings, alphabets, and formal languages | Notes 01 |
|
| WK 2 | S2–S3 · Sep 8, Sep 10 | Deterministic finite automata: definition, computation, and construction | Notes 02 |
|
| WK 3 | S4–S5 · Sep 15, Sep 17 | Nondeterministic finite automata and the subset construction | Notes 03 |
|
| WK 4 | S6–S7 · Sep 22, Sep 24 | Regular expressions, equivalence with automata, and closure properties | Notes 04 |
|
| WK 5 | S8–S9 · Sep 29, Oct 1 | The pumping lemma for regular languages. Myhill–Nerode and minimization | Notes 05 |
|
| WK 6 | S10–S11 · Oct 6, Oct 8 | Context-free grammars, derivations, parse trees, and ambiguity | Notes 06 |
|
| WK 7 | S12–S13 · Oct 13, Oct 15 | Pushdown automata and the equivalence of PDAs and CFGs | Notes 07 |
|
| WK 8 | S14–S15 · Oct 20, Oct 22 | The pumping lemma for context-free languages. Parsing in practice Project 1 due (Oct 19) |
Notes 08 |
|
| WK 9 | S16–S17 · Oct 27, Oct 29 | Turing machines: the model, configurations, and variants | Notes 09 |
|
| WK 10 | S18–S19 · Nov 3, Nov 5 | The Church–Turing thesis. Decidable and recognizable languages | Notes 10 |
|
| WK 11 | S20–S21 · Nov 10, Nov 12 | Undecidability, diagonalization, and the halting problem Project 2 due (Nov 9) |
Notes 11 |
|
| WK 12 | S22–S23 · Nov 17, Nov 19 | Mapping reductions and Rice's theorem Project 3 due (Nov 16) |
Notes 12 |
|
| WK 13 | S24 · Nov 24 | Time complexity, the class P, nondeterminism, and the class NP◦ Nov 26 — no class (Thanksgiving) Capstone proposal due |
Notes 13 · soon |
|
| WK 14 | S25–S26 · Dec 1, Dec 3 | NP-completeness, the Cook–Levin theorem, and polynomial-time reductions | Notes 14 · soon |
|
| WK 15 | S27–S28 · Dec 8, Dec 10 | Space complexity and PSPACE. Capstone presentations | Notes 15 · soon |
|
| FINALS | Dec 14 – 21 | Final capstone deliverables due. No final examination. | ||
No examinations
Projects & Grading
This course is graded entirely on four hands-on projects — there are no exams. Specifications and rubrics are released at least two weeks before each due date. Every project is submitted as a Git repository plus a written report; late work is reduced by 10% per calendar day.
Project 225%
Invent a Tiny Language
Invent a language of your own — pizza orders, dance moves, potion recipes — write its grammar as the Notes 06 dictionary, and watch a provided script speak it and certify it with the stack machine. One file and one screenshot — no report.
Full specification: Invent a Tiny Language →Project 325%
Turing Machine Workbench
Implement a Turing machine simulator supporting multiple tape variants, encode several decidable and recognizable languages on it, and produce a written demonstration of why the halting problem cannot be solved by any such machine.
Specification released in classProject 425%
Capstone: Reductions and Complexity
Build a reduction toolkit that transforms instances of one NP-complete problem into another (for example, 3-SAT to Clique to Vertex Cover), verify the transformations empirically with a solver, and present the complexity argument in a technical report and a live presentation.
Specification released in classGrading rubric — how every project is assessed
Every project is graded on the same four criteria. Each project rubric is released with its specification.
| Criterion | Weight | What is assessed |
|---|---|---|
| Correctness and completeness | 35% | The artifact does what the specification requires, and the required cases are handled. |
| Implementation quality | 20% | Structure, readability, and evidence of testing. Commit history shows sustained individual work. |
| Analysis and written report | 25% | The report explains the design, justifies the decisions, and reports results honestly, including what did not work. |
| Demonstration and defense | 20% | The student can run the artifact live and answer questions about any part of it. |
Grading scale
| Letter | Range % | GPA |
|---|---|---|
| A | 93–100 | 4.00 |
| A- | 90–92 | 3.67 |
| B+ | 87–89 | 3.33 |
| B | 83–86 | 3.00 |
| B- | 80–82 | 2.67 |
| C+ | 77–79 | 2.33 |
| C | 73–76 | 2.00 |
| C- | 68–72 | 1.67 |
| D | 60–67 | 1.00 |
| F | < 60 | 0.00 |
Expected time commitment (160 h total)
| Synchronous class sessions | 51 h |
| Review of posted notes | 30 h |
| Project 1 — Adopt a Machine | 17 h |
| Project 2 — Invent a Tiny Language | 20 h |
| Project 3 — Turing Machine Workbench | 20 h |
| Project 4 — Capstone and presentation | 22 h |
| Total | 160 h |
The fine print
Course Info & Policies
Prerequisites
College-level discrete mathematics and programming proficiency in a language of your choice, or permission of the instructor.
Software & tools — all free
- Python 3.11 or later (primary language for all projects; another language may be used with prior approval)
- Git and a personal GitHub account
- A code editor of your choice (VS Code recommended)
- JFLAP or an equivalent automaton visualizer (optional, for exploration)
- Google Meet, for all synchronous class sessions
What you'll be able to do
- Construct finite automata, regular expressions, and context-free grammars for a specified language, and prove that the construction is correct.
- Prove that a given language is not regular or not context-free using the appropriate pumping lemma or the Myhill–Nerode theorem.
- Implement working simulators for finite automata, pushdown automata, and Turing machines, and use them to test language membership.
- Explain the Church–Turing thesis and demonstrate the undecidability of the halting problem.
- Construct polynomial-time reductions between problems and use them to argue NP-completeness.
- Communicate a formal argument clearly in writing and defend a computational-theory result in a technical presentation.
Live sessions & attendance
All class sessions are held live on Google Meet at the scheduled times. Students are expected to attend, to have their development environment running, and to be able to share their screen when demonstrating work. Every student presents current work and takes part in critique at each meeting.
Communication
Modes of communication are Brightspace (lms.liu.edu) and email; expect a reply within 24 hours. Virtual office hours are held by appointment — email the instructor to schedule.
Materials & this site
All course notes, examples, and project specifications are distributed through the course repository and this site. Students are responsible for reviewing the current version before each session.
Submission & late work
Every project is submitted through Brightspace as a link to the student's Git repository, together with the written report. Commit history is part of the evidence of individual work. Late work is reduced by 10% per calendar day. Extensions are granted only for a documented medical or family emergency, requested before the deadline by email.
Individual work & AI use
Projects are individual work unless a specification explicitly designates a team deliverable. Discussing approaches is fine, but submitted code, models, and writing must be your own. Generative AI tools may be used as a learning aid and are treated like any other reference: any AI-assisted portion of a submission must be disclosed in the project report, and you must be able to explain and defend every line of what you submit.
Recording
Recording of class sessions by students is not permitted without the instructor's prior written consent.
Accommodations
Students with a documented disability/impairment who require reasonable accommodations should provide an Accommodation Letter from Student Support Services (Sloan Building, 1st Floor · 718-488-1044 · studentsupportservices@brooklyn.liu.edu · Mon–Fri 9am–5pm).
Technical issues
For issues with Brightspace, LIU email, Google Meet, or campus network access, contact IT: It@liu.edu · 718-488-3300 (Mon–Fri 9am–5pm).