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.
We define a simple variation of the standard Kripke semantics motivated by the connection between constructive logic and the Medvedev lattice. We show that while the new semantics is still complete, it gives a simple and direct correspondence between Kripke models and algebraic structures such as factors of the Medvedev lattice.
We survey some recent results related to the complexity of isomorphism testing in different algebraic structures. We concentrate on isomorphism problems for finite groups and rings. The complexity of these problems depends not only on the particular underlying algebraic structure, but also on the way the input instances are encoded. As in the case of better studied isomorphism questions, like graph...
Conceptual difficulties involved in attempts to build analog super-Turing sources are examined in the light of epistemic problems of physical measurement. Basic concepts of computability theory are appealed to in order to set up a procedural comparison between analog and digital computations which is not affected by similar conceptual difficulties: Is the interpretation of program code within the...
We define a general concept of a network of analogue modules connected by channels, processing data from a metric space A, and operating with respect to a global continuous clock T.
Computable Analysis studies those functions on the real numbers and related sets which can be computed by machines such as digital computers. It connects two traditionally disjoint fields, namely Analysis/Numerical Analysis on the one hand and Computability/Computational Complexity on the other hand, combining concepts of approximation and of computation. In particular, Computable Analysis supplies...
We produce a classification of the pointclasses of sets of reals produced by infinite time turing machines with 1-tape. The reason for choosing this formalism is that it apparently yields a smoother classification of classes defined by algorithms that halt at limit ordinals. We consider some relations of such classes with other similar notions, such as arithmetical quasi-inductive...
We investigate the computational complexity of an optical model of computation called the continuous space machine (CSM). We characterise worst case resource growth over time for each of the CSM’s ten operations with respect to seven resource measures. Many operations exhibit unreasonably large growth rates thus motivating restrictions on the CSM, in particular we give a restriction called the C ...
This note is concerned with computability of the solution operator associated with the wave maker problem for the classical Korteweg-de Vries equation. The Korteweg-de Vries equation is one of several non-linear partial differential equations which have been most intensively studied in the past fifty years due to its physical and mathematical importance.
The sometimes so-called Main Theorem of Recursive Analysis implies that any computable real function is necessarily continuous. We consider three relaxations of this common notion of real computability for the purpose of treating also discontinuous functions f: ℝ→ℝ: non-deterministic computation; relativized computation, specifically given access to oracles like ∅′...
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.