Juliette Kennedy – Gödel’s Reception of Turing’s Model of Computability: the Shift of Perception in 1934
Initially the logicians working in Princeton in the 1930s viewed the intuitive concept, “human calculability following a fixed routine” in terms of calculability in a logic. Later they viewed the concept as being more adequately expressed by Turing’s model. In this talk we consider a shift of perception—one in which Gödel was a key figure—in relation to Gödel’s philosophical outlook subsequently. On the way we consider a question that Kripke has asked recently: why did Gödel not see that the Entscheidingsproblem is an immediate consequence of the Completeness and Incompleteness Theorems?
Jan von Plato – Rosa Politzer and the beginnings of the theory of computable functions
The Hungarian mathematician Rosa Politzer (1906-1977) studied as the first one computable functions for their intrinsic mathematical interest, in a series of papers written between 1932 and 1936. She was inspired by the teaching of Bernays, through the mediation of her friend Kalmar, and by the use of primitive recursive functions in Gödel’s incompleteness paper. Politzer’s early results were on the relations between various forms of recursion, on the method of diagonalization, and on the Ackermann function. Unpublished sources show that in the summer of 1933, she worked with Bernays in Göttingen, which led to the incorporation of her results in the long chapter on recursion theory of the Grundlagen der Mathematik Bernays finished in 1934. These sources also show the discrimination Politzer had to face as a Jew, leading to a change of surname, and in the end to a narrow escape from the 1944 mass deportation of the Jews of Budapest to Auschwitz. After the war, Politzer authored the first monograph on computability theory, the Rekursive Funktionen published under the name of Rozsa Peter in 1951.
Hector Zenil – Computability and Causality
I will explain how algorithmic information theory–the mathematical theory of randomness; and algorithmic probability–the theory of optimal induction, both heavily based upon Computability/Recursion theory, can be used in surprising applications as far as network science and molecular biology in the challenge of causality discovery providing new and powerful tools to study and steer artificial and biological systems such as cellular automata and genetic regulatory networks to reveal key evolving mechanisms of these systems.
Cliff Jones – Turing’s 1949 paper in context
Anyone who has written one knows how frustratingly difficult it can be to perfect a computer program. Several of the founding fathers of computing recognised the difficulty and in early papers set out ideas for reasoning about software — one would say today ‘techniques for proving that a program satisfies its specification’. Alan Turing presented a paper entitled ‘Checking a Large Routine’ that laid out a workable method for reasoning about programs. Sadly his paper had little impact. Understanding the problem faced, Turing’s proposal and what followed provides insight into how ideas evolve. Comparing three contributions from the 1940s with the current state of the art clarifies a problem that still costs society a fortune each year.