Computability

About this programme

No fees are charged for EU and EEA citizens, Swedish residence permit holders and exchange students. More information about tuition fees This course is about the concept of "computation": how it can be modelled, and what its limits are. To avoid unnecessary complexity one often chooses to study computation via simplified, but powerful, models. These models can for instance be simple programming languages (like the -calculus), or idealised computers (like Turing machines). In thecourse several such models will be studied, both "imperative" and "functional". One or more models will be used to explore the limits of computation: problems that cannot be solved (within the confines of a given model), and programs that can run arbitrary programs (modelled in a certain way).The course also includes a discussion of the Church-Turing thesis, a hypothesis which states, roughly, that a function is computable in a certain intuitive sense only if it can be defined within one of several models of computation. To be eligible to the course, the student should have successfully completed 120 credits of studies in Computer Science or equivalent. - 7\.5 credits in discrete mathematics (e.g., DIT980 Discrete Mathematics for Computer Scientists) - 7\.5 credits in functional programming (e.g., DIT143 Functional Programming or DIT440 Introduction to Functional Programming) Applicants must prove knowledge of English: English 6/English level 2 or the equivalent level of an internationally recognized test, for example TOEFL, IELTS.