IAS BMVP Stanislav Speranski Public Lecture: On the discovery of incomputability and unsolvability

3 August 2017, 4.00 PM - 3 August 2017, 5.00 PM

Stanislav Speranski

Verdon-Smith Room, Royal Fort House

IAS Benjamin Meaker Visiting Fellow Stanislav Speranski will give a public lecture entitled: On the discovery of incomputability and unsolvability.


Let us start with two definitions. Call a set of objects (such as natural numbers, formulas or formal words) computable if there exists an algorithm for deciding whether or not a given object belongs to this set, and further, call an algorithmic problem of the form `Does a given object satisfy P?' with P a predicate solvable if the set of all objects that satisfy P is computable. The discovery of incomputable sets, and hence of unsolvable algorithmic problems, occupies a special place in the history of logic, methodology and philosophy of science. The most famous example of an unsolvable problem was provided by Alan Turing in 1936.

He first introduced a fundamentally important mathematical model of computability known as Turing machines, and then considered the halting problem for them, i.e. the problem of deciding whether or not a given Turing machine halts on a given input, which turned out to be unsolvable. The conventional proof of this unsolvability result has two interesting features: i. it uses the existence of a universal Turing machine, which behaves like a modern operating system for any Turing machine; ii. it involves (like the standard proof of Goedel's first incompleteness theorem) a variant of Cantor's diagonal argument. We shall discuss the significance of this result and its proof, along with their variations and generalisations, from different perspectives (historical, logical, methodological and philosophical).

The lecture will be followed by a drinks reception. All welcome, no booking required. 

Read more about Dr Speranski's visit, which is being hosted by Professor Leon Horsten (Philosophy) here.