Search

Abstract: A widely accepted method to specify (possibly infinite) behaviour is to define it as the solution, in some process algebra, of a recursive specification, i.e., a system of recursive equations over the fundamental operations of the process algebra. The method only works if the recursive specification has a unique solution in the process algebra; it is well-known that guardedness is a sufficient requirement on a recursive specification to guarantee a unique solution in any of the standard process algebras. In this paper we investigate to what extent guardedness is also a necessary requirement to ensure unique solutions. We prove a theorem to the effect that all unguarded recursive specifications over have infinitely many solutions in the standard models for . In contrast, we observe that there exist recursive specifications over , necessarily involving parallel composition, that have a unique solution, or finitely many solutions in the standard models for . [Copyright &y& Elsevier]

Abstract: Many attempts to transcend the fundamental limitations to computability implied by the Halting Problem for Turing Machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. Thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. Here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability. [Copyright &y& Elsevier]

Abstract: Higher dimensional automata (HDA) represent a promising tool for modelling (“true”) concurrency in a both combinatorial and topological framework. Within these models, fast algorithms investigating deadlocks and unreachable regions have been devised previously on a background of easily understandable “directed” geometric ideas. In this article, we modify notions and methods from homotopy theory to define and investigate “essentially different” schedules in a HDA and to detect whether two given runs are essentially different using an algorithm again based on “directed geometry”. [Copyright &y& Elsevier]

Abstract: This paper proves the decidability of several problems in the theory of HD , and PD systems, some of which that have been proved before but are now proved in a different way. First, the paper tackles the decidability of the nilpotency of HD systems and the infinitude of PD languages. Then, we prove the decidability of the problem of momentary stagnation of the growth function of PD systems. Finally, we suggest a way to solve the decidability of the momentary stagnation of the growth function of systems, proving the decidability of the infinitude of HD as a trivial consequence. [Copyright &y& Elsevier]

Stream X-machines are a formalisation of extended finite state machines that have been used to specify systems. One of the great benefits of using stream X-machines, for the purpose of specification, is the associated test generation technique which produces a test that is guaranteed to determine correctness under certain design for test conditions. This test generation algorithm has recently been extended to the case where the specification is non-deterministic. However, the algorithms for testing from a non-deterministic stream X-machine currently have limitations: either they test for equivalence, rather than conformance or they restrict the source of non-determinism allowed in the specification. This paper introduces a new test generation algorithm that overcomes both of these limitations, for situations where the implementation is known to be deterministic. [Copyright &y& Elsevier]

We now know both that hypercomputation (or super-recursive computation) is mathematically well-understood, and that it provides a theory that according to some accounts for some real-life computation (e.g., operating systems that, unlike Turing machines, never simply output an answer and halt) better than the standard theory of computation at and below the “Turing Limit.” But one of the things we do not know is whether the human mind hypercomputes, or merely computes—this despite informal arguments from Gödel, Lucas, Penrose and others for the view that, in light of incompleteness theorems, the human mind has powers exceeding those of TMs and their equivalents. All these arguments fail; their fatal flaws have been repeatedly exposed in the literature. However, we give herein a novel, formal modal argument showing that since it''s mathematically possible that human minds are hypercomputers, such minds are in fact hypercomputers. We take considerable pains to anticipate and rebut objections to this argument. [Copyright &y& Elsevier]

We introduce Concurrent Timed Automata (CTAs) where automata running in parallel are synchronized. We consider the subclasses of CTAs obtained by admitting, or not, diagonal clock constraints and constant updates, and by letting, or not, sequential automata to update the same clocks. We prove that such subclasses recognize the same languages but differ w.r.t. the succinctness of the models. Moreover, we distinguish between subclasses that are polynomially closed w.r.t. finite union and finite intersection, and subclasses that do not have such properties. [Copyright &y& Elsevier]