CS151 | Discrete Structures |
This module will cover predicate logic and set theory, which will provide a basic tool-kit for formal descriptions in computer science. The topics covered will include:
As well as proving a basis for formal descriptions, logic is used in software engineering (e.g. OCL, design-by-contract, Spec#), logic-based techniques are important in program analysis (e.g. pointer analysis, object ownership), and logics can be used to formulate advanced type systems for programming languages (polymorphism, generics and higher-order types). One of the most important logical problems, the Entscheidungsproblem was a key motivation in the foundation of computer science in the 1930s. The textbook is
See also: university module description | |
CS314 | Computational Epistemology |
The aim of this module is to explore the relationship between uncertainty, logic and computation. Traditionally, logic and computation have focused on the deduction of certain knowledge, neglecting the role of uncertainty and its computational manifestation. One component of the module will focus on epistemic modal logic, which extends formal classical logics to express reasoning about knowledge and information. Another component will consider the computational nature of reliability and its role in defining standards of measurement and systems of representation. Concepts such as the measurement problem, the private language argument, logical depth and the connection between data compression, prediction and understanding will be explored, with a focus on how finite objects can be used to reliably communicate Platonic ideals. On successful completion of the module, students should be able to:
See also: university module description | |
CS434 | Readings in the Foundations of Computer Science |
This module explores the foundation of Computer Science, laid with the discovery of (computationally) unsolvable problems in the 1930s. A particular feature of the module is its focus on reading primary sources from the period, starting with Gödel's 1931 incompleteness theorem and moving on through the results of Church, Turing and Post in 1936. Here, "primary sources" are taken as being the published research work of scientists, in their full and original form (or in translation). The central idea is to bypass all interpretations, simplifications and explanations, and put you in direct contact with the words of these pioneers, as one scientist to another. The historical and scientific background, from Frege and Russell through Hilbert's programme is also reviewed. In this context, computer science can be seen as part of a tradition of human enquiry spanning many generations, rather than just a collection of technological novelties. This module lays a solid basis for considering future developments in the foundations of computer science. The papers we'll be covering are:
General ReadingThis module is fairly theoretical in content, and will be based closely on the above papers. Some text related to these papers include:
See also: university module description | |