The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This paper formalizes an open semantics for a calculus featuring thread classes, where the environment, consisting in particular of an overapproximation of the heap topology, is abstractly represented. We extend our prior work not only by adding thread classes, but also in that thread names may be communicated, which means that the semantics needs to account explicitly for the possible acquaintance...
Gödel’s main contribution to set theory is his proof that GCH is consistent with ZFC (assuming that ZF is consistent). For this proof he has introduced the important ideas of constructibility of sets, and of absoluteness of formulas. In this paper we show how these two ideas of Gödel naturally lead to a simple unified framework for dealing with computability of functions and relations, domain independence...
Datatype-generic programs are programs that are parameterised by a datatype. Designing datatype-generic programs brings new challenges and new opportunities. We review the allegorical foundations of a methodology of designing datatype-generic programs. The effectiveness of the methodology is demonstrated by an extraordinarily concise proof of the well-foundedness of a datatype-generic occurs-in relation.
We introduce a notion of complexity for sets of finite binary sequences such that the corresponding fan theorem is constructively equivalent to the uniform continuity theorem. This settles an open question.
The elementary algebraic specifications form a small subset of the range of techniques available for algebraic specifications and are based on equational specifications with hidden functions and sorts and initial algebra semantics. General methods exist to show that all semicomputable and computable algebras can be characterised up to isomorphism by such specifications. Here we consider these specification...
We investigate notions of randomness in the space of nonempty closed subsets of {0,1}ℕ. A probability measure is given and a version of the Martin-Löf Test for randomness is defined. Π02 random closed sets exist but there are no random Π01 closed sets. It is shown that a random closed set is perfect, has measure 0, and has no computable elements...
We see a notion of normal derivation for the calculus of structures, which is based on a factorisation of derivations and which is more general than the traditional notion of cut-free proof in this formalism.
Logspace complexity of functions and structures is based on the notion of a Turing machine with input and output as in Papadmitriou [16]. For any k > 1, we construct a logspace isomorphism between {0,1}* and {0,1,..., k}*. We improve results of Cenzer and Remmel [5] by characterizing the sets which are logspace isomorphic to {1}*. We generalize Proposition 8.2 of [16] by giving upper bounds on...
Computability in the limit represents the non-plus-ultra of constructive describability. It is well known that the limit computable functions on naturals are exactly those computable with the oracle for the halting problem. However, prefix (Kolmogorov) complexities defined with respect to these two models may differ. We introduce and compare several natural variations of prefix complexity definitions...
It is well known that to be able to represent continuous functions between domain representable spaces it is critical that the domain representations of the spaces we consider are dense. In this article we show how to develop a representation theory over a category of domains with morphisms partial continuous functions. The raison d’être for introducing partial continuous functions is that by passing...
We define a new cost model for the call-by-value lambda-calculus satisfying the invariance thesis. That is, under the proposed cost model, Turing machines and the call-by-value lambda-calculus can simulate each other within a polynomial time overhead. The model only relies on combinatorial properties of usual beta-reduction, without any reference to a specific machine or evaluator. In particular,...
We present a reduction from the Pigeon-Hole Principle to the classical Sperner Lemma. The reduction is used 1. to show that the Sperner Lemma does not have a short constant-depth Frege proof, and 2. to prove lower bounds on the Query Complexity of the Sperner Lemma in the Black-Box model of Computation.
Many years ago, I wrote [7]: It is truly remarkable (Gödel ...speaks of a kind of miracle) that it has proved possible to give a precise mathematical characterization of the class of processes that can be carried out by purely machanical means. It is in fact the possibility of such a characterization that underlies the ubiquitous applicability of digital computers. In addition it has made it...
The centenary of Kurt Gödel (1906–78) is an appropriate occasion on which to assess his profound, yet indirect, influence on the development of computer science. His contributions to and attitudes toward that field are discussed, and are compared with those of other pioneer figures such as Alonzo Church, Emil Post, Alan Turing, and John von Neumann, in order better to understand why Gödel’s role was...
A theoretical approach to a novel design method for special purpose processors for computable integral transforms and related operations is presented. The method is based on algebraic processor models and Type-2 Theory of Effectivity and aims for specification formalization and calculation reliability together with implementation feasibility. The convolution operation is presented as a case of study.
A computer is classically formalized as a universal Turing machine. However over the years a lot of research has focused on the computational properties of dynamical systems other than Turing machines, such cellular automata, artificial neural networks, mirrors systems, etc. In this talk we review some of the definitions that have been proposed for Turing universality of various systems, and...
Kučera and Gács independently showed that every infinite sequence is Turing reducible to a Martin-Löf random sequence. We extend this result to show that every infinite sequence S is Turing reducible to a Martin-Löf random sequence R such that the asymptotic number of bits of R needed to compute n bits of S, divided by n, is precisely the constructive dimension of S. We show that this is the optimal...
In Abstract geometrical computation for black hole computation (MCU ’04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability. In the present paper, we prove the Turing computing capability of reversible conservative abstract geometrical computation. Reversibility allows backtracking as well as saving energy; it corresponds...
LJQ is a focused sequent calculus for intuitionistic logic, with a simple restriction on the first premisss of the usual left introduction rule for implication. We discuss its history (going back to about 1950, or beyond), present the underlying theory and its applications both to terminating proof-search calculi and to call-by-value reduction in lambda calculus.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.