Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

We extend the theory of “Fine structure and iteration trees” to models having more than one Woodin cardinal.

In this paper I shall present a method for proving determinacy from large cardinals which, in many cases, seems to yield optimal results. One of the main applications extends theorems of Martin, Steel and Woodin about determinacy within the projective hierarchy. The method can also be used to give a new proof of Woodin's theorem about determinacy in L.The reason we look for optimal determinacy proofs is not only vanity. Such proofs serve to tighten the connection between large cardinals and (...) descriptive set theory, letting us bring our knowledge of one subject to bear on the other, and thus increasing our understanding of both. A classic example of this is the Harrington-Martin proof that -determinacy implies -determinacy. This is an example of a transfer theorem, which assumes a certain determinacy hypothesis and proves a stronger one. While the statement of the theorem makes no mention of large cardinals, its proof goes through 0#, first proving that-determinacy ⇒ 0# exists,and then that0# exists ⇒ -determinacyMore recent examples of the connection between large cardinals and descriptive set theory include Steel's proof thatADL ⇒ HODL ⊨ GCH,see [9], and several results of Woodin about models of AD+, a strengthening of the axiom of determinacy AD which Woodin has introduced. These proofs not only use large cardinals, but also reveal a deep, structural connection between descriptive set theoretic notions and notions related to large cardinals. (shrink)

We generalize ordinary register machines on natural numbers to machines whose registers contain arbitrary ordinals. Ordinal register machines are able to compute a recursive bounded truth predicate on the ordinals. The class of sets of ordinals which can be read off the truth predicate satisfies a natural theory SO. SO is the theory of the sets of ordinals in a model of the Zermelo-Fraenkel axioms ZFC. This allows the following characterization of computable sets: a set of ordinals is ordinal register (...) computable if and only if it is an element of Gödel’s constructible universe L. (shrink)

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set (...) to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}$ sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not ${n \in r}$ with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs. (shrink)

We analyze the effect of replacing several natural uses of definability in set theory by the weaker model-theoretic notion of algebraicity. We find, for example, that the class of hereditarily ordinal algebraic sets is the same as the class of hereditarily ordinal definable sets; that is, $\mathrm{HOA}=\mathrm{HOD}$. Moreover, we show that every algebraic model of $\mathrm{ZF}$ is actually pointwise definable. Finally, we consider the implicitly constructible universe Imp—an algebraic analogue of the constructible universe—which is obtained by iteratively adding not only (...) the sets that are definable over what has been built so far, but also those that are algebraic over the existing structure. While we know that $\mathrm{Imp}$ can differ from $L$, the subtler properties of this new inner model are just now coming to light. Many questions remain open. (shrink)

I develop a translation procedure between λ-structures, which correspond to premice in the Friedman–Jensen indexing convention on the one hand and s-structures, which are essentially the same as premice in the Mitchell–Steel indexing scheme.

We investigate various strong notions of rigidity for Souslin trees, separating them under ♢ into a hierarchy. Applying our methods to the automorphism tower problem in group theory, we show under ♢ that there is a group whose automorphism tower is highly malleable by forcing.

We present two ways in which the model L(R) is canonical assuming the existence of large cardinals. We show that the theory of this model, with ordinal parameters, cannot be changed by small forcing; we show further that a set of ordinals in V cannot be added to L(R) by small forcing. The large cardinal needed corresponds to the consistency strength of AD L (R); roughly ω Woodin cardinals.

The Infinite Time Turing Machine model [8] of Hamkins and Kidder is, in an essential sense, a "Σ₂-machine" in that it uses a Σ₂ Liminf Rule to determine cell values at limit stages of time. We give a generalisation of these machines with an appropriate Σ n rule. Such machines either halt or enter an infinite loop by stage ζ(n) = df μζ(n)[∃Σ(n) > ζ(n) L ζ(n) ≺ Σn L Σ(n) ], again generalising precisely the ITTM case. The collection of (...) such machines taken together computes precisely those reals of the least model of analysis. (shrink)

We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting and (...) resetting infinite-time register machines, and α-Turing machines for countable admissible ordinals α. (shrink)

Continuing the work of Fuchs [1], I show that the translation functions developed previously map iterable λ-structures to iterable s-structures and vice versa. To this end, I analyse how the translation functions interact with the formation of extender ultrapowers and normal iterations. This analysis makes it possible to translate iterations, and, in a last step, iteration strategies, thus arriving at the result.

Infinite Time Register Machines are a well-established machine model for infinitary computations. Their computational strength relative to oracles is understood, see e.g. , and . We consider the notion of recognizability, which was first formulated for Infinite Time Turing Machines in [6] and applied to ITRM 's in [3]. A real x is ITRM -recognizable iff there is an ITRM -program P such that PyPy stops with output 1 iff y=xy=x, and otherwise stops with output 0. In [3], it is (...) shown that the recognizable reals are not contained in the ITRM -computable reals. Here, we investigate in detail how the ITRM -recognizable reals are distributed along the canonical well-ordering shrink)

We describe the inner models with representatives in all equivalence classes of thin equivalence relations in a given projective pointclass of even level assuming projective determinacy. The main result shows that these models are characterized by their correctness and the property that they correctly compute the tree from the appropriate scale. The main step towards this characterization shows that the tree from a scale can be reconstructed in a generic extension of an iterate of a mouse. We then construct models (...) with this property as generic extensions of iterates of mice under the assumption that the corresponding projective ordinal is below ω2ω2. On the way, we consider several related problems, including the question when forcing does not add equivalence classes to thin projective equivalence relations. For instance, we show that if every set has a sharp, then reasonable forcing does not add equivalence classes to thin provably View the MathML source Δ1/3 equivalence relations, and generalize this to all projective levels. (shrink)