Models of Computation

The course is included in the degree programme Logic, Master's (120 credits)programme (H2LOG) and can also be given as a freestanding course.

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.

A model for computability describes how, and if, a function or operation can be computed. The course covers many such models and how these models are related to one another. Central results and concepts in the subject area are also discussed. The course content includes:

• Finite automata
• Regular and context-free languages
• Turing computability and recursive functions
• The recursion theorem and relative Turing computability
• Basic results in complexity theory

On successful completion of the course the student will be able to:

Knowledge and understanding

• demonstrate knowledge and understanding of the different models of computation discussed in the course, and relate these to one another,
• explain and apply fundamental results relating automata theory and formal languages,
• demonstrate understanding of resource-bounded computation.

Competence and skills

• formulate and present proofs of the most important results in the course including, as well as of lemmas used in the proofs,
• apply methods and results of the course in independent problem-solving,
• design algorithms and implement them in different models of computation,
• design automata that recognise a given language and grammars that generate it,
• analyse the complexity of programs and computational problems,

Judgement and approach

• critically discuss, analyse and evaluate the results in the course as well as their applications.

Teaching is given in the form of lectures and individual assignments or group assignments.

Language of instruction: English

The course is assessed individually in written form. In addition to a final written exam, there may also be up to four compulsory homework assignments during the course.

The grading teacher may request completion of examined student achievements.

If a student who has been failed twice for the same examination element wishes to change examiner before the next examination session, such a request is to be granted unless there are specific reasons to the contrary (Chapter 6 Section 22 HF).

If a student has received a certificate of disability study support from the University of Gothenburg with a recommendation of adapted examination and/or adapted forms of assessment, an examiner may decide, if this is consistent with the course’s intended learning outcomes and provided that no unreasonable resources would be needed, to grant the student adapted examination and/or adapted forms of assessment.

If a course has been discontinued or undergone major changes, the student must be offered at least two examination sessions in addition to ordinary examination sessions. These sessions are to be spread over a period of at least one year but no more than two years after the course has been discontinued/changed. The same applies to placement and internship (VFU) except that this is restricted to only one further examination session.

If a student has been notified that they fulfil the requirements for being a student at Riksidrottsuniversitetet (RIU student), to combine elite sports activities with studies, the examiner is entitled to decide on adaptation of examinations if this is done in accordance with the Local rules regarding RIU students at the University of Gothenburg.

The course is given one of the grades Pass with distinction (VG), Pass (G) and Fail (U). All compulsory elements of the course must be completed to obtain a passing grade. To receive a Pass with distinction, it is furthermore required that the final exam receives the assessment Pass with distinction.

Students who participate in or have completed the course are given the opportunity to anonymously express their experiences of and views on it in a course evaluation. A compilation of the course evaluation and the reflection of the teacher responsible for the course is made available to the students within a reasonable time after the end of the course. The next time the course is given, the summary and any implemented measures will be presented.

The course requires access to a computer (or equivalent) with internet connection.
The course may not be included in the degree together with the course LOG260.