Infinite time computable model theory

This survey paper examines the effective model theory obtained with the BSS model of real number computation. It treats the following topics: computable ordinals, satisfaction of computable infinitary formulas, forcing as a construction technique, effective categoricity, effective topology, and relations with other models for the effective theory of uncountable structures.

We present the model theoretic concepts that allow mathematics to be developed with the notion of the potential infinite instead of the actual infinite. The potential infinite is understood as a dynamic notion, being an indefinitely extensible finite. The main adoption is the interpretation of the universal quantifier, which has an implicit reflection principle. Each universal quantification refers to an indefinitely large, but finite set. The quantified sets may increase, so...

We consider the question whether there is an infinitary analogue of the Church-Turing-thesis. To this end, we argue that there is an intuitive notion of transfinite computability and build a canonical model, called Idealized Agent Machines ($IAM$s) of this which will turn out to be equivalent in strength to the Ordinal Turing Machines defined by P. Koepke.

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for functions f:R-->N, the same class of computable functions. Nevertheless, there are infinite time computable functions f:R-->R that are not one-tape computable, and so the two models of supertask computation are not equivalent. Surp...

This paper deals with formulas of set theory which force the infinity. For such formulas, we provide a technique to infer satisfiability from a finite assignment.

An essay on Model Theory: Why am I interested in model theory? What are, in my opinion, the most challenging problems in model theory?

We introduce an analog of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce a...

We present a dynamic model theory that avoids the paradoxes stemming from completed infinities, but does not require any translation of formulae. The main adoption is the replacement of an actual infinite carrier set by a potential infinite one, and by a finitistic interpretation of the universal quantifier.

This paper extends our paper \cite{C2} for the conference ``Computability in Europe'' 2022. After Infinite Time Turing Machines (ITTM) were introduced in Hamkins and Lewis \cite{HL}, a number of machine models of computability have been generalized to the transfinite, along with various variants thereof. While for some of these models the computational strength has been successfully determined, there are still several white spots on the map of transfinite computability. In ...

By a theorem of Sacks, if a real $x$ is recursive relative to all elements of a set of positive Lebesgue measure, $x$ is recursive. This statement, and the analogous statement for non-meagerness instead of positive Lebesgue measure, have been shown to carry over to many models of transfinite computations. Here, we start exploring another analogue concerning recognizability rather than computability. We introduce a notion of relativized recognizability and show that, for Infin...