We consider the first-order theory of the monoid P(A*) of languages over a finite or infinite alphabet A (with at least two letters) endowed solely with concatenation lifted to sets: no set theoretical predicate or function, no constant. Coding a word u by the submonoid u* it generates, we prove that the operation (u*, v*) → (uv)* and the predicate {(u*,X) | ε ∈ X, u ∈ X} are definable in 〈P(A*); ·,=〉. This allows to interpret the second-order theory of 〈A*; ·,=〉 in the first-order theory of 〈P(A*); ·,=〉 and prove the undecidability of the Π 8 fragment of this last theory. These results involve technical difficulties witnessed by the logical complexity of the obtained definitions: the above mentioned predicates are respectively Δ 5 and Δ 7 .

What parts of the classical descriptive set theory done in Polish spaces still hold for more general topological spaces, possibly T0 or T1, but not T2 (i.e. not Hausdorff)? This question has been addressed by Selivanov in a series of papers centred on algebraic domains. And recently it has been considered by de Brecht for quasi-Polish spaces, a framework that contains both countably based continuous domains and Polish spaces. In this paper, we present alternative unifying topological spaces, that we call approximation spaces. They are exactly the spaces for which player Nonempty has a stationary strategy in the Choquet game. A natural proper subclass of approximation spaces coincides with the class of quasi-Polish spaces. We study the Borel and Hausdorff difference hierarchies in approximation spaces, revisiting the work done for the other topological spaces. We also consider the problem of effectivization of these results.

We prove some results on the Wadge order on the space of sets of natural numbers endowed with Scott topology, and more generally, on omega-continuous domains. Using alternating decreasing chains we characterize the property of Wadge hardness for the classes of the Hausdorff difference hierarchy (iterated differences of open sets). A similar characterization holds for Wadge one-to-one and finite-to-one completeness. We consider the same questions for the effectivization of the Wadge relation. We also show that for the space of sets of natural numbers endowed with the Scott topology, in each class of the Hausdorff difference hierarchy there are two strictly increasing chains of Wadge degrees of sets properly in that class. The length of these chains is the rank of the considered class, and each element in one chain is incomparable with all the elements in the other chain.

We consider computable functionals mapping the Baire space into the set of integers. By continuity, the value of the functional on a given function depends only on a "critical" finite part of this function. Care: there is in general no way to compute this critical finite part without querying the function on an arbitrarily larger finite part! Nevertheless, things are different in case there is a uniform bound on the size of the domain of this critical finite part. We prove that, modulo a quadratic blow-up of the bound, one can compute the value of the functional by an algorithm which queries the input function on a uniformly bounded finite part. Up to a constant factor, this quadratic blow-up is optimal. We also characterize such functionals in topological terms using uniformities. As an application of these results, we get a topological characterization of the dynamics of algorithms as modeled by Gurevich's Abstract State Machines.

It is well-known that Abstract State Machines (ASMs) can simulate ``step-by-step" any type of machines (Turing machines, RAMs, etc.). We aim to overcome two facts: 1) simulation is not identification, 2) the ASMs simulating machines of some type do not constitute a natural class among all ASMs. We modify Gurevich's notion of ASM to that of EMA (``Evolving MultiAlgebra") by replacing the program (which is a syntactic object) by a semantic object: a functional which has to be very simply definable over the static part of the ASM. We prove that very natural classes of EMAs correspond via ``literal identifications'' to slight extensions of the usual machine models and also to grammar models. Though we modify these models,we keep their computation approach: only some contingencies are modified. Thus, EMAs appear as the mathematical model unifying all kinds of sequential computation paradigms.

Abstract We obtain a large class of significant examples ofn-random reals (i.e., Martin-Löf random in oracle ∅(n−1)) à la Chaitin. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite (resp. finite large enough, resp. finite self-delimited) inputs produces an output in a given set . In particular, we develop methods to transfer many-one completeness results of index sets ton-randomness of associated probabilities.

Abstract We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: • ΩU[X] is random whenever X is Σn0-complete or Πn0-complete for some n ≥ 2. • However, for n ≥ 2, ΩU[X] is not n-random when X is Σn0 or Πn0. Nevertheless, there exists Δn+10 sets such that ΩU[X] is n-random. • There are Δ20 sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is Δn+10 and Σn0-hard such that ΩU[X] is not random. We also look at the range of ΩU as an operator. We prove that the set {ΩU[X]: X ⊆ 2≤ω} is a finite union of closed intervals. It follows that for any optimal machine U and any sufficiently small real r, there is a set X ⊆ 2≤ω recursive in ∅′ ⊕ r, such that ΩU[X] = r. The same questions are also considered in the context of infinite computations, and lead to similar results.

Abstract Using possibly infinite computations on universal monotone Turing machines, we prove Martin-Löf randomness in ∅′ of the probability that the output be in some set under complexity assumptions about .

Abstract We introduce a notion ofsyntactical truth predicate(s.t.p.) for the second order arithmeticPA2. An s.t.p. is a setTof closed formulas such that: (i)T(t=u) if and only if the closed first order termstanduare convertible, i.e., have the same value in the standard interpretation (ii)T(A→B) if and only if (T(A) ⇒T(B)) (iii)T(∀xA) if and only if (T(A[x←t]) for any closed first order termt) (iv)T(∀X A) if and only if (T(A[X← ∆]) for any closed set definition ∆ = {x∣D(x)}). S.t.p.'s can be seen as a counterpart to Tarski's notion of (model-theoretical)validityand have main model properties. In particular, their existence is equivalent to the existence of anω-model ofPA2, this fact being provable inPA2with arithmetical comprehension only.

This paper is a contribution to the following natural problem in complexity theory: (*) Is there a complexity theory for isomorphism types of recursive countable relational structures? I.e. given a recursive relational structure ℛ over the set N of nonnegative integers, is there a nontrivial lower bound for the time-space complexity of recursive structures isomorphic (resp. recursively isomorphic) to ℛ? For unary recursive relations R, the answer is trivially negative: either R is finite or coinfinite or 〈N, R〉 is recursively isomorphic to 〈N, {x ϵ N: x is even}〉. The general problem for relations with arity 2 (or greater) is open. Related to this problem, a classical result (going back to S. C. Kleene [4], 1955) states that every recursive ordinal is in fact primitive recursive. In [3] Patrick Dehornoy, using methods relevant to computer science, improves this result, showing that every recursive ordinal can be represented by a recursive total ordering over N which has linear deterministic time complexity relative to the binary representation of integers. As he notices, his proof applies to every recursive total order type α such that the isomorphism type of α is not changed if points are replaced by arbitrary finite nonempty subsets of consecutive points. In this paper we extend Dehornoy's result to all recursive total orderings over N and get minimal complexity for both time and space simultaneously.