We examine the problem of generating definite noun phrases that are appropriate referring expressions; that is, noun phrases that (a) successfully identify the intended referent to the hearer whilst (b) not conveying to him or her any false conversational implicatures (Grice, 1975). We review several possible computational interpretations of the conversational implicature maxims, with different computational costs, and argue that the simplest may be the best, because it seems to be closest to what human speakers do. We describe our recommended (...) algorithm in detail, along with a specification of the resources a host system must provide in order to make use of the algorithm, and an implementation used in the natural language generation component of the IDAS system. (shrink)

This article offers a survey of computational research on referring expressions generation (REG). It introduces the REG problem and describes early work in this area, discussing what basic assumptions lie behind it, and showing how its remit has widened in recent years. We discuss computational frameworks underlying REG, and demonstrate a recent trend that seeks to link up REG algorithms with well-established Knowledge Representation traditions. Considerable attention is given to recent efforts at evaluating REG algorithms and the lessons that they (...) allow us to learn. The article concludes with a discussion of the way forward in REG, focussing on references in larger and more realistic settings. (shrink)

The tension between expressive power and computational tractability poses an acute problem for theories of underspecified semantic representation. In previous work we have presented an account of underspecified scope representations within Property Theory with Curry Typing, an intensional first-order theory for natural language semantics. Here we show how filters applied to the underspecified-scope terms of PTCT permit both expressive completeness and the reduction of computational complexity in a significant class of non-worst case scenarios.

In Fox and Lappin (2005a) we propose Property Theory with Curry Typing (PTCT) as a formal framework for the semantics of natural language. PTCT allows finegrained distinctions of meaning without recourse to modal notions like (im)possible worlds. It also supports a unified dynamic treatment of pronominal anaphora and VP ellipsis, as well as related phenomena such as gapping and pseudo-gapping.

We discuss here one of our projects, aimed at developing an automatic facial expression interpreter, mainly in terms of signaled emotions. We present some of the relevant findings on facial expressions from cognitive science and psychology that can be understood by and be useful to researchers in Human-Computer Interaction and Artificial Intelligence. We then give an overview of HCI applications involving automated facial expression recognition, we survey some of the latest progresses in this area reached by various approaches in computer (...) vision, and we describe the design of our facial expression recognizer. We also give some background knowledge about our motivation for understanding facial expressions and we propose an architecture for a multimodal intelligent interface capable of recognizing and adapting to computer users¿ affective states. Finally, we discuss current interdisciplinary issues and research questions which will need to be addressed for further progress to be made in the promising area of computational facial expression recognition. (shrink)

This article introduces a computational model which illustrates how a population of agents can coordinate a vocabulary for goal oriented behavior through repeated local interactions, called “Action Games”. Using principles of self organization and specific assumptions on their behavior, the agents learn the goals and a vocabulary for them. It is shown that the proposed model can be used to investigate the coordination of vocabularies for goal oriented behavior both in a vertical and in a horizontal transmission scheme. Furthermore, it (...) is shown that in this model shared vocabularies can only be learned from multiple demonstrations consisting of exactly these actions that are strictly required to reach the goal. Keywords: robot imitation; self organization; vocabularies. (shrink)

This article introduces a computational model which illustrates how a population of agents can coordinate a vocabulary for goal oriented behavior through repeated local interactions, called “Action Games”. Using principles of self organization and specific assumptions on their behavior, the agents learn the goals and a vocabulary for them. It is shown that the proposed model can be used to investigate the coordination of vocabularies for goal oriented behavior both in a vertical and in a horizontal transmission scheme. Furthermore, it (...) is shown that in this model shared vocabularies can only be learned from multiple demonstrations consisting of exactly these actions that are strictly required to reach the goal. Keywords: robot imitation; self organization; vocabularies. (shrink)

The work of Chandra and Harel contained in Chandra and Harel 156–178) can be considered as the beginning of the construction of a theoretical framework in which the computability and the complexity of queries to relational databases could be studied. In the definition of the class CQ of computable queries, the authors included untyped queries , that is, queries whose answers are relations of possibly different arities on different relational structures or databases. However, it seems that in the quite wide (...) and important work which followed on the subject, untyped queries were not considered at all, neither in the abstract machines side , nor in the logic framework. We propose to re-introduce these queries in the study of query computability and complexity without the need to leave the relational model. One important application which we consider in the theoretical setting is the computation of numerical queries, that is, queries which range over the naturals. Numerical queries do not fit in the current state of the theory regarding the two formalisms referenced above, since they can result in numerical values which are not necessarily in the domain of the given structure. We define an extension of the reflective relational machine of Abiteboul et al. , which we call untyped reflective relational machine , and we prove that this model is complete considering the whole class CQ . In the logic framework, we define a new quantifier, which we call conditional quantifier , and we build with it an infinitary logic which we denote by L ω 1 ω c . The difference between this logic and the well-known infinitary logic L ω 1 ω is that a formula of our logic can induce relations of different arities on different structures or databases. Then we prove that L ω 1 ω c strictly includes the whole sub-class of the total computable queries, including untyped queries. Finally, we define a fragment of L ω 1 ω c which we prove that exactly captures the sub-class of the total computable queries, but which is undecidable. We also define an undecidable fragment of L ω 1 ω which exactly captures the sub-class of the total and typed computable queries. (shrink)

I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." The definitions might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous, If the meaning of the words "machine" and "think" are to be found by examining how they are commonly used it is difficult to escape the conclusion that the meaning and the answer to (...) the question, "Can machines think?" is to be sought in a statistical survey such as a Gallup poll. But this is absurd. Instead of attempting such a definition I shall replace the question by another, which is closely related to it and is expressed in relatively unambiguous words. The new form of the problem can be described in terms of a game which we call the 'imitation game." It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." The interrogator is allowed to put questions to A and B. We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?". (shrink)

The theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning, facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for the solution of precisely described questions and problems. The book is a unified introduction to the modern theory of these concepts, to the way in which they developed first in mathematical logic and computability theory and later in automata theory, (...) and to the theory of formal languages and complexity theory. Apart from considering the fundamental themes and classical aspects of these areas, the subject matter has been selected to give priority throughout to the new aspects of traditional questions, results and methods which have developed from the needs or knowledge of computer science and particularly of complexity theory. It is both a textbook for introductory courses in the above-mentioned disciplines as well as a monograph in which further results of new research are systematically presented and where an attempt is made to make explicit the connections and analogies between a variety of concepts and constructions. (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)

This chapter contains sections titled: Approaches in Computer Ethics Topics in Computer Ethics Moral Responsibility Other Topics References and Further Reading.

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)

We study human performance in two classical NP‐hard optimization problems: Set Cover and Maximum Coverage. We suggest that Set Cover and Max Coverage are related to means selection problems that arise in human problem‐solving and in pursuing multiple goals: The relationship between goals and means is expressed as a bipartite graph where edges between means and goals indicate which means can be used to achieve which goals. While these problems are believed to be computationally intractable in general, they become more (...) tractable when the structure of the network resembles a tree. Thus, our main prediction is that people should perform better with goal systems that are more tree‐like. We report three behavioral experiments which confirm this prediction. Our results suggest that combinatorial parameters that are instrumental to algorithm design can also be useful for understanding when and why people struggle to choose between multiple means to achieve multiple goals. (shrink)

This book provides a general survey of the main concepts, questions and results that have been developed in the recent interactions between quantum information, quantum computation and logic. Divided into 10 chapters, the books starts with an introduction of the main concepts of the quantum-theoretic formalism used in quantum information. It then gives a synthetic presentation of the main “mathematical characters” of the quantum computational game: qubits, quregisters, mixtures of quregisters, quantum logical gates. Next, the book investigates the puzzling (...) entanglement-phenomena and logically analyses the Einstein–Podolsky–Rosen paradox and introduces the reader to quantum computational logics, and new forms of quantum logic. The middle chapters investigate the possibility of a quantum computational semantics for a language that can express sentences like “Alice knows that everybody knows that she is pretty”, explore the mathematical concept of quantum Turing machine, and illustrate some characteristic examples that arise in the framework of musical languages. The book concludes with an analysis of recent discussions, and contains a Mathematical Appendix which is a survey of the definitions of all main mathematical concepts used in the book. (shrink)

An ideal vision model accounts for behavior and neurophysiology in both naturalistic conditions and designed lab experiments. Unlike psychological theories, artificial neural networks (ANNs) actually perform visual tasks and generate testable predictions for arbitrary inputs. These advantages enable ANNs to engage the entire spectrum of the evidence. Failures of particular models drive progress in a vibrant ANN research program of human vision.

Discussions about the achievements and limitations of the various approaches to the development of intelligent systems can have an essential impact on empirically based research, and with that also on the future development of computer technologies. However, such discussions are often based on vague concepts and assumptions. In this context, we claim that the proposed `three-world ontology'' offers the most appropriate conceptual framework in which the basic problems concerned with cognition and computation can be suitably expressed and discussed, although (...) the solutions of some of these problems seem to lie beyond the horizon of our current understanding. We stress the necessity to differentiate between authentic and functional cognitive abilities; although computation is not a plausible way towards authentic intelligence, we claim that computational systems do offer virtually unlimited possibilities to replicate and surpass human cognitive abilities on the functional level. (shrink)

Facial expression recognition plays a significant part in artificial intelligence and computer vision. However, most of facial expression recognition methods have not obtained satisfactory results based on low-level features. The existed methods used in facial expression recognition encountered the major issues of linear inseparability, large computational burden, and data redundancy. To obtain satisfactory results, we propose an innovative deep learning model using the kernel entropy component analysis network and directed acyclic graph support vector machine. We use the KECANet in the (...) feature extraction stage. In the stage of output, binary hashing and blockwise histograms are adopted. We sent the final output features to the DAGSVM classifier for expression recognition. We test the performance of our proposed method on three databases of CK+, JAFFE, and CMU Multi-PIE. According to the experiment results, the proposed method can learn high-level features and provide more recognition information in the stage of training, obtaining a higher recognition rate. (shrink)

Various algorithms have been proposed for learning (partial) genetic regulatory networks through systematic measurements of differential expression in wild type versus strains in which expression of specific genes has been suppressed or enhanced, as well as for determining the most informative next experiment in a sequence. While the behavior of these algorithms has been investigated for toy examples, the full computational complexity of the problem has not received sufficient attention. We show that finding the true regulatory network requires (in the (...) worst-case) exponentially many experiments (in the number of genes). Perhaps more importantly, we provide an algorithm for determining the set of regulatory networks consistent with the observed data. We then show that this algorithm is infeasible for realistic data (specifically, nine genes and ten experiments). This infeasibility is not due to an algorithmic flaw, but rather to the fact that there are far too many networks consistent with the data (10 18 in the provided example). We conclude that gene perturbation experiments are useful in confirming regulatory network models discovered by other techniques, but not a feasible search strategy. (shrink)

Computational cognitive models hypothesize internal mental processes of human cognitive activities and express such activities by computer programs Such computational models often consist of many components and aspects Claims are often made that certain aspects of the models play a key role in modeling but such claims are sometimes not well justi ed or explored In this paper we rst review some fundamental distinctions and issues in computational modeling We then discuss in principle systematic ways of identifying the source of (...) power in the models.. (shrink)

This book provides an in-depth view of the current issues, problems and approaches in the computation of meaning as expressed in language. Aimed at linguists, computer scientists, and logicians with an interest in the computation of meaning, this book focuses on two main topics in recent research in computational semantics. The first topic is the definition and use of underspecified semantic representations, i.e. formal structures that represent part of the meaning of a linguistic object while leaving other parts (...) unspecified. The second topic discussed is semantic annotation. Annotated corpora have become an indispensable resource both for linguists and for developers of language and speech technology, especially when used in combination with machine learning methods. The annotation in corpora has only marginally addressed semantic information, however, since semantic annotation methodologies are still in their infancy. This book discusses the development and application of such methodologies. (shrink)

What is computer art? Do the concepts we usually employ to talk about art, such as ‘meaning’, ‘form’ or ‘expression’ apply to computer art? _A Philosophy of Computer Art_ is the first book to explore these questions. Dominic Lopes argues that computer art challenges some of the basic tenets of traditional ways of thinking about and making art and that to understand computer art we need to place particular emphasis on terms such as ‘interactivity’ and ‘user’. Drawing on a wealth (...) of examples he also explains how the roles of the computer artist and computer art user distinguishes them from makers and spectators of traditional art forms and argues that computer art allows us to understand better the role of technology as an art medium. (shrink)

previous theories and the relevance of those criticisms to the new accounts. Additionally, we have included a new section at the end, which gives some directions to literature outside of formal semantics in which the notion of mass has been employed. We looked at work on mass expressions in psycholinguistics and computational linguistics here, and we discussed some research in the history of philosophy and in metaphysics that makes use of the notion of mass.

In a rather general setting, we prove a number of basic theorems concerning computational complexity of derivability in adaptive logics. For that setting, the so-called standard format of adaptive logics is suitably adopted, and the corresponding completeness results are established in a very uniform way.

We study the computational complexity of reciprocal sentences with quantified antecedents. We observe a computational dichotomy between different interpretations of reciprocity, and shed some light on the status of the so-called Strong Meaning Hypothesis.

There seems to exist an indirect link between computer science and theology via psychology, which is founded on dualism. First, these theories from psychology, computer science and theology are considered that acknowledge the existence of (at least) two different kinds of reality, or, possibly, two different realms of the same reality. In order to express a root of incompatibility of science and theology, a distinction is drawn between ontological and epistemological dualism. It seems that computer science combines ontological monism with (...) epistemological monism, theology combines ontological and epistemological dualism, and psychologytakes a position of epistemological monism and is quite hesitant about the ontological status of the phenomena it analyzes. A direct transition from the computer metaphor to theology is almost impossible: there is no overlap of platforms between these domains. (shrink)

In this paper, the issues of computability and constructivity in the mathematics of physics are discussed. The sorts of questions to be addressed are those which might be expressed, roughly, as: Are the mathematical foundations of our current theories unavoidably non-constructive: or, Are the laws of physics computable?

This article introduces the topic ‘‘Production of Referring Expressions: Bridging the Gap between Computational and Empirical Approaches to Reference’’ of the journal Topics in Cognitive Science. We argue that computational and psycholinguistic approaches to reference production can benefit from closer interaction, and that this is likely to result in the construction of algorithms that differ markedly from the ones currently known in the computational literature. We focus particularly on determinism, the feature of existing algorithms that is perhaps most clearly at (...) odds with psycholinguistic results, discussing how future algorithms might include non-determinism, and how new psycholinguistic experiments could inform the development of such algorithms. (shrink)

Brain-Computer Interface is a set of technologies that are of increasing interest to researchers. BCI has been proposed as assistive technology for individuals who are non-communicative or paralyzed, such as those with amyotrophic lateral sclerosis or spinal cord injury. The technology has also been suggested for enhancement and entertainment uses, and there are companies currently marketing BCI devices for those purposes as well as health-related purposes. The unprecedented direct connection created by BCI between human brains and computer hardware raises various (...) ethical, social, and legal challenges that merit further examination and discussion. To identify and characterize the key issues associated with BCI use, we performed a scoping review of biomedical ethics literature, analyzing the ethics concerns cited across multiple disciplines, including philosophy and medicine. Based on this investigation, we report that BCI research and its potential translation to therapeutic intervention generate significant ethical, legal, and social concerns, notably with regards to personhood, stigma, autonomy, privacy, research ethics, safety, responsibility, and justice. Our review of the literature determined, furthermore, that while these issues have been enumerated extensively, few concrete recommendations have been expressed. We conclude that future research should focus on remedying a lack of practical solutions to the ethical challenges of BCI, alongside the collection of empirical data on the perspectives of the public, BCI users, and BCI researchers. (shrink)

We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a Σ03-condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n≥ 1 in ω, there exists a computable tree of finite height which is δ0n+1-categorical but (...) not δ0n-categorical. (shrink)

As AI Systems become increasingly autonomous, they are expected to engage in decision-making processes that have moral implications. In this research we integrate theoretical and empirical lines of thought to address the matters of moral reasoning and moral uncertainty in AI Systems. We reconceptualize the metanormative framework for decision-making under moral uncertainty and we operationalize it through a latent class choice model. The core idea being that moral heterogeneity in society can be codified in terms of a small number of (...) classes with distinct moral preferences and that this codification can be used to express moral uncertainty of an AI. Choice analysis allows for the identification of classes and their moral preferences based on observed choice data. Our reformulation of the metanormative framework is theory-rooted and practical in the sense that it avoids runtime issues in real time applications. To illustrate our approach we conceptualize a society in which AI Systems are in charge of making policy choices. While one of the systems uses a baseline morally certain model, the other uses a morally uncertain model. We highlight cases in which the AI Systems disagree about the policy to be chosen, thus illustrating the need to capture moral uncertainty in AI systems. (shrink)

Previous research has demonstrated how emotion resembling cues in the face help shape impression formation. Perhaps most notable in the literature to date, has been work suggesting that gender-related appearance cues are visually confounded with certain stereotypic expressive cues. Only a couple studies to date have used computer vision to directly map out and test facial structural resemblance to emotion expressions using facial landmark coordinates to estimate face shape. In one study using a Bayesian network classifier trained to detect emotional (...) expressions structural resemblance to a specific expression on a non-expressive face was found to influence trait impressions of others. In another study, a connectionist model trained to detect emotional expressions found different emotion-resembling cues in male vs. female faces. Despite this seminal work, direct evidence confirming the theoretical assertion that humans likewise utilize these emotion-resembling cues when forming impressions has been lacking. Across four studies, we replicate and extend these prior findings using new advances in computer vision to examine gender-related, emotion-resembling structure, color, and texture and their impact on gender-stereotypic impression formation. We show that all three are meaningfully related to human impressions of emotionally neutral faces. Further when applying the computer vision algorithms to experimentally manipulate faces, we show that humans derive similar impressions from them as did the computer. (shrink)

We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete metric space cannot be decomposed into countably many nowhere dense pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish two different logical versions of (...) the theorem, where one can be seen as the contrapositive form of the other one. The first version aims to find an uncovered point in the space, given a sequence of nowhere dense closed sets. The second version aims to find the index of a closed set that is somewhere dense, given a sequence of closed sets that cover the space. Even though the two statements behind these versions are equivalent to each other in classical logic, they are not equivalent in intuitionistic logic, and likewise, they exhibit different computational behavior in the Weihrauch lattice. Besides this logical distinction, we also consider different ways in which the sequence of closed sets is “given.” Essentially, we can distinguish between positive and negative information on closed sets. We discuss all four resulting versions of the Baire category theorem. Somewhat surprisingly, it turns out that the difference in providing the input information can also be expressed with the jump operation. Finally, we also relate the Baire category theorem to notions of genericity and computably comeager sets. (shrink)

Emojis and stickers are becoming increasingly popular in computer mediated communications. The present study examined the associations between personality traits and people’s reasons and patterns for using both emojis and stickers. Participants (n= 312) completed three on-line questionnaires assessing shyness, the Big Five personality traits and why and how they used emojis and stickers. Results revealed that shyness, neuroticism, extraversion and agreeableness were correlated with different reasons of usage. Moreover, some participants exhibited a tendency to adjust frequency of usage depending (...) on who the target person was and whether they were in a private or group chat. People who showed such tendencies were found to differ in personality with those who did not. Some differences in usage patterns were also observed between emojis and stickers. Together, the present study sheds more insights into how emojis and stickers can help people with different personality traits to achieve different purposes in their daily communication. (shrink)

In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly work as computational (...) models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

This paper presents an approach to the belief system based on a computational framework in three levels: first, the logic level with the definition of binary local rules, second, the arithmetic level with the definition of recursive functions and finally the behavioural level with the definition of a recursive construction pattern. Social communication is achieved when different beliefs are expressed, modified, propagated and shared through social nets. This approach is useful to mimic the belief system because the defined functions provide (...) different ways to process the same incoming information as well as a means to propagate it. Our model also provides a means to cross different beliefs so, any incoming information can be processed many times by the same or different functions as it occurs is social nets. (shrink)

Given a class ℱ oft otal functions in the set oft he natural numbers, one could study the real numbers that have arbitrarily close rational approximations explicitly expressible by means of functions from ℱ. We do this for classes ℱsatisfying certain closedness conditions. The conditions in question are satisfied for example by the class of all recursive functions, by the class of the primitive recursive ones, by any of the Grzegorczyk classes ℰnwith n ≥ 2, by the class of all (...) functions recursive in a given function and by the class of the functions primitive recursive in it, as well as by the class of all total functions in the set of the natural numbers. (shrink)

For the people who make them, music recommender systems hold a utopian promise: they can broaden listeners' horizons and help obscure musicians find audiences, taking advantage of the enormous catalogs offered by companies like Spotify, Apple Music, and their kin. But for critics, recommender systems have come to epitomize the potential harms of algorithms: they seem to reduce expressive culture to numbers, they normalize ever-broadening data collection, and they profile their users for commercial ends, tearing the social fabric into isolated (...) patches of atomized individuals. Drawing on years of ethnographic fieldwork, anthropologist Nick Seaver offers an account of how the makers of music recommendation navigate these tensions: how product managers understand their relationship with the users they want to help and to capture, how engineers imagine the abstract geography of the "world of music" as a space they control and care for, how scientists conceive of listening itself as a kind of data processing. The book rehumanizes the algorithmic systems that shape our world, foregrounding the ideas animating the people who build and maintain them. Seaver braids together the thinking of programmers and anthropologists, opening up the cultural world of computation in a vividly theorized book that ranges widely from cosmology to calculation, metaphor to myth, and captivation to care. (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)