Catálogo de publicaciones - libros

With reference to Mandelkern’s characterisation of colocated subsets of the line in constructive analysis, we introduce the notion of “strongly colocated set” and find conditions under which such a set is Lebesgue integrable.

We introduce Genetic Systems, a formalism inspired by genetic regulatory networks and suitable for modeling the interactions between the genes and the proteins, acting as regulatory products.

The generation of new objects, representing proteins, is driven by genetic gates: a new object is produced when all the activator objects are available in the system, and no inhibitor object is available. Activators are not consumed by the application of such an evolution rule. Objects disappear because of degradation: each object is equipped with a lifetime, and the object decays when such a lifetime expires.

We investigate the computational expressiveness of Genetic Systems: we show that they are Turing equivalent by providing an encoding of Random Access Machines in Genetic Systems.

Computability theoretic learning theory (machine inductive inference) typically involves learning programs for languages or functions from a stream of complete data about them and, importantly, allows mind changes as to conjectured programs. This theory takes into account algorithmicity but typically does take into account of computational resources. This paper provides some example results and problems for three ways this theory can be constrained by computational feasibility. Considered are: the learner has memory limitations, the learned programs are desired to be optimal, and there are feasibility constraints on obtaining each output program on the number of mind changes.

The interest is in characterizing insightfully the power of program self-reference in effective programming systems (epses), the computability-theoretic analogs of programming languages. In an eps in which the form of Kleene’s Recursion Theorem () holds, it is possible to construct, algorithmically, from an arbitrary algorithmic task, a self-referential program that, in a sense, creates a self-copy and then performs that task on the self-copy. In an eps in which the -constructive form of Kleene’s Recursion Theorem () holds, such self-referential programs exist, but cannot, in general, be found algorithmically.

In an earlier effort, Royer proved that there is collection of recursive denotational control structures whose implementability the epses in which holds. One main result herein, proven by a finite injury priority argument, is that the epses in which holds are, similarly, characterized by the implementability of some collection of recursive denotational control structures.

On the positive side, however, a characterization of such epses of a rather different sort shown herein. Though, perhaps not the insightful characterization sought after, this surprising result reveals that a hidden and inherent constructivity is always present in .

– Greek proverb

We investigate the notion of -triviality for closed sets and continuous functions. Every -trivial closed set contains a -trivial real. There exists a -trivial class with no computable elements. For any -trivial degree , there is a -trivial continuous function of degree .

For a pseudojump operator and a class , we consider properties of the set {:  ∈ }. We show that there always exists  ∈  with and that if is Medvedev complete, then there exists  ∈  with . We examine the consequences when is Turing incomparable with for  ≠  in and when for all , ∈ . Finally, we give a characterization of the jump in terms of classes.

The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram. In this paper we study conditions for a sofic subshift to be the trace of a cellular automaton.

We study existence problems of maximal antichains in the Turing degrees. In particular, we give a characterization of the existence of thin maximal antichains in the Turing degrees in terms of (relatively) constructible reals. A corollary of our main result gives a negative solution to a question of Jockusch under the assumption that every real is constructible.

Nonlinear dynamical and control systems are an important source of applications for theories of computation over the the real numbers, since these systems are usually to complicated to study analytically, but may be extremely sensitive to numerical error. Further, computer-assisted proofs and verification problems require a rigorous treatment of numerical errors. In this paper we will describe how to provide a semantics for effective computations on sets and maps and show how these operations have been implemented in the tool for the analysis, design and verification of nonlinear and hybrid systems.

We present model–theoretic techniques to obtain conservation results for first order bounded arithmetic theories, based on a hierarchical version of the well known notion of an existentially closed model.