Page History

Versions Compared


  • This line was added.
  • This line was removed.
  • Formatting was changed.


Wednesday 11.5.2022 12-14, C124 POSTPONED TWO WEEKS CANCELLED
Joint talk: Jean Luis Gastaldi, Luc Pellesier


Wednesday 25.5.2022 12-14, B121 + Zoom

Informal lecture by Philip Welch

Title: Reworking Kleene's Higher Type Recursions

Abstract: In the late 50's and early 60's Kleene wrote four papers on recursion in finite types. In two of them he gave an equation theoretic basis for such recursions, making it look rather like extensions of Goedel-Herbrand recursion. These two papers were very influential. In the other two papers he gave an alternative definition using Turing machines and showed their equivalence. The latter papers seem not to have had any substantial consequences, or indeed readership. Nevertheless they produce in type 2, a notion of computation whereby the 'halting problem' in this context is a complete Pi^1_1 set of integers, or equivalently a complete GSIgma^0_1 set. By taking Kleene's idea and reworking it for infinite time Turing machines (ITTM's) one has a halting problem that is a complete GSIgma^0_3 set, thereby neatly tying in ITTM's with classical descriptive set theory.

Talks of the fall term 2021