Transcript Introductory Lecture - Homepages | The University of Aberdeen

CS3518
Languages and Computability
Kees van Deemter
[email protected]
Lectures
Monday
Tuesday
14:00 MT6
11:00 KC T2
Tutorials/Practicals
Tuesday
13:00-15:00 (one group)
and 15:00-17:00 (another),
in Meston 311
Aims of the course
• The main question of the course:
– What problems can be solved on a computer?
– I.e., which problems are computable?
• Different perspectives on computability exist.
In most of these, problems are seen as formal
languages
• Hence, we start talking about formal languages
– only the basics!
Aims of the course
• Given that we know what a problem is, how
does a solution look?
• A solution is an algorithm encoded in a
programming language
• We consider 2 types of programming languages:
– Imperative languages (e.g. JAVA)
– Functional languages (e.g. HASKELL)
– (If time allowed: logical languages, e.g. PROLOG)
Aims of the course
Hence the second and third topics of the course:
• Functional programming languages
• Imperative programming languages
Finally, we shall present the basics of
computability theory
• Just the basics!
Course structure in more detail
1.
2.
3.
4.
Formal languages
Functional programming
Imperative Programming
Computability
Course structure in more detail
1. Formal languages
–
finite state automata and regular languages
2. Functional programming
–
–
Theory: lambda calculus
Practice: Haskell
3. Imperative Programming
–
Turing machines
4. Computability
History of CS3518
• In previous years at Aberdeen, there were
several courses in this area:
– CS3511: Discrete Methods
– CS3012: Formal language and Compilers
– CD4026: Formal models of computation
• All three modules now merged into CS3518
– But some set theory and symbolic logic covered in
year 1 (Foundations of Computing 1&2)
– Please take a look at your old course notes
Let’s get started with formal languages