What are the fundamental limits of computation? Do there exist well-defined problems that no computer, regardless of its power, can ever solve? This course offers a concise introduction to the core ideas of computability theory (also known as recursion theory), focusing on the boundary between the computable and the uncomputable. We begin by formalising the intuitive notion of an algorithm through models such as Turing machines and recursive (μ-recursive) functions, highlighting their equivalence under the Church–Turing thesis. Building on this foundation, we explore the classification of problems into decidable and undecidable sets, culminating in the landmark result of the Halting Problem. The series then develops the key technique of reduction to demonstrate undecidability in a broad range of settings, alongside an introduction to Rice's theorem and its implications. We also examine how computable functions can be constructed from simple initial functions using composition, primitive recursion, and minimisation, offering an arithmetic perspective on computation. We also touch on the structure underlying degrees of unsolvability and reflect on the broader significance of these results in logic, computer science, and the philosophy of computation. The course shall be accessible to anyone with a basic background in discrete mathematics.

TBA

By definition, abstract entities are entities which exist outside of space and are causally inefficacious, i.e. they cannot causally interact with anything. Prototypical examples of abstract entities include numbers, sets, functions, properties, shapes, species, colors, linguistic types, and institutions. For each of these entities, we can seemingly use singular terms (expressions whose express purpose is to refer) to refer to them. For example, we can refer to numbers using expressions like 'the number two', and we can refer to colors using expressions like 'the color red'. Such reference is puzzling, however, for two reasons. First, in many cases it threatens paradox. Thus, even if we can refer to properties, we seemingly cannot coherently refer to the property whose instances are all and only properties. Secondly, many philosophers have thought that reference is causally constrained in the sense that we cannot refer to what we cannot causally interact with. The purpose of this course is to introduce the variety of abstract entities we can seemingly refer to, the linguistic means by which we do that, and the philosophical challenges such reference poses for our best semantic and metasemantic theories.

TBA