We introduce a realisability semantics for infinitary intuitionistic set theory that is based on Ordinal Turing Machines (OTMs). We show that our notion of OTM-realisability is sound with respect to certain systems of infinitary intuitionistic logic, and that all axioms of infinitary Kripke-Platek set theory are realised. Finally, we use a variant of our notion of realisability to show that the propositional admissible rules of (finitary) intuitionistic Kripke-Platek set theory are exactly the admissible rules of intuitionistic propositional logic.

We study the computational strength of resetting $α$-register machines, a model of transfinite computability introduced by P. Koepke in \cite{K1}. Specifically, we prove the following strengthening of a result from \cite{C}: For an exponentially closed ordinal $α$, we have $L_α\models$ZF$^{-}$ if and only if COMP$^{\text{ITRM}}_α=L_{α+1}\cap\mathfrak{P}(α)$, i.e. if and only if the set of $α$-ITRM-computable subsets of $α$ coincides with the set of subsets of $α$ in $L_{α+1}$. Moreover, we show that, if $α$ is exponentially closed and $L_α\not\models$ZF$^{-}$, then COMP$^{\text{ITRM}}_α=L_{β(α)}\cap\mathfrak{P}(α)$, where $β(α)$ is the supremum of the $α$-ITRM-clockable ordinals, which coincides with the supremum of the $α$-ITRM-computable ordinals. We also determine the set of subsets of $α$ computable by an $α$-ITRM with time bounded below $δ$ when $δ>α$ is an exponentially closed ordinal smaller than the supremum of the $α$-ITRM-clockable ordinals. Moreover, we obtain some sufficient and necessary conditions on ordinals $α$ for which the $α$-wITRM-clockable ordinals are bounded by $α$.

We consider notions of space complexity for Infinite Time Turing Machines (ITTMs) that were introduced by B. Löwe and studied further by J. Winter. We answer several open questions about these notions, among them whether low space complexity implies low time complexity (it does not) and whether one of the equalities P=PSPACE, P$_{+}=$PSPACE$_{+}$ and P$_{++}=$PSPACE$_{++}$ holds for ITTMs (all three are false). We also show various separation results between space complexity classes for ITTMs. This considerably expands our earlier observations on the topic in section 7.2.2 of \cite{Ca2}, which appear here as Lemma $6$ up to Corollary $9$.

We study randomness beyond $Π^1_1$-randomness and its Martin-Löf type variant, introduced in \cite{MR2340241} and further studied in \cite{Continuous-higher-randomness}. The class given by the infinite time Turing machines (\ITTM s), introduced by Hamkins and Kidder, is strictly between $Π^1_1$ and $Σ^1_2$. We prove that the natural randomness notions associated to this class have several desirable properties resembling those of the classical random notions such as Martin-Löf randomness, and randomness notions defined via effective descriptive set theory such as $Π^1_1$-randomness. For instance, mutual randoms do not share information and can be characterized as in van Lambalgen's theorem. We also obtain some differences to the hyperarithmetic setting. Already at the level of $Σ^1_2$, some properties of randomness notions are independent \cite{Infinite-computations}. Towards the results about randomness, we prove the following analogue to a theorem of Sacks. If a real is infinite time Turing computable relative to all reals in some given set of reals with positive Lebesgue measure, then it is already infinite time Turing computable. As a technical tool, we prove facts of independent interest about random forcing over admissible sets and increasing unions of admissible sets. These results are also useful for more efficient proofs of some classical results about hyperarithmetic sets.

Abstract Exploring further the properties of ITRM-recognizable reals started in [1], we provide a detailed analysis of recognizable reals and their distribution in Gödels constructible universe L. In particular, we show that new unrecognizable reals are generated at every index $\gamma \, \ge \,\omega _\omega ^{CK}$ . We give a machine-independent characterization of recognizability by proving that a real r is recognizable if and only if it is ${\Sigma _1}$ -definable over ${L_{\omega _\omega ^{CK,\,r}}}$ and that $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ for every recognizable real r and show that either every or no r with $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ generated over an index stage ${L_\gamma }$ is recognizable. Finally, the techniques developed along the way allow us to prove that the halting number for ITRMs is recognizable and that the set of ITRM-computable reals is not ITRM-decidable.