An impossibility about failure detectors in the iterated immediate snapshot model

The Iterated Immediate Snapshot model (IIS) is an asynchronous computation model where processes communicate through a sequence of one-shot Immediate Snapshot (IS) objects. It is known that this model is equivalent to the usual asynchronous read/write shared memory model, for wait-free task solvability. Its interest lies in the fact that its runs are more structured and easier to analyze than the runs in the shared memory model. As the IIS model and the shared memory model are equivalent for wait-free task solvability, a natural question is the following: Are they still equivalent for wait-free task solvability, when they are enriched with the same failure detector? The paper shows that the answer to this question is “no”.     

Minimality considerations for ordinal computers modeling constructibility

We describe a simple model of ordinal computation which can compute truth in the constructible universe. We try to use well-structured programs and direct limits of states at limit times whenever possible. This may make it easier to define a model of ordinal computation within other systems of hypercomputation, especially systems inspired by physical models.     

Turing-, Human- and Physical Computability: An Unasked Question

In recent years it has been convincingly argued that the Church-Turing thesis concerns the bounds of human computability: The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm. Thus the Thesis needs to be distinguished from the so-called Physical Church-Turing thesis (or Thesis M), according to which all physically computable functions are Turing computable. The latter is often claimed to be false, or, if true, contingently so. On all accounts, though, thesis M is not easy to give counterexamples to, but it is never asked why—how come that a thesis that transfers a notion from the strictly human domain to the general physical domain just happens to be so difficult to falsify (or even to be true). In this paper I articulate this question and consider several tentative answers to it.

Two Dogmas of Computationalism

This paper challenges two orthodox theses: (a) that computational processes must be algorithmic; and (b) that all computed functions must be Turing-computable. Section 2 advances the claim that the works in computability theory, including Turing's analysis of the effective computable functions, do not substantiate the two theses. It is then shown (Section 3) that we can describe a system that computes a number-theoretic function which is not Turing-computable. The argument against the first thesis proceeds in two stages. It is first shown (Section 4) that whether a process is algorithmic depends on the way we describe the process. It is then argued (Section 5) that systems compute even if their processes are not described as algorithmic. The paper concludes with a suggestion for a semantic approach to computation. This revised version was published online in July 2006 with corrections to the Cover Date.     

Modelling test data for performance evaluation of large parallel database machines

Parallel servers offer improved processing power for relational database systems and provide system scalability. In order to support the users of these systems, new ways of assessing the performance of such machines are required. If these assessments are to show how the machines perform under commercial workloads they need to be based upon models which have a real commercial basis. This paper shows how a realistic model of a financial application has been developed and how a set of tools has been created which allow the implementation of the model on any commercial database system. The tools allow the generation of large quantities of test data in a manner which renders it amenable to subsequent independent analysis. The test data thus generated forms the basis for the performance tuning of parallel database machines.Recommended by: Patrick Valduriez     

Membrane systems with carriers

A membrane system is a model of computation which is inspired by some basic features of biological membranes. In this paper we consider another biologically inspired notion, viz., the notion of a carrier (or vehicle), as, e.g., used in gene cloning. We investigate the power of membrane systems where the rules for the evolving of objects are replaced by the rules that carry objects (by vehicles) through membranes. It turns out that these systems (even with a small number of membranes, a small number of carriers, and a small number of passengers taken by carriers) are computationally universal.     

PX systems = P systems + X machines

The paper is a survey of the main features of P systems, X machines and of a new computational device called PX system. The sequential and the parallel PX systems are presented. Results reflecting the computational power of these models and their effectiveness in solving NP-complete problems are briefly mentioned.     

A general framework for computing maximal contractions

This paper investigates the problem of computing all maximal contractions of a given formula set Γ with respect to a consistent set Δ of atomic formulas and negations of atomic formulas. We first give a constructive definition of minimal inconsistent subsets and propose an algorithmic framework for computing all minimal inconsistent subsets of any given formula set. Then we present an algorithm to compute all maximal contractions fromminimal inconsistent subsets. Based on the algorithmic framework and the algorithm, we propose a general framework for computing all maximal contractions. The computability of the minimal inconsistent subset and maximal contraction problems are discussed. Finally, we demonstrate the ability of this framework by applying it to the first-order language without variables and design an algorithmfor the computation of all maximal contractions.     

Macrotransducers and Applicative Systems for Partially Continuous Functions

The -calculus is an applicative system having the axioms of universality and approximation and the so-called s-m-n-axiom. It is proved that this calculus is interpreted in the theory of partially continuous operators on the space C[0, 1] consisting of continuous real functions defined on the segment [0, 1] . The problems of realizability, continuity, and computability are considered. The realizability of functionals and operators is understood to be the possibility of their representation by macrotransducers over labeled trees.