Course syllabus
Welcome to Models of Computations
This course is both part of the Master in Logic and available as a free standing course. The first part of the course runs in parallel with the course on Set theory and the the second part with the course on Modal logic.
Course instructor and coordinator
Gianluca Curzi (gianluca.curzi@gu.se)
Course content
PART 1: Automata and languages (Chapters 1 & 2)
- Deterministic finite automata (Section 1.1)
- Nondeterministic finite automata (Section 1.2)
- Regular expressions + equivalence with DFAs (Section 1.3)
- Pumping lemma for DFA (Section 1.4)
- Context-free grammars (Section 2.1)
- Push-down automata + Equivalence of CFGs and PDAs (Section 2.2)
PART 2: Computability and complexity
- Brief recap on Turing machines, decidability and reducibility (Chapters 3,4 & 5, see also course Logical Theory)
- Big O notation (Section 7.1)
- Time complexity: the classes P and NP (Sections 2 & 3), NP-completeness and examples of NP-complete problems (Sections 7.4 & 5)
- Space complexity: the class PSPACE and Savitch's theorem (8.1 & 2)
PART 3: Basic recursion theory
- Primitive recursive functions (see Logical Theory)
Registration
You will be able to register on the course one week before it starts. When you have registered for the course you will get access to more course information.
You can find information regarding registration here.
Schedule
Below are links to the schedule in TimeEdit. There are two links - one which require login (your GU account) and one that does not. The link requiring login shows some additional information.
Schedule for LOG115 without login and with login
The schedule is preliminary until two weeks before the course starts. Please also note that the schedule is a "living document" and could be subject to changes throughout the semester. Make a habit of checking it every once in a while!
Course Syllabus and literature list
You can search for the course code (and other courses) on https://www.gu.se/en/study-gothenburg/study-options/find-syllabus-and-reading-list?hits=25 to find the course syllabi and literature list.
The course will follow the handbook Introduction to the Theory of Computation by Michael Sipser, 3rd edition, 2013.
Examination
3 hand-in Assignments and a written examination.
Special pedagogical support
If you have a disability and are in need of special pedagogical support please see the information available at the student portal.
Contact information
- Course coordinator Gianluca Curzi gianluca.curzi@gu.se answers questions about the course content, literature and schedule.
- Education administrator Sandra Schriefer, sandra.schriefer@gu.se answers questions about registration, study interruptions, study breaks, certificates, etc.
- Education administrator Annika Herrström, annika.herrstrom@gu.se answers questions about examination administration.
- Program Coordinator Ivan Di Liberti, ivan.di.liberti@gu.se is responsible for programme issues and study guidance for students of the programme.
Plagiarism and academic integrity
Please take the time to go through the module Academic Integrity 1 to make sure that you understand what plagiarism is, why one should not plagiarise, and what happens if one does plagiarise.
Student information
Welcome to the department of Philosophy, Linguistics and Theory of Science