Models of Computation
Summary
Explore the Foundations of Computation
About
How do we know what computers can and cannot do? This course takes you to the very core of computer science by exploring the fundamental models of computation and the limits of algorithmic problem-solving.
You’ll study a range of powerful computational models—from finite automata and formal languages to Turing machines and recursive functions—and discover how they connect to each other. Along the way, you’ll engage with key ideas in computability and complexity theory, gaining insight into how efficiently problems can be solved—or whether they can be solved at all.
What you’ll gain
By the end of the course, you will:
Understand and compare different models of computation
Work confidently with automata, grammars, and formal languages
Design algorithms and implement them across multiple computational frameworks
Construct automata and grammars for specific languages
Analyse the complexity of algorithms and computational problems
Develop and present rigorous proofs of central theoretical results
Think like a computer scientist
Beyond technical skills, you’ll learn to critically evaluate computational methods and their real-world implications—an essential ability in today’s data-driven world.
A hands-on, analytical learning experience
Through problem-solving, proof-writing, and design tasks, you’ll build both theoretical insight and practical competence in understanding computation at a deep level.
This course is ideal for students who want to understand the true power—and limits—of computation, and who are ready to tackle the theory behind modern computer science.
Prerequisites and selection
Entry requirements
Admission to the course requires successful completion of
- at least 60 credits in total in the subject areas mathematics, logic, computer scienceor formal linguistics, or
- at least 90 credits in philosophy or linguistics, and at least 30 credits in total in the subject areas mathematics, logic, computer science or formal linguistics,
or equivalent knowledge. English 6 or equivalent is also required.
Selection
Selection is based upon the number of credits from previous university studies, maximum 165 credits.
Facilities
The Faculty of Humanities is located in the Humanisten building at Renströmsgatan 6. The Department of Philosophy, Linguistics and Theory of Science has its premises on the 5th floor. Both the Faculty of Humanities and the adjacent Humanities Library offer several study areas and group rooms.
More information about facilities
Teaching is given in the form of lectures and individual assignments or group assignments.
