Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007. Proceedings
We consider the family of all the Cellular Automata (CA) sharing the same local rule but have different memory. This family contains also all the CA with memory m ≤ 0 (one-sided CA) which can act both on A ℤ and on A ℕ. We study several set theoretical and topological properties for these classes. In particular we investigate if the properties of a given CA are preserved when we...
In this paper I describe the general principles of learning as data compression. I introduce two-part code optimization and analyze the theoretical background in terms of Kolmogorov complexity. The good news is that the optimal compression theoretically represents the optimal interpretation of the data, the bad news is that such an optimal compression cannot be computed and that an increase in compression...
There has been a great deal of progress in the fifteen years that have elapsed since Wigderson published his survey on the complexity of the graph connectivity problem [Wig92]. Most significantly, Reingold solved the longstanding question of the complexity of the s-t connectivity problem in undirected graphs, showing that this is complete for logspace (L) [Rei05]. This survey talk will focus...
Realizability theory can produce interfaces for the data structure corresponding to a mathematical theory. Our tool, called RZ, serves as a bridge between constructive mathematics and programming by translating specifications in constructive logic into annotated interface code in Objective Caml. The system supports a rich input language allowing descriptions of complex mathematical structures. RZ...
The paper investigates different relationships between membrane systems and Petri nets by focusing on modelling variants of the producer/consumer paradigm. Two models of producer/consumer systems based on membrane systems are described, and it is shown how to translate these models into equivalent Petri nets with a corresponding semantics. It is then observed a direct correspondence between the Petri...
In this paper, we prove the existence of a minimal pair of c.e. degrees a and b such that both of them are cuppable, and no incomplete c.e. degree can cup both of them to 0′. As a consequence, [a] and [b] form a minimal pair in M/NCup, the quotient structure of the cappable degrees modulo noncuppable degrees. We also prove that the dual of Lempp’s conjecture is true.
This paper examines the constructive Hausdorff and packing dimensions of weak truth-table degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dimH(S) and constructive packing dimension dimP(S) is weak truth-table equivalent to a sequence R with ${\rm dim_H}({\it R}) \geq {\rm dim_H}(S) / {\rm dim_P}(S) - \epsilon$ , for arbitrary ε> 0. Furthermore,...
We study computer virology from an abstract point of view. Viruses and worms are self-replicating programs, whose constructions are essentially based on Kleene’s second recursion theorem. We show that we can classify viruses as solutions of fixed point equations which are obtained from different versions of Kleene’s second recursion theorem. This lead us to consider four classes of viruses which various...
We study the Borel complexity of topological operations on closed subsets of computable metric spaces. The investigated operations include set theoretic operations as union and intersection, but also typical topological operations such as the closure of the complement, the closure of the interior, the boundary and the derivative of a set. These operations are studied with respect to different computability...
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...
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 not take into account feasibility of computational resources. This paper provides some example...
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 constructive form of Kleene’s Recursion Theorem (KRT) holds, it is possible to construct, algorithmically, from an arbitrary algorithmic task, a self-referential program that, in a sense, creates...
We investigate the notion of K-triviality for closed sets and continuous functions. Every K-trivial closed set contains a K-trivial real. There exists a K-trivial class with no computable elements. For any K-trivial degree d, there is a K-trivial continuous function of degree d.
For a pseudojump operator V X and a class P, we consider properties of the set {V X : X ∈ P}. We show that there always exists X ∈ P with and that if P is Medvedev complete, then there exists X ∈ P with . We examine the consequences when V ...
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...