We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel (...) random-access machine in polylogarithmic parallel time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. (shrink)

This book is dedicated to a classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while presenting the basic ideas of whole number, function, proof, and real number. Part II starts with readings from Turing and Post leading to the formal theory of recursive functions. Part III (...) presents sufficient formal logic to give a full development of Gödel's incompleteness theorems. Part IV considers the significance of the technical work with a discussion of Church's Thesis and readings on the foundations of mathematics. This new edition contains the timeline "Computability and Undecidability" as well as the essay "On mathematics". (shrink)

Quantum mechanical measurements on a physical system are represented by observables - Hermitian operators on the state space of the observed system. It is an important question whether all observables may be realized, in principle, as measurements on a physical system. Dirac’s influential text ( [1], page 37) makes the following assertion on the question: The question now presents itself – Can every observable be measured? The answer theoretically is yes. In practice it may be very awkward, or perhaps even (...) beyond the ingenuity of the experimenter, to devise an apparatus which could measure some particular observable, but the theory always allows one to imagine that the measurement can be made. This Letter re-examines the question of whether it is possible, even in principle, to measure every quantum mechanical observable. Unexpectedly, ideas from com-. (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)

Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis of ourgeneral concept (...) of an effective procedure; mundane procedures and Turing machine procedures are different kinds of procedure. Moreover, the same sequence ofparticular physical action can realize both a mundane procedure and a Turing machine procedure; it is sequences of particular physical actions, not mundane procedures, which enter the world of mathematics. I conclude by discussing whether genuinely continuous physical processes can enter the world of real numbers and compute real-valued functions. I argue that the same kind of correspondence assumptions that are made between non-numerical structures and the natural numbers, in the case of Turing machines and personal computers, can be made in the case of genuinely continuous, physical processes and the real numbers. (shrink)

The discrepancy between syntax and semantics is a painstaking issue that hinders a better comprehension of the underlying neuronal processes in the human brain. In order to tackle the issue, we at first describe a striking correlation between Wittgenstein's Tractatus, that assesses the syntactic relationships between language and world, and Perlovsky's joint language-cognitive computational model, that assesses the semantic relationships between emotions and “knowledge instinct”. Once established a correlation between a purely logical approach to the language and computable psychological (...) activities, we aim to find the neural correlates of syntax and semantics in the human brain. Starting from topological arguments, we suggest that the semantic properties of a proposition are processed in higher brain's functional dimensions than the syntactic ones. In a fully reversible process, the syntactic elements embedded in Broca's area project into multiple scattered semantic cortical zones. The presence of higher functional dimensions gives rise to the increase in informational content that takes place in semantic expressions. Therefore, diverse features of human language and cognitive world can be assessed in terms of both the logic armor described by the Tractatus, and the neurocomputational techniques at hand. One of our motivations is to build a neuro-computational framework able to provide a feasible explanation for brain's semantic processing, in preparation for novel computers with nodes built into higher dimensions. (shrink)

Epstein and Carnielli's fine textbook on logic and computability is now in its second edition. The readers of this journal might be particularly interested in the timeline `Computability and Undecidability' added in this edition, and the included wall-poster of the same title. The text itself, however, has some aspects which are worth commenting on.

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers by (...) Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

Inspired from a joint work by A. Beckmann, S. Buss and S. Friedman, we propose a class of set-theoretic functions, predicatively computable set functions. Each function in this class is polynomial time computable when we restrict to finite binary strings.

The first-order logical theory Th $({\mathbb{N}},x + 1,F(x))$ is proved to be complete for the class ATIME-ALT $(2^{O(n)},O(n))$ when $F(x) = 2^{x}$ , and the same result holds for $F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)$ , and F(x) = tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.

As is well known the derivative of a computable and C1 function may not be computable. For a computable and C∞ function f, the sequence {f} of its derivatives may fail to be computable as a sequence, even though its derivative of any order is computable. In this paper we present a necessary and sufficient condition for the sequence {f} of derivatives of a computable and C∞ function f to be computable. We also (...) give a sharp regularity condition on an initial computable function f which insures the computability of its derivative f′. (shrink)

The ArgumentWhat kind of objects are computer programs used for simulation purposes in scientific settings? The current investigation treats a special case. It focuses on “event generators,” the program packages that particle physicists construct and use to simulate mechanisms of particle production. The paper is an attempt to bring the multiplex and unfolding character of such knowledge objects to the fore: Multiple meanings and functions are embodied in the object and can be drawn out selectively according to the requirements (...) of a work setting. The object's conceptual complexity governs its application in some contexts, while the object is considered a mere “black box,” transparent and ready-to-hand, in others. These two poles span a full spectrum of object aspects, functions, and conceptions. Event generators are ideas turned into software, testing grounds for models, just a tool to study the performance of a detector, etc. The object's multiplex nature is submitted to negotiation among different actors. (shrink)

In this paper we will state and prove some comparative theorems concerning PRA and IΣ1. We shall provide a characterization of IΣ1 in terms of PRA and iterations of a class of functions. In particular, we prove that for this class of functions the difference between IΣ1 and PRA is exactly that, where PRA is closed under iterations of these functions, IΣ1 is moreover provably closed under iteration. We will formulate a sufficient condition for a model of (...) PRA to be a model of IΣ1. This condition is used to give a model-theoretic proof of Parsons’ theorem, that is, IΣ1 is Π2-conservative over PRA. We shall also give a purely syntactical proof of Parsons’ theorem. Finally, we show that IΣ1 proves the consistency of PRA on a definable IΣ1-cut. This implies that proofs in IΣ1 can have non-elementary speed up over proofs in PRA. (shrink)

We begin by distinguishing computationalism from a number of other theses that are sometimes conflated with it. We also distinguish between several important kinds of computation: computation in a generic sense, digital computation, and analog computation. Then, we defend a weak version of computationalism—neural processes are computations in the generic sense. After that, we reject on empirical grounds the common assimilation of neural computation to either analog or digital computation, concluding that neural computation is sui generis. Analog computation requires continuous (...) signals; digital computation requires strings of digits. But current neuroscientific evidence indicates that typical neural signals, such as spike trains, are graded like continuous signals but are constituted by discrete functional elements (spikes); thus, typical neural signals are neither continuous signals nor strings of digits. It follows that neural computation is sui generis. Finally, we highlight three important consequences of a proper understanding of neural computation for the theory of cognition. First, understanding neural computation requires a specially designed mathematical theory (or theories) rather than the mathematical theories of analog or digital computation. Second, several popular views about neural computation turn out to be incorrect. Third, computational theories of cognition that rely on non-neural notions of computation ought to be replaced or reinterpreted in terms of neural computation. (shrink)

Driven by the question, 'What is the computational content of a (formal) proof?', this book studies fundamental interactions between proof theory and computability. It provides a unique self-contained text for advanced students and researchers in mathematical logic and computer science. Part I covers basic proof theory, computability and Gödel's theorems. Part II studies and classifies provable recursion in classical systems, from fragments of Peano arithmetic up to Π11-CA0. Ordinal analysis and the (Schwichtenberg-Wainer) subrecursive hierarchies play a central role and are (...) used in proving the 'modified finite Ramsey' and 'extended Kruskal' independence results for PA and Π11-CA0. Part III develops the theoretical underpinnings of the first author's proof assistant MINLOG. Three chapters cover higher-type computability via information systems, a constructive theory TCF of computable functionals, realizability, Dialectica interpretation, computationally significant quantifiers and connectives and polytime complexity in a two-sorted, higher-type arithmetic with linear logic. (shrink)

This volume is a guide to two types of transcendence of academic borders which seem necessary for understanding and modelling brain function.

We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time (...) or memory, to be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. -/- We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition. (shrink)

This introduction to certain mathematical topics central to theoretical computer science treats computability and recursive functions, formal languages and automata, computational complexity, and cruptography. The presentation is essentially self-contained with detailed proofs of all statements provided. Although it begins with the basics, it proceeds to some of the most important recent developments in theoretical computer science.

Law, Human Agency and Autonomic Computing interrogates the legal implications of the notion and experience of human agency implied by the emerging paradigm of autonomic computing, and the socio-technical infrastructures it supports. The development of autonomic computing and ambient intelligence âe" self-governing systems âe" challenge traditional philosophical conceptions of human self-constitution and agency, with significant consequences for the theory and practice of constitutional self-government. Ideas of identity, subjectivity, agency, personhood, intentionality, and embodiment are all central to the functioning of modern (...) legal systems. But once artificial entities become more autonomic, and less dependent on deliberate human intervention, criteria like agency, intentionality and self-determination, become too fragile to serve as defining criteria for human subjectivity, personality or identity, and for characterizing the processes through which individual citizens become moral and legal subjects. Are autonomic âe" yet artificial âe" systems shrinking the distance between (acting) subjects and (acted upon) objects? How âe~distinctively humanâe(tm) will agency be in a world of autonomic computing? Or, alternatively, does autonomic computing merely disclose that we were never, in this sense, âe~humanâe(tm) anyway? A dialogue between philosophers of technology and philosophers of law, this book addresses these questions, as it takes up the unprecedented opportunity that autonomic computing and ambient intelligence offer for a reassessment of the most basic concepts of law. (shrink)

Law, Human Agency and Autonomic Computing interrogates the legal implications of the notion and experience of human agency implied by the emerging paradigm of autonomic computing, and the socio-technical infrastructures it supports. The development of autonomic computing and ambient intelligence âe" self-governing systems âe" challenge traditional philosophical conceptions of human self-constitution and agency, with significant consequences for the theory and practice of constitutional self-government. Ideas of identity, subjectivity, agency, personhood, intentionality, and embodiment are all central to the functioning of modern (...) legal systems. But once artificial entities become more autonomic, and less dependent on deliberate human intervention, criteria like agency, intentionality and self-determination, become too fragile to serve as defining criteria for human subjectivity, personality or identity, and for characterizing the processes through which individual citizens become moral and legal subjects. Are autonomic âe" yet artificial âe" systems shrinking the distance between (acting) subjects and (acted upon) objects? How âe~distinctively humanâe(tm) will agency be in a world of autonomic computing? Or, alternatively, does autonomic computing merely disclose that we were never, in this sense, âe~humanâe(tm) anyway? A dialogue between philosophers of technology and philosophers of law, this book addresses these questions, as it takes up the unprecedented opportunity that autonomic computing and ambient intelligence offer for a reassessment of the most basic concepts of law. (shrink)

The basic motivation behind this work is to tie together various computational complexity classes, whether over different domains such as the naturals or the reals, or whether defined in different manners, via function algebras (Real Recursive Functions) or via Turing Machines (Computable Analysis). We provide general tools for investigating these issues, using two techniques we call approximation and lifting. We use these methods to obtain two main theorems. First, we provide an alternative proof of the result from Campagnolo (...) et al. (J Complex 18:977–1000, 2002), which precisely relates the Kalmar elementary computable functions to a function algebra over the reals. Second, we build on that result to extend a result of Bournez and Hainry (Theor Comput Sci 348(2–3):130–147, 2005), which provided a function algebra for the ${\mathcal{C}}^2$ real elementary computable functions; our result does not require the restriction to ${\mathcal{C}}^2$ functions. In addition to the extension, we provide an alternative approach to the proof. Their proof involves simulating the operation of a Turing Machine using a function algebra. We avoid this simulation, using a technique we call lifting, which allows us to lift the classic result regarding the elementary computable functions to a result on the reals. The two new techniques bring a different perspective to these problems, and furthermore appear more easily applicable to other problems of this sort. (shrink)

There is a prevalent notion among cognitive scientists and philosophers of mind that computers are merely formal symbol manipulators, performing the actions they do solely on the basis of the syntactic properties of the symbols they manipulate. This view of computers has allowed some philosophers to divorce semantics from computational explanations. Semantic content, then, becomes something one adds to computational explanations to get psychological explanations. Other philosophers, such as Stephen Stich, have taken a stronger view, advocating doing away with semantics (...) entirely. This paper argues that a correct account of computation requires us to attribute content to computational processes in order to explain which functions are being computed. This entails that computational psychology must countenance mental representations. Since anti-semantic positions are incompatible with computational psychology thus construed, they ought to be rejected. Lastly, I argue that in an important sense, computers are not formal symbol manipulators. (shrink)

The paper shows how ideas that explain the sense of an expression as a method or algorithm for finding its reference, preshadowed in Frege’s dictum that sense is the way in which a referent is given, can be formalized on the basis of the ideas in Thomason (1980). To this end, the function that sends propositions to truth values or sets of possible worlds in Thomason (1980) must be replaced by a relation and the meaning postulates governing the behaviour of (...) this relation must be given in the form of a logic program. The resulting system does not only throw light on the properties of sense and their relation to computation, but also shows circular behaviour if some ingredients of the Liar Paradox are added. The connection is natural, as algorithms can be inherently circular and the Liar is explained as expressing one of those. Many ideas in the present paper are closely related to those in Moschovakis (1994), but receive a considerably lighter formalization. (shrink)

There is a prevalent notion among cognitive scientists and philosophers of mind that computers are merely formal symbol manipulators, performing the actions they do solely on the basis of the syntactic properties of the symbols they manipulate. This view of computers has allowed some philosophers to divorce semantics from computational explanations. Semantic content, then, becomes something one adds to computational explanations to get psychological explanations. Other philosophers, such as Stephen Stich, have taken a stronger view, advocating doing away with semantics (...) entirely. This paper argues that a correct account of computation requires us to attribute content to computational processes in order to explain which functions are being computed. This entails that computational psychology must countenance mental representations. Since anti-semantic positions are incompatible with computational psychology thus construed, they ought to be rejected. Lastly, I argue that in an important sense, computers are not formal symbol manipulators. (shrink)

Logic and Computation is concerned with techniques for formal theorem-proving, with particular reference to Cambridge LCF (Logic for Computable Functions). Cambridge LCF is a computer program for reasoning about computation. It combines methods of mathematical logic with domain theory, the basis of the denotational approach to specifying the meaning of statements in a programming language. This book consists of two parts. Part I outlines the mathematical preliminaries: elementary logic and domain theory. They are explained at an intuitive level, (...) giving references to more advanced reading. Part II provides enough detail to serve as a reference manual for Cambridge LCF. It will also be a useful guide for implementors of other programs based on the LCF approach. (shrink)

At the present time, when we are experiencing one of the extraordinary conditions in which the basics of life are shaken, exceptional practices concerning the sources of the meaning of the world of life have become one of the urgent issues for the sociology of religion to consider. This study discusses the reactions of people to the effects of the COVID-19 pandemic on the regularity of social life in the early stages in the framework of Muslim religious groups. Since the (...) forms of social organization reveal reactions in their own specific forms, a research design that considers the differences were preferred. The provision that ‘man is social by nature,’ which is the indispensable principle of social sciences, has been the main feature of important issues to elaborate in the restrictions of today’s pandemic. Religious socialization, which is important for the inquiry, is a phenomenon that is desired to be carried out on a continuous basis. Its performative dimension draws attention to important elements that affect the formation and the social ontology of the group, such as consciousness and solidarity. While some religious groups insist on face-to-face interaction and rituals, some of them prefer to use effectively digital tools and channels. This differing approach has become a public issue, especially during the pandemic process. On the other hand, there is a discussion in the context of the digital world of new media tools and the travel possibilities of transportation technology. The theoretical basis of this study, which deals with the insistence of religious groups on face-to-face interaction and rituals is represented from the scope of Erving Goffman. His analyzes face-to-face communication and his comments emphasizing the ritualistic nature of daily life are operationalized through two basic case studies: the first case is the persistence and practice of Tablīghī Djamā‘at, in its annual meetings in the early days of the pandemic. The discussion started with the practice of the religious group in Delhi (Nizamuddin Markaz), since they did not cancel their annual meeting despite the diagnosis of the disease. The second case is based on the ritual insistence of pilgrims in visiting shrines in the Iranian city of Qom. The insistence of the Shiite Islamic understanding on ritual and pilgrimage and the solidarity built with the consciousness based on it is a well-known phenomenon. In the Covid-19 pandemic, the risk of contamination caused by the mobility of the pilgrims coming to the city of Qom from countries such as Pakistan was discussed, as well as the contact and social distance during the Hajj. Two cases were handled with a qualitative design including case analysis method and descriptive analysis technique. The main purpose and intended contribution of the article are to reveal the insistence of face-to-face interaction through the performative based on rituals as an analytical explanatory on the social level. Inferences based on the analysis of religious groups’ response to restrictions in times of emergency build the importance of the issue. Case information identified in the context of the case study shows that groups with traditional interaction forms insist on their own practice in the field of uncertainty and initiative. Unless necessity eliminates the initiative, the determination of this insistence of traditional religious groups is not only theological but also ontological confirmation. It is understood that the members of the group took the initiative to represent their reputation within the group and their extent to dedicate to the group. The fact that Tablīghī Djamā‘at, the largest group of the transnational Islamic da‘wa (call), did not give up on a method based on demographic mobility, has been a matter of discussion. The insistence of the group is because of the methods that require every ordinary believer to accept to convey the da‘wa as his primary duty. On the other hand, Shiism, which stands out with its traditional structure and ritual intensity in the Islamic world, insisted on the initiative process in the pilgrimage phenomenon, on which it attached special importance and built its solidarity and identity on this phenomenon. This insistence aims preserving the dynamics and social ontology of the religious group in the performance of the membership system. Essentially, the individual in the group insists on his position in face-to-face interaction because having a role in a group also means having a face. Thus, this insistence performance by religious groups should also be read as a reflection of self-technologies. In the final analysis, the insistence put forward should be considered essentially in relation to the insistence on the position in social ontology. (shrink)

1. One theory or many? In 2004 a very interesting and readable article by Lenore Blum, entitled “Computing over the reals: Where Turing meets Newton,” appeared in the Notices of the American Mathematical Society. It explained a basic model of computation over the reals due to Blum, Michael Shub and Steve Smale (1989), subsequently exposited at length in their influential book, Complexity and Real Computation (1997), coauthored with Felipe Cucker. The ‘Turing’ in the title of Blum’s article refers of course (...) to Alan Turing, famous for his explication of the notion of mechanical computation on discrete data such as the integers. The ‘Newton’ there has to do to with the well known numerical method due to Isaac Newton for approximating the zeros of continuous functions under suitable conditions that is taken to be a paradigm of scientific computing. Finally, the meaning of “Turing meets Newton” in the title of Blum’s article has another, more particular aspect: in connection with the problem of controlling errors in the numerical solution of linear equations and inversion of matrices,Turing (1948) defined a notion of condition for the relation of changes in the output of a computation due to small changes in the input that is analogous to Newton’s definition of the derivative. The thrust of Blum’s 2004 article was that the BSS model of computation on the reals is the appropriate foundation for scientific computing in general. By way of response, two years later another very interesting and equally readable article appeared in the Notices, this time by Mark Braverman and Stephen Cook (2006) entitled “Computing over the reals: Foundations for scientific computing,” in which the authors argued that the requisite foundation is provided by a quite different “bit computation” model, that is in fact prima facie incompatible with the BSS model. The bit computation model goes back to ideas due to Stefan Banach and Stanislaw Mazur in the latter part of the 1930s, but the first publication was not made until Mazur (1963).. (shrink)

In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr (...) Cutland begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest. (shrink)

On Buddhist virtues, ethics, aesthetics, and truth.

We explore the relationship between analytic behavior of a computable real valued function and the computability-theoretic complexity of the individual values of its derivative almost-everywhere. Given a computable function f, the values of its derivative \\), where they are defined, are uniformly computable from \, the Turing jump of the input. It is known that when f is \, the values of \\) are actually computable from x. We construct a \ function f so that, almost (...) everywhere, \\ge _T x'\). Although the values \\) at each point x cannot uniformly compute the corresponding jumps \ of the inputs x almost everywhere for any \ function f, we produce an example of a \ function f such that \\ge _T \emptyset '\) uniformly on subsets of arbitrarily large measure, effectively. We also explore analogous questions for weaker smoothness conditions, such as for f differentiable everywhere, and f differentiable almost everywhere. (shrink)

Much of computational cognitive science construes human cognitive capacities as representational capacities, or as involving representation in some way. Computational theories of vision, for example, typically posit structures that represent edges in the distal scene. Neurons are often said to represent elements of their receptive fields. Despite the ubiquity of representational talk in computational theorizing there is surprisingly little consensus about how such claims are to be understood. The point of this chapter is to sketch an account of the nature (...) and function of representation in computational cognitive models. (shrink)