This course introduces the foundational theory of computation through the study of formal models such as finite automata, pushdown automata, and Turing machines, along with key ideas in computability and complexity. You will learn to reason rigorously about computational models, distinguish between decidable and undecidable problems, and classify problems based on their computational difficulty. These skills provide the theoretical basis for further studies in algorithms, programming languages, cryptography, and AI.
- AUs
- 3.0 AUs
- Grade Type
- None
- Prerequisite
- SC1007, SC2001(Corequisite), SC2301(Corequisite)
- Exam
- None
Prerequisite graph
Required first
SC1007Data Structures & AlgorithmsAutomata, Computability & Complexity
Available indexes
| Mon | Tue | Wed | Thu | Fri | ||
|---|---|---|---|---|---|---|
| 1030 | COMMON LEC (SCL2) 1030-1120 Thu LT3 Wk1-9,11-13 | |||||
| 1100 | ||||||
| 1130 | ||||||
| 1200 | ||||||
| 1230 | ||||||
| 1300 | ||||||
| 1330 | ||||||
| 1400 | ||||||
| 1430 | COMMON LEC (SCL2) 1430-1520 Tue LT3 Wk1-9,11-13 | |||||
| 1500 | ||||||
| 1530 | 10308 TUT (SDDA) 1530-1620 Tue TR+3 Wk2-9,11-13 | 10309 TUT (SDDB) 1530-1620 Tue TR+4 Wk2-9,11-13 | ||||
| 1600 | ||||||
Other offerings
Other relevant mods
- SC1001Introduction to Computational Thinking & Programming
- SC1004Linear Algebra for Computing
- SC1005Digital Logic
- SC1006Computer Organisation & Architecture
- SC1007Data Structures & Algorithms
- SC1008C & C++ Programming
- SC1124Math 2: Discrete Structures for Computing
- SC1304Artificial Intelligence for Social Good
- SC1305Linear Algebra
Planning guides
View all articlesSTARS · 9 min read
NTU STARS Guide 2026: Registration Rounds, Bidding & Planner Tips
NTU STARS planner guide — how bidding rounds work, how to prepare a shortlist before registration opens, and what to do when a module fills up. Includes a free STARS planner tool.
Module Planning · 6 min read
NTU Degree Audit: How to Check Your Graduation Requirements
How the NTU degree audit works, where to find it, and how to read it against your programme's core, BDE, UE, and AU requirements before you register for modules.
Module Planning · 6 min read
How to Plan NTU Modules Before STARS Opens: Step-by-Step
Step-by-step guide to planning NTU modules using NTUMods — map degree requirements, build your timetable, check prerequisites, balance workload, and lock in your plan before STARS bidding starts.