Serwis Infona wykorzystuje pliki cookies (ciasteczka). Są to wartości tekstowe, zapamiętywane przez przeglądarkę na urządzeniu użytkownika. Nasz serwis ma dostęp do tych wartości oraz wykorzystuje je do zapamiętania danych dotyczących użytkownika, takich jak np. ustawienia (typu widok ekranu, wybór języka interfejsu), zapamiętanie zalogowania. Korzystanie z serwisu Infona oznacza zgodę na zapis informacji i ich wykorzystanie dla celów korzytania z serwisu. Więcej informacji można znaleźć w Polityce prywatności oraz Regulaminie serwisu. Zamknięcie tego okienka potwierdza zapoznanie się z informacją o plikach cookies, akceptację polityki prywatności i regulaminu oraz sposobu wykorzystywania plików cookies w serwisie. Możesz zmienić ustawienia obsługi cookies w swojej przeglądarce.
As it happens, ”Computability in Europe” was invented, just over two years ago, and in a short time has grown beyond all expectations. But even though the surprise of finding together so many researchers into different aspects of computability has not worn off, CiE does represent a strand of scientific endevour going back to the earliest times. Even before Euclid of Alexandria devised his algorithm...
The strong weak truth table reducibility was suggested by Downey, Hirschfeldt, and LaForte as a measure of relative randomness, alternative to the Solovay reducibility. It also occurs naturally in proofs in classical computability theory as well as in the recent work of Soare, Nabutovsky and Weinberger on applications of computability to differential geometry. Yu and Ding showed that the relevant...
In presence of continuous choice the fan theorem is equivalent to each pointwise continuous function f from the Cantor space to the natural numbers being uniformly continuous. We investigate whether we can prove this equivalence without the use of continuous choice. By strengthening the assumption of pointwise continuity of f to the assertion that f has a modulus of pointwise continuity which itself...
We prove a general strong normalization theorem for higher type rewrite systems based on Tait’s strong computability predicates and a strictly continuous domain-theoretic semantics. The theorem applies to extensions of Gödel’s system T but also to various forms of bar recursion for which strong normalization was hitherto unknown.
In a previous paper, we developed an algebraic theory of threads and multi-threads based on strategic interleaving. This theory includes a number of plausible interleaving strategies on thread vectors. The strategic interleaving of a thread vector constitutes a multi-thread. Several multi-threads may exist concurrently on a single host in a network, several host behaviors may exist concurrently in...
In the last decade and especially after Adleman’s experiment [1] a number of computational paradigms, inspired or gleaned from biochemical phenomena, are becoming of growing interest building a wealth of models, called generically Molecular Computing. New advances in, on the one hand, molecular and theoretical biology, and on the other hand, mathematical and computational sciences promise to make...
We argue that there is currently no satisfactory general framework for comparing the extensional computational power of arbitrary computational models operating over arbitrary domains. We propose a conceptual framework for comparison, by linking computational models to hypothetical physical devices. Accordingly, we deduce a mathematical notion of relative computational power, allowing the comparison...
Many computational problems that turn up in industry, operations research, network design, artificial intelligence, simulation of physical systems, logic, number theory, combinatorics, algebra, and computational biology lack a fast or feasible algorithmic solution. The best known algorithms for these problems are horrendously slow. One of the central open problems in computer science is the question...
This paper presents the Cognitive Symbol Grounding framework for modeling language in neural networks and adaptive agent simulations. This approach is characterized by the hypothesis that symbols are directly grounded into the agents’ own categorical representations, whilst at the same time having syntactic relationships with other symbols. The mechanism of grounding transfer is also introduced. This...
We study the complexity of computable and Σ inductive definitions of sets of natural numbers. For we example, we show how to assign natural indices to monotone Σ -definitions and we use these to calculate the complexity of the set of all indices of monotone Σ -definitions which are computable. We also examine the complexity of new type of...
Recent work in constructive mathematics show that Hilbert’s program works for a large part of abstract algebra. Furthermore the arguments we get are not only elementary but also mathematically simpler. We present an example where the simplification was significant enough to suggest an improved version of a classical theorem. For this we use a general method to transform some logically complex first-order...
Following Lutz’s approach to effective (constructive) dimension, we define a notion of dimension for individual sequences based on Schnorr’s concept(s) of randomness. In contrast to computable randomness and Schnorr randomness, the dimension concepts defined via computable martingales and Schnorr tests coincide. Furthermore, we give a machine characterization of Schnorr dimension, based on prefix...
In the Cellular Automata (CA) literature, discrete lines inside (discrete) space-time diagrams are often idealized as Euclidean lines in order to analyze a dynamics or to design CA for special purposes. In this article, we present a parallel analog model of computation corresponding to this idealization: dimensionless signals are moving on a continuous space in continuous time generating Euclidean...
We promote the concept of object directed computability in computational geometry in order to faithfully generalise the well-established theory of computability for real numbers and real functions. In object directed computability, a geometric object is computable if it is the effective limit of a sequence of finitary objects of the same type as the original object, thus allowing a quantitative measure...
Since Di Gianantonio introduced his semantics for exact real number computation, there has always been a struggle to maintain data abstraction and efficiency as much as possible. The interval domain model — or its variations — can be regarded as the standard setting to obtain maximum data abstraction. As for efficiency there has been much focus on sequentiality to the extent that these two terms have...
We determine completely the Borel hierarchy of the class of context free ω-languages, showing that, for each recursive non null ordinal α, there exist some Σ -complete and some Π -complete ω-languages accepted by Büchi 1-counter automata.
Seventeen years ago, John McCarthy wrote the note Epistemological challenges for connectionism as a response to Paul Smolensky’s paper On the proper treatment of connectionism. I will discuss the extent to which the four key challenges put forward by McCarthy have been solved, and what are the new challenges ahead. I argue that there are fewer epistemological challenges for connectionism, but progress...
Computational Learning Theory has two goals: one, proposing rigorous models of learning tasks that can be carried out by computers. Two, designing algorithms that provably learn whole classes of concepts in these models within some efficiency criterion.
Podaj zakres dat dla filtrowania wyświetlonych wyników. Możesz podać datę początkową, końcową lub obie daty. Daty możesz wpisać ręcznie lub wybrać za pomocą kalendarza.