For regular sets in Euclidean space, previous work has identified twelve ‘basic’ computability notions to which many previous notions considered in literature were shown to be equivalent. With respect to those basic notions we now investigate on the computability of natural operations on regular sets: union, intersection, complement, convex hull, image, and pre-image under suitable classes of functions. It turns out that only few of these notions are suitable in the sense of rendering all those operations uniformly computable.

We develop some parts of the theory of compact operators from the point of view of computable analysis. While computable compact operators on Hilbert spaces are easy to understand, it turns out that these operators on Banach spaces are harder to handle. Classically, the theory of compact operators on Banach spaces is developed with the help of the non-constructive tool of sequential compactness. We demonstrate that a substantial amount of this theory can be developed (...) computably on Banach spaces with computable Schauder bases that are well-behaved. The conditions imposed on the bases are such that they generalize the Hilbert space case. In particular, we prove that the space of compact operators on Banach spaces with monotone, computably shrinking, and computable bases is a computable Banach space itself and operations such as composition with bounded linear operators from left are computable. Moreover, we provide a computable version of the Theorem of Schauder on adjoints in this framework and we discuss a non-uniform result on composition with bounded linear operators from right. (shrink)

We study operator equations within the Turing machine based framework for computability in analysis. Is there an algorithm that maps pairs to solutions of Tx = u ? Here we consider the case when T is a bounded linear mapping between Hilbert spaces. We are in particular interested in computing the generalized inverse T†u, which is the standard concept of solution in the theory of inverse problems. Typically, T† is discontinuous and hence no computable mapping. However, we will use (...) effective versions of theorems from the theory of regularization to show that the mapping ↦ T†u is computable. We then go on to study the computability of average-case solutions with respect to Gaussian measures which have been considered in information based complexity. Here, T† is considered as an element of an L2-space. We define suitable representations for such spaces and use the results from the first part of the paper to show that ↦ T† is computable. (shrink)

The connected and acyclic components contained in a network are identified by the computation of its complexity, where complexity of a network refers to the total number of spanning trees present within. The article in hand deals with the enumeration of the complexity of various networks’ operations such as sum, product, difference K 2, n ⊖ K 2, and the conjunction of S n with K 2. All our computations have been concluded by implementation of the methods of linear algebra (...) and matrix theory. Our derivations will also be highlighted with the assistance of 3D plots at the end of this article. (shrink)

The functional capabilities that consciousness seems to provide to biological systems can supply valuable principles in the design of more autonomous and robust technical systems. These functional concepts keep a notable similarity to those underlying the notion of operating system in software engineering, which allows us to specialize the computer metaphor for the mind into that of the operating system metaphor for consciousness. In this article, departing from these ideas and a model-based theoretical framework for cognition, we present an architectural (...) proposal for machine consciousness, called the Operative Mind. According to it, machine consciousness could be implemented as a set of services, in an operative system fashion, based on modeling of the own control architecture, that supervise the adequacy of the system architectural structure to the current objectives, triggering and managing adaptativity mechanisms. (shrink)

In this paper we investigate computable isomorphisms of Boolean algebras with operators (BAOs). We prove that there are examples of polymodal Boolean algebras with finitely many computable isomorphism types. We provide an example of a polymodal BAO such that it has exactly one computable isomorphism type but whose expansions by a constant have more than one computable isomorphism type. We also prove a general result showing that BAOs are complete with respect to the degree spectra (...) of structures, computable dimensions, expansions by constants, and the degree spectra of relations. (shrink)

For any class of operators which transform unary total functions in the set of natural numbers into functions of the same kind, we define what it means for a real function to be uniformly computable or conditionally computable with respect to this class. These two computability notions are natural generalizations of certain notions introduced in a previous paper co-authored by Andreas Weiermann and in another previous paper by the same authors, respectively. Under certain weak assumptions about the (...) class in question, we show that conditional computability is preserved by substitution, that all conditionally computable real functions are locally uniformly computable, and that the ones with compact domains are uniformly computable. The introduced notions have some similarity with the uniform computability and its non-uniform extension considered by Katrin Tent and Martin Ziegler, however, there are also essential differences between the conditional computability and the non-uniform computability in question. (shrink)

We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

This paper analyses the impact of representation and search operators on Computational Complexity. A model of computation is introduced based on a directed graph, and representation and search are defined to be the vertices and edges of this graph respectively. Changing either the representation or the search algorithm leads to different possible complexity classes. The final section explores the role of representation in reducing time complexity in Artificial Intelligence.

Combinatorial operations on sets are almost never well defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric-difference operator; there are pairs of degrees for which the symmetric-difference operation is well defined. Some examples can be extracted from the literature, e.g. from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric-difference operation is well defined.

Computer models and simulations have become, since the 1960s, an essential instrument for scientific inquiry and political decision making in several fields, from climate to life and social sciences. Philosophical reflection has mainly focused on the ontological status of the computational modeling, on its epistemological validity and on the research practices it entails. But in computational sciences, the work on models and simulations are only two steps of a longer and richer process where operations on data are as important as, (...) and even more time and energy-consuming than modeling itself. Drawing on two study cases—computational embryology and computational epidemiology—this article contributes to filling the gap by focusing on the operations of producing and re-using data in computational sciences. The different phases of the scientific and artisanal work of modelers include data collection, aggregation, homogenization, assemblage, analysis and visualization. The article deconstructs the ideas that data are self-evident informational aggregates and that data-driven approaches are exempted from theoretical work. More importantly, the paper stresses the fact that data are constructed and theory laden not only in their fabrication, but also in their reusing. (shrink)

Using Type-2 theory of effectivity, we define computability notions on the spaces of Lebesgue-integrable functions on the real line that are based on two natural approaches to integrability from measure theory. We show that Fourier transform and convolution on these spaces are computable operators with respect to these representations. By means of the orthonormal basis of Hermite functions in L2, we show the existence of a linear complexity bound for the Fourier transform.

Quantum probability (QP) theory can be seen as a type of vector symbolic architecture (VSA): mental states are vectors storing structured information and manipulated using algebraic operations. Furthermore, the operations needed by QP match those in other VSAs. This allows existing biologically realistic neural models to be adapted to provide a mechanistic explanation of the cognitive phenomena described in the target article by Pothos & Busemeyer (P&B).

In the book, I argue that the mind can be explained computationally because it is itself computational—whether it engages in mental arithmetic, parses natural language, or processes the auditory signals that allow us to experience music. All these capacities arise from complex information-processing operations of the mind. By analyzing the state of the art in cognitive science, I develop an account of computational explanation used to explain the capacities in question.

This work focuses on the application of machine learning techniques to assist the clinicians in the administration of analgesic drug during general anaesthesia. Specifically, the main objective is to propose the basis of an intelligent system capable of making decisions to guide the opioid dose changes based on a new nociception monitor, the analgesia nociception index. Clinical data were obtained from 15 patients undergoing cholecystectomy surgery. By means of an off-line study, machine learning techniques were applied to analyse the possible (...) relationship between the analgesic dose changes performed by the physician due to the hemodynamic activity of the patients and the evolution of the ANI. After training different classifiers and testing the results under cross validation, a preliminary relationship between the evolution of ANI and the dosage of remifentanil was found. These results evidence the potential of the ANI as a promising index to guide the infusion of analgesia. (shrink)

Computational explanations focus on information processing required in specific cognitive capacities, such as perception, reasoning or decision-making. These explanations specify the nature of the information processing task, what information needs to be represented, and why it should be operated on in a particular manner. In this article, the focus is on three questions concerning the nature of computational explanations: What type of explanations they are, in what sense computational explanations are explanatory and to what extent they involve a special, “independent” (...) or “autonomous” level of explanation. In this paper, we defend the view computational explanations are genuine explanations, which track non-causal/formal dependencies. Specifically, we argue that they do not provide mere sketches for explanation, in contrast to what for example Piccinini and Craver :283–311, 2011) suggest. This view of computational explanations implies some degree of “autonomy” for the computational level. However, as we will demonstrate that does not make this view “computationally chauvinistic” in a way that Piccinini or Kaplan :339–373, 2011) have charged it to be. (shrink)

Using Type‐2 theory of effectivity, we define computability notions on the spaces of Lebesgue‐integrable functions on the real line that are based on two natural approaches to integrability from measure theory. We show that Fourier transform and convolution on these spaces are computable operators with respect to these representations. By means of the orthonormal basis of Hermite functions in L2, we show the existence of a linear complexity bound for the Fourier transform. (© 2004 WILEY‐VCH Verlag GmbH & (...) Co. KGaA, Weinheim). (shrink)

Each of our theories of mental representation provides some insight into how the mind works. However, these insights often seem incompatible, as the debates between symbolic, dynamical, emergentist, sub-symbolic, and grounded approaches to cognition attest. Mental representations—whatever they are—must share many features with each of our theories of representation, and yet there are few hypotheses about how a synthesis could be possible. Here, I develop a theory of the underpinnings of symbolic cognition that shows how sub-symbolic dynamics may give rise (...) to higher-level cognitive representations of structures, systems of knowledge, and algorithmic processes. This theory implements a version of conceptual role semantics by positing an internal universal representation language in which learners may create mental models to capture dynamics they observe in the world. The theory formalizes one account of how truly novel conceptual content may arise, allowing us to explain how even elementary logical and computational operations may be learned from a more primitive basis. I provide an implementation that learns to represent a variety of structures, including logic, number, kinship trees, regular languages, context-free languages, domains of theories like magnetism, dominance hierarchies, list structures, quantification, and computational primitives like repetition, reversal, and recursion. This account is based on simple discrete dynamical processes that could be implemented in a variety of different physical or biological systems. In particular, I describe how the required dynamics can be directly implemented in a connectionist framework. The resulting theory provides an “assembly language” for cognition, where high-level theories of symbolic computation can be implemented in simple dynamics that themselves could be encoded in biologically plausible systems. (shrink)

By the Riesz representation theorem for the dual of C [0; 1], if F: C [0; 1] → ℝ is a continuous linear operator, then there is a function g: [0;1] → ℝ of bounded variation such that F = ∫ f dg . The function g can be normalized such that V = ‖F ‖. In this paper we prove a computable version of this theorem. We use the framework of TTE, the representation approach to computable analysis, (...) which allows to define natural computability for a variety of operators. We show that there are a computable operator S mapping g and an upper bound of its variation to F and a computable operator S ′ mapping F and its norm to some appropriate g. (shrink)

This paper seeks to understand machine cognition. The nature of machine cognition has been shrouded in incomprehensibility. We have often encountered familiar arguments in cognitive science that human cognition is still faintly understood. This paper will argue that machine cognition is far less understood than even human cognition despite the fact that a lot about computer architecture and computational operations is known. Even if there have been putative claims about the transparency of the notion of machine computations, these claims do (...) not hold out in unraveling machine cognition, let alone machine consciousness (if there is any such thing). The nature and form of machine cognition remains further confused also because of attempts to explain human cognition in terms of computation and to model/simulate (aspects of) human cognitive processing in machines. Given that these problems in characterizing machine cognition persist, a view of machine cognition that aims to avoid these problems is outlined. The argument that is advanced is that something becomes a computation in machines only when a human interprets it, which is a kind of semiotic causation. From this it follows that a computing machine is not engaged in a computation unless a human interprets what it is doing; instead, it is engaged in machine cognition, which is defined as a member or subset of the set of all possible mappings of inputs to outputs. The human interpretation, which is a semiotic process, gives meaning to what a machine does, and then what it does becomes a computation. (shrink)

The use of computers and the role of women in radio astronomy and X-ray crystallography research at the Cavendish Laboratory between 1949 and 1975 have been investigated. We recorded examples of when computers were used, what they were used for and who used them from hundreds of papers published during these years. The use of the EDSAC, EDSAC 2 and TITAN computers was found to increase considerably over this time-scale and they were used for a diverse range of applications. The (...) majority of references to computer operators and programmers referred to women, 57% for astronomy and 62% for crystallography, in contrast to a very small proportion, 4% and 13% respectively, of female authors of papers. (shrink)

We present a computer-supported approach for the logical analysis and conceptual explicitation of argumentative discourse. Computational hermeneutics harnesses recent progresses in automated reasoning for higher-order logics and aims at formalizing natural-language argumentative discourse using flexible combinations of expressive non-classical logics. In doing so, it allows us to render explicit the tacit conceptualizations implicit in argumentative discursive practices. Our approach operates on networks of structured arguments and is iterative and two-layered. At one layer we search for logically correct formalizations for each (...) of the individual arguments. At the next layer we select among those correct formalizations the ones which honor the argument’s dialectic role, i.e. attacking or supporting other arguments as intended. We operate at these two layers in parallel and continuously rate sentences’ formalizations by using, primarily, inferential adequacy criteria. An interpretive, logical theory will thus gradually evolve. This theory is composed of meaning postulates serving as explications for concepts playing a role in the analyzed arguments. Such a recursive, iterative approach to interpretation does justice to the inherent circularity of understanding: the whole is understood compositionally on the basis of its parts, while each part is understood only in the context of the whole. We summarily discuss previous work on exemplary applications of human-in-the-loop computational hermeneutics in metaphysical discourse. We also discuss some of the main challenges involved in fully-automating our approach. By sketching some design ideas and reviewing relevant technologies, we argue for the technological feasibility of a highly-automated computational hermeneutics. (shrink)

Classic text considersgeneral theory of computability, computable functions, operations on computable functions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.

Currently, there is widespread skepticism that higher cognitive processes, given their apparent flexibility and globality, could be carried out by specialized computational devices, or modules. This skepticism is largely due to Fodor’s influential definition of modularity. From the rather flexible catalogue of possible modular features that Fodor originally proposed has emerged a widely held notion of modules as rigid, informationally encapsulated devices that accept highly local inputs and whose opera- tions are insensitive to context. It is a mistake, however, to (...) equate such features with computational devices in general and therefore to assume, as Fodor does, that higher cognitive processes must be non-computational. Of the many possible non-Fodorean architectures, one is explored here that offers possible solutions to computational problems faced by conventional modular systems: an ‘enzymatic’ architecture. Enzymes are computational devices that use lock-and-key template matching to iden- tify relevant information (substrates), which is then operated upon and returned to a common pool for possible processing by other devices. Highly specialized enzymes can operate together in a common pool of information that is not pre-sorted by information type. Moreover, enzymes can use molecular ‘tags’ to regulate the operations of other devices and to change how particular substrates are construed and operated upon, allowing for highly interactive, context-specific processing. This model shows how specialized, modular processing can occur in an open system, and suggests that skepti- cism about modularity may largely be due to failure to consider alternatives to the standard model. (shrink)

The issue of proper functioning of operative computing and the utility of program verification, both in general and of specific methods, has been discussed a lot. In many of those discussions, attempts have been made to take mathematics as a model of knowledge and certitude achieving, and accordingly infer about the suitable ways to handle computing. I shortly review three approaches to the subject, and then take a stance by considering social factors which affect the epistemic status of both mathematics (...) and computing. I use the analogy between mathematics and computing in reverse—that is to say, I consider operative computing as a form of making mathematics, and so attempt to learn from computing to mathematics in general. I conclude that mathematics engineering is a field to be both developed for practical improvement of doing mathematics and taken into consideration while philosophizing about mathematics as well. (shrink)

The medium‐independence of computational descriptions has shaped common conceptions of computational explanation. So long as our goal is to explain how a system successfully carries out its computations, then we only need to describe the abstract series of operations that achieve the desired input–output mapping, however they may be implemented. It is argued that this abstract conception of computational explanation cannot be applied to so‐called real‐time computing systems, in which meeting temporal deadlines imposed by the systems with which a device (...) interfaces are constitutive of the computing tasks that a device performs. Instead, real‐time computing reveals the need for alternative conceptions of computational explanation, as well as computational implementation, that eschew medium‐independence. (shrink)

Cloud computing is rapidly gaining traction in business. It offers businesses online services on demand (such as Gmail, iCloud and Salesforce) and allows them to cut costs on hardware and IT support. This is the first paper in business ethics dealing with this new technology. It analyzes the informational duties of hosting companies that own and operate cloud computing datacenters (e.g., Amazon). It considers the cloud services providers leasing ‘space in the cloud’ from hosting companies (e.g, Dropbox, Salesforce). And it (...) examines the business and private ‘clouders’ using these services. The first part of the paper argues that hosting companies, services providers and clouders have mutual informational (epistemic) obligations to provide and seek information about relevant issues such as consumer privacy, reliability of services, data mining and data ownership. The concept of interlucency is developed as an epistemic virtue governing ethically effective communication. The second part considers potential forms of government restrictions on or proscriptions against the development and use of cloud computing technology. Referring to the concept of technology neutrality, it argues that interference with hosting companies and cloud services providers is hardly ever necessary or justified. It is argued, too, however, that businesses using cloud services (banks, law firms, hospitals etc. storing client data in the cloud, e.g.) will have to follow rather more stringent regulations. (shrink)

Brownian computers are supposed to illustrate how logically reversible mathematical operations can be computed by physical processes that are thermodynamically reversible or nearly so. In fact, they are thermodynamically irreversible processes that are the analog of an uncontrolled expansion of a gas into a vacuum.

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to investigate semantic (...) distinctions between quantified reciprocal sentences. We show a computational dichotomy<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of the formal<br>semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science. (shrink)

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The (...) importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn—Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense. (shrink)

We study the computational complexity of the universal and quasi-equational theories of classes of bounded distributive lattices with a negation operation, i.e., a unary operation satisfying a subset of the properties of the Boolean negation. The upper bounds are obtained through the use of partial algebras. The lower bounds are either inherited from the equational theory of bounded distributive lattices or obtained through a reduction of a global satisfiability problem for a suitable system of propositional modal logic.

This dissertation is an investigation into the degree to which the mathematics used in physical theories can be constructivized. The techniques of recursive function theory and classical logic are used to separate out the algorithmic content of mathematical theories rather than attempting to reformulate them in terms of "intuitionistic" logic. The guiding question is: are there experimentally testable predictions in physics which are not computable from the data? ;The nature of Church's thesis, that the class of effectively calculable functions (...) on the natural numbers is identical to the class of general recursive functions, is discussed. It is argued that this thesis is an example of an explication of the very notion of an effectively calculable function. This is contrary to a view of the thesis as a hypothesis about the limitations of the human mind. ;The extension to functions of a real variable of the notion of effective calculability is discussed, and it is argued that a function of a real variable must be continuous in order to be considered effectively calculable . The relation between continuity and computability is significant for the problem at hand. The results of a well-designed experiment do not depend critically upon the precise values of the relevant parameters. Accordingly, if the solution to a problem in mathematical physics depends discontinuously upon the data, it cannot be regarded as an experimentally testable prediction of the theory. The principle that the testable predictions of a physical theory cannot be singular is known as the principle of regularity. This principle is significant, because discontinuities generate non-computability, but they also disqualify a prediction from being experimentally testable. ;A mathematical framework is set up for discussing computability in physical theories. This framework is then applied to the case of quantum mechanics. It is found that, due to the use of unbounded operators in the theory, noncomputable objects appear, but predictions which satisfy the principle of regularity are nevertheless computable functions of the data. (shrink)

In this paper I criticize a view of functional localization in neuroscience, which I call “computational absolutism”. “Absolutism” in general is the view that each part of the brain should be given a single, univocal function ascription. Traditional varieties of absolutism posit that each part of the brain processes a particular type of information and/or performs a specific task. These function attributions are currently beset by physiological evidence which seems to suggest that brain areas are multifunctional—that they process distinct information (...) and perform different tasks depending on context. Many theorists take this contextual variation as inimical to successful localization, and claim that we can avoid it by changing our functional descriptions to computational descriptions. The idea is that we can have highly generalizable and predictive functional theories if we can discover a single computation performed by each area regardless of the specific context in which it operates. I argue, drawing on computational models of perceptual area MT, that this computational version of absolutism fails to come through on its promises. In MT, the modeling field has not produced a univocal computational description, but instead a plurality of models analyzing different aspects of MT function. Moreover, CA cannot appeal to theoretical unification to solve this problem, since highly general models, on their own, neither explain nor predict what MT does in any particular context. I close by offering a perspective on neural modeling inspired by Nancy Cartwright’s and Margaret Morrison’s views of modeling in the physical sciences. (shrink)

Computational models of infant word‐finding typically operate over transcriptions of infant‐directed speech corpora. It is now possible to test models of word segmentation on speech materials, rather than transcriptions of speech. We propose that such modeling efforts be conducted over the speech of the experimental stimuli used in studies measuring infants' capacity for learning from spoken sentences. Correspondence with infant outcomes in such experiments is an appropriate benchmark for models of infants. We demonstrate such an analysis by applying the DP‐Parser (...) model of Algayres and colleagues to auditory stimuli used in infant psycholinguistic experiments by Pelucchi and colleagues. The DP‐Parser model takes speech as input, and creates multiple overlapping embeddings from each utterance. Prospective words are identified as clusters of similar embedded segments. This allows segmentation of each utterance into possible words, using a dynamic programming method that maximizes the frequency of constituent segments. We show that DP‐Parse mimics American English learners' performance in extracting words from Italian sentences, favoring the segmentation of words with high syllabic transitional probability. This kind of computational analysis over actual stimuli from infant experiments may be helpful in tuning future models to match human performance. (shrink)