(1) Simple models in Malament-Hogarth spacetimes, up to (Δ_1)~1 or HYP. (2) Ordinal Time Register Machines: up to (Π_1)~1-CA_0. (3) Infinite Time Turing Machines: up to (Π_2)~1-CA_0 +Det((Σ_2)~0) and beyond. In this paper we survey some of the complexity issues surrounding discrete models of transfinite recursion. We emphasise today the connections with Proof Theory, Reverse Mathematics, and Subsystems of Second Order Number Theory as set forth in Simpson's [13]. Our concerns are thus mainly the logico-mathematical ones of analysing such models rather 'implementational concerns' (to put it broadly).
展开▼
