Search

In this paper, we show that accepting networks of splicing processors (ANSPs) of size 3 are computationally complete. Moreover, we prove that they can decide all languages in NP in polynomial time. The previous lower bound for both issues was 7. Since, by its definition, ANSPs need at least 2 nodes for any non-trivial computation, we leave only one open case. We also prove the following normal form: For any ANSP there exists an equivalent ANSP without output filters. [ABSTRACT FROM AUTHOR]

The Ordinal Register Machine (ORM) is one of several different machine models for infinitary computability. We classify, by complexity, the sets that can be decided quickly by ORMs. In particular, we show that the arithmetical sets are exactly those sets that can be decided by ORMs in times uniformly less than ${\ensuremath{\omega^\omega}}$. Further, we show that the hyperarithmetical sets are exactly those sets that can be decided by an ORM in time uniformly less than $\omega_1^{CK}$. [ABSTRACT FROM AUTHOR]

A classic result known as the speed-up theorem in machine-independent complexity theory shows that there exist some computable functions that do not have best programs for them [2][3]. In this paper we lift this result into type-2 computation under the notion of our type-2 complexity theory depicted in [15][13][14]. While the speed-up phenomenon is essentially inherited from type-1 computation, we cannot directly apply the original proof to our type-2 speed-up theorem because the oracle queries can interfere the speed of the programs and hence the cancellation strategy used in the original proof is no longer correct at type-2. We also argue that a type-2 analog of the operator speed-up theorem [16] does not hold, which suggests that this curious phenomenon disappears in higher-typed computation beyond type-2. [ABSTRACT FROM AUTHOR]

Effective domain theory is applied to fuzzy logic to give suitable notions of semi-decidable and decidable L-subset. The connection with the notions of fuzzy Turing machines and fuzzy grammar given in literature is also investigated. This shows the inadequateness of these definitions and the difficulties in formulating an analogue of Church Thesis for fuzzy logic. [ABSTRACT FROM AUTHOR]

A guiding question in the study of weak 2-randomness is whether weak 2-randomness is closer to 1-randomness, or closer to 2-randomness. Recent research indicates that the first alternative holds. We add further evidence in this direction by showing that, in contrast to the case for 2-randomness, a weakly 2-random set can fail to be generalized low. [ABSTRACT FROM AUTHOR]

Concerning the set of rooted binary trees, one shows that Higman's Lemma and Dershowitz's recursive path ordering can be used for the decision of its maximal order type according to the homeomorphic embedding relation as well as of the order type according to its canonical linearization, well-known in proof theory as the Feferman-Schütte notation system without terms for addition. This will be done by showing that the ordinal ωn + 1 can be found as the (maximal) order type of a set in a cumulative hierarchy of sets of rooted binary trees. [ABSTRACT FROM AUTHOR]

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses the more challenging problem of the strict self-assembly of discrete Sierpinski triangles, i.e., the task of tiling a discrete Sierpinski triangle and nothing else. We first prove that the standard discrete Sierpinski triangle cannot strictly self-assemble in the Tile Assembly Model. We then define the fibered Sierpinski triangle, a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of Winfree counters, coupled with measured delay and corner-turning operations. We verify our strict self-assembly using the local determinism method of Soloveichik and Winfree (2005). [ABSTRACT FROM AUTHOR]

Realism about computation is the view that whether or not a particular physical system is performing a particular computation is at least sometimes a mindindependent feature of reality. The caveat 'at least sometimes' is necessary here because a realist about computation need not believe that all instances of computation should be realistically construed. The computational theory of mind presupposes realism about computation. If whether or not the human nervous system implements particular computations is not a natural fact about the world that is independent of whether we represent it as doing so, then the computational theory of mind fails to naturalise the mind. Realism about computation is also presupposed by attempts to use computational principles such as Landauer's Principle to dispel Maxwell's Demon. Realism about computation has been challenged by Hilary Putnam and John Searle among others. Various arguments have been put forward purporting to show that any physical system of sufficient complexity trivially implements all computations. Ladyman et al. (2007) offer a precisification and general proof Landauer's Principle. In order to do this they present an analysis of what it is for a physical process to implement a logical transformation. In this paper, their analysis is explained and its implications for realism about computation and the use of Landauer's Principle in foundational debates is assessed. [ABSTRACT FROM AUTHOR]

We prove that for any k ≥ 3 each element of the homomorphic quasiorder of finite k-labeled forests is definable, provided that the minimal non-smallest elements are allowed as parameters. As corollaries, we show that the structure is atomic and characterize the automorphism group of the structure. Similar results hold true for two other relevant structures: the homomorphic quasiorder of finite k-labeled trees, and of finite k-labeled trees with a fixed label of the root element. [ABSTRACT FROM AUTHOR]

We survey our current knowledge of circuit complexity of regular languages. We show that regular languages are of interest as languages providing understanding of different circuit classes. We also prove that regular languages that are in AC0 and ACC0 are all computable by almost linear size circuits, extending the result of Chandra et al.[5]. [ABSTRACT FROM AUTHOR]

In this paper we prove the Uniformity Principle for Σ-definability over the real numbers extended by open predicates. Using this principle we show that if we have a ΣK-formula, i.e. a formula with quantifier alternations where universal quantifiers are bounded by computable compact sets, then we can eliminate all universal quantifiers obtaining a Σ-formula equivalent to the initial one. We also illustrate how the Uniformity Principle can be employed for reasoning about computability over continuous data in an elegant way. [ABSTRACT FROM AUTHOR]

We show that the bounded arithmetic theory V0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). This result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input. This is a continuation of earlier work by the authors which showed that this collapse is not provable in ${\mbox{\rm{PV}}}$ under a cryptographic assumption. [ABSTRACT FROM AUTHOR]

We prove confluence of two cut-elimination procedures for the implicational fragment of a standard intuitionistic sequent calculus. One of the cut-elimination procedures uses global proof transformations while the other consists of local ones. Both of them include permutation of cuts to simulate β-reduction in an isomorphic image of the λ-calculus. We establish the confluence properties through a conservativity result on the cut-elimination procedures. [ABSTRACT FROM AUTHOR]

In the paper the problem of existence of an algebraic structure with the degree spectra is studied for arbitrary degree . [ABSTRACT FROM AUTHOR]

We study Post's Problem for the ordinal register machines defined in [6], showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors the results in [3] for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time. [ABSTRACT FROM AUTHOR]

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 structures on the hyperspace of closed subsets. These structures include positive or negative information on the represented closed subsets. Topologically, they correspond to the lower or upper Fell topology, respectively, and the induced computability concepts generalize the classical notions of r.e. or co-r.e. subsets, respectively. The operations are classified with respect to effective measurability in the Borel hierarchy and it turns out that most operations can be located in the first three levels of the hierarchy, or they are not even Borel measurable at all. In some cases the effective Borel measurability depends on further properties of the underlying metric spaces, such as effective local compactness and effective local connectedness. [ABSTRACT FROM AUTHOR]

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 polymorphic features. We propose to use virus distribution in order to deal with mutations. Topics covered. Computability theoretic aspects of programs, computer virology. [ABSTRACT FROM AUTHOR]

We extend the notion of (TTE-)computability to nonstandard universes by the traditional method of enlarging universes through ultrafilters. In this way a nonstandard notion of effectivity is obtained. [ABSTRACT FROM AUTHOR]

In the paper the exact pair theorem for the ω-enumeration degrees is proved. As a corollary an exact pair theorem involving the jump operation for the enumeration degrees is obtained. Mathematics subject classification: 03D30. [ABSTRACT FROM AUTHOR]

We attempt to understand a cohomological approach to lower bounds in Boolean circuits (of [Fri05]) by studying a very restricted case; in this case Boolean complexity is described via the kernel (or nullspace) of a fairly simple linear transformation and its transpose. We look at this linear transformation approach for Boolean functions where we only allow AND gates, which is essentially the SET COVER problem. These linear transformations can recover the linear programming bound. More importantly, we learn that the optimal linear transformation to use can depend on the Boolean function whose complexity we wish to bound; we also learn that infinite complexity (that can occur in AND complexity over arbitrary sets and "bases") appears as a limits of the linear transformation bounds. [ABSTRACT FROM AUTHOR]

The index set of computable structures with decidable theory for some fixed infinite language σ* is m-complete $\Sigma^{0,\emptyset^{(\omega)}}_2$. [ABSTRACT FROM AUTHOR]

We introduce and discuss some basic concepts of parameterized complexity theory via model-checking problems. [ABSTRACT FROM AUTHOR]

In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring or Hamilton Path or Minimum Dominating Set for graphs of bounded max leaf number? We do two things: (1) We describe much improved FPT algorithms for a large number of graph problems, for input of bounded max leaf number, based on the polynomial-time extremal structure theory associated to the parameter max leaf number. (2) The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach. [ABSTRACT FROM AUTHOR]

When defined with general elimination/application rules, natural deduction and λ-calculus become closer to sequent calculus. In order to get real isomorphism, normalisation has to be defined in a "multiary" variant, in which reduction rules are necessarily non-local (reason: nomalisation, like cut-elimination, acts at the head of applicative terms, but natural deduction focuses at the tail of such terms). Non-local rules are bad, for instance, for the mechanization of the system. A solution is to extend natural deduction even further to a unified calculus based on the unification of cut and general elimination. In the unified calculus, a sequent term behaves like in the sequent calculus, whereas the reduction steps of a natural deduction term are interleaved with explicit steps for bringing heads to focus. A variant of the calculus has the symmetric role of improving sequent calculus in dealing with tail-active permutative conversions. [ABSTRACT FROM AUTHOR]

We develop a notion of derivative of a real-valued function on a Banach space, called the L-derivative, which is constructed by introducing a generalization of Lipschitz constant of a map. The values of the L-derivative of a function are non-empty weak* compact and convex subsets of the dual of the Banach space. This is also the case for the Clarke generalised gradient. The L-derivative, however, is shown to be upper semi continuous with respect to the weak* topology, a result which is not known to hold for the Clarke gradient on infinite dimensional Banach spaces. We also formulate the notion of primitive maps dual to the L-derivative, an extension of Fundamental Theorem of Calculus for the L-derivative and a domain for computation of real-valued functions on a Banach space with a corresponding computability theory. [ABSTRACT FROM AUTHOR]

Abstract geometrical computation naturally arises as a continuous counterpart of cellular automata. It relies on signals (dimensionless points) traveling at constant speed in a continuous space in continuous time. When signals collide, they are replaced by new signals according to some collision rules. This simple dynamics relies on real numbers with exact precision and is already known to be able to carry out any (discrete) Turing-computation. The Blum, Shub and Small (BSS) model is famous for computing over ℝ (considered here as a ℝ unlimited register machine) by performing algebraic computations. We prove that signal machines (set of signals and corresponding rules) and the infinite-dimension linear (multiplications are only by constants) BSS machines can simulate one another. [ABSTRACT FROM AUTHOR]

This paper introduces two complexity-theoretic formulations of Bennett's logical depth: finite-state depth and polynomial-time depth. It is shown that for both formulations, trivial and random infinite sequences are shallow, and a slow growth law holds, implying that deep sequences cannot be created easily from shallow sequences. Furthermore, the $\textsf{E}$ analogue of the halting language is shown to be polynomial-time deep, by proving a more general result: every language to which a nonnegligible subset of $\textsf{E}$ can be reduced in uniform exponential time is polynomial-time deep. [ABSTRACT FROM AUTHOR]

A formal specification of an arithmetic unit for computable normalized rational numbers is proposed. This specification, developed under the scope of the paradigm known as algebraic models of processors, exploits the connection between the signed digit representation for rational numbers in Type-2 Theory of Effectivity and online arithmetic in Computer Arithmetic. The proposal aims for specification formalization and calculation reliability together with implementation feasibility. [ABSTRACT FROM AUTHOR]

The authors' ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are ATR-definable (ATR types are confined to levels 0, 1, and 2). A limitation of the original version of ATR is that the only directly expressible recursions are tail-recursions. Here we extend ATR so that a broad range of affine recursions are directly expressible. In particular, the revised ATR can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper's main work is in extending and simplifying the original time-complexity semantics for ATR to develop a set of tools for extracting and solving the higher-type recurrences arising from feasible affine recursions. [ABSTRACT FROM AUTHOR]

To each computable enumerable (c.e.) set A with a particular enumeration {As}s ∈ ω, there is associated a settling function mA(x), where mA(x) is the last stage when a number less than or equal to x was enumerated into A. In [7], R.W. Robinson classified the complexity of c.e. sets into two groups of complexity based on whether or not the settling function was dominant. An extension of this idea to a more refined ordering of c.e. sets was first introduced by Nabutovsky and Weinberger in [6] and Soare [9], for application to differential geometry. There they defined one c.e. set A to settling time dominate another c.e. set B (B > stA) if for every computable function f , for all but finitely many x, mB(x) > f(mA(x)). In [4] Csima and Soare introduced a stronger ordering, where B > sstA if for all computable f and g, for almost all x, mB(x) > f(mA(g(x))). We give a survey of the known results about these orderings, make some observations, and outline the open questions. [ABSTRACT FROM AUTHOR]

We show that, using our more or less established framework of inductive definition of real-valued functions (work started by Cristopher Moore in [9]) together with ideas and concepts of standard computability we can prove theorems of Analysis. Then we will consider our ideas as a bridging tool between the standard Theory of Computability (and Complexity) on one side and Mathematical Analysis on the other, making real recursive functions a possible branch of Descriptive Set Theory. What follows is an Extended Abstract directed to a large audience of CiE 2007, Special Session on Logic and New Paradigms of Computability. (Proofs of statements can be found in a detailed long paper at the address http://fgc.math.ist.utl.pt/papers/hierarchy.pdf.) [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 Ariadne for the analysis, design and verification of nonlinear and hybrid systems. [ABSTRACT FROM AUTHOR]

We study existence problems of maximal antichains in the Turing degrees. In particular, we give a characterization of the existence of thin $\Pi^1_1$ 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

For a pseudojump operator VX and a $\Pi^0_1$ class P, we consider properties of the set {VX: X ∈ P}. We show that there always exists X ∈ P with $V^X \leq_T {\mathbf 0'}$ and that if P is Medvedev complete, then there exists X ∈ P with $ V^X \equiv_T {\mathbf 0'}$. We examine the consequences when VX is Turing incomparable with VY for X ≠ Y in P and when $W_e^X = W_e^Y$ for all X,Y ∈ P. Finally, we give a characterization of the jump in terms of $\Pi^0_1$ classes. [ABSTRACT FROM AUTHOR]

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 $\Pi^0_1$ class with no computable elements. For any K-trivial degree d, there is a K-trivial continuous function of degree d. [ABSTRACT FROM AUTHOR]

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 a self-copy and then performs that task on the self-copy. In an eps in which the not-necessarily-constructive form of Kleene's Recursion Theorem (krt) holds, such self-referential programs exist, but cannot, in general, be found algorithmically. In an earlier effort, Royer proved that there is no collection of recursive denotational control structures whose implementability characterizes the epses in which KRT holds. One main result herein, proven by a finite injury priority argument, is that the epses in which krt holds are, similarly, not 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 is shown herein. Though, perhaps not the insightful characterization sought after, this surprising result reveals that a hidden and inherent constructivity is always present in krt. Know thyself. - Greek proverb [ABSTRACT FROM AUTHOR]

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 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 and on the number of mind changes. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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, if dimP(S) > 0, then dimP(R) ≥ 1 − ε. The reduction thus serves as a randomness extractor that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of wtt degrees (and, by extension, Turing degrees). A lower bound of dimH(S) / dimP(S) is shown to hold for the wtt degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of wtt degrees. It is also shown that, for any regular sequence S (that is, dimH(S) = dimP(S)) such that dimH(S) > 0, the wtt degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor. [ABSTRACT FROM AUTHOR]

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 nets representation of the proposed models and standard solutions based on Petri nets already present in the literature. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 does not extract code from proofs, but allows any implementation method, from handwritten code to code extracted from proofs by other tools. [ABSTRACT FROM AUTHOR]

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 consider the CA obtained by changing the memory of the original one (shifting operation). Furthermore we focus our attention to the one-sided CA acting on Aℤ starting from the one-sided CA acting on Aℕ and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity $\Rightarrow$ Density of the Periodic Orbits (DPO)] is equivalent to the conjecture [Topological Mixing $\Rightarrow$ DPO]. [ABSTRACT FROM AUTHOR]

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 not necessarily implies a better theory. I discuss the application of these insights to DFA induction. [ABSTRACT FROM AUTHOR]