Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, the $\mathbf{P} \neq \mathbf{NP}$ (...) problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof. (shrink)

This paper argues that the idea of a computer is unique. Calculators and analog computers are not different ideas about computers, and nature does not compute by itself. Computers, once clearly defined in all their terms and mechanisms, rather than enumerated by behavioral examples, can be more than instrumental tools in science, and more than source of analogies and taxonomies in philosophy. They can help us understand semantic content and its relation to form. This can be achieved because they have (...) the potential to do more than calculators, which are computers that are designed not to learn. Today’s computers are not designed to learn; rather, they are designed to support learning; therefore, any theory of content tested by computers that currently exist must be of an empirical, rather than a formal nature. If they are designed someday to learn, we will see a change in roles, requiring an empirical theory about the Turing architecture’s content, using the primitives of learning machines. This way of thinking, which I call the intensional view of computers, avoids the problems of analogies between minds and computers. It focuses on the constitutive properties of computers, such as showing clearly how they can help us avoid the infinite regress in interpretation, and how we can clarify the terms of the suggested mechanisms to facilitate a useful debate. Within the intensional view, syntax and content in the context of computers become two ends of physically realizing correspondence problems in various domains. (shrink)

Natural recursion in syntax is recursion by linguistic value, which is not syntactic in nature but semantic. Syntax-specific recursion is not recursion by name as the term is understood in theoretical computer science. Recursion by name is probably not natural because of its infinite typeability. Natural recursion, or recursion by value, is not species-specific. Human recursion is not syntax-specific. The values on which it operates are most likely domain-specific, including those for syntax. Syntax seems to require no more (and no (...) less) than the resource management mechanisms of an embedded push-down automaton (EPDA). We can conceive EPDA as a common automata-theoretic substrate for syntax, collaborative planning, i-intentions, and we-intentions. They manifest the same kind of dependencies. Therefore, syntactic uniqueness arguments for human behavior can be better explained if we conceive automata-constrained recursion as the most unique human capacity for cognitive processes. (shrink)

A response to a recent critique by Cem Bozşahin of the theory of syntactic semantics as it applies to Helen Keller, and some applications of the theory to the philosophy of computer science.

Why should moral philosophers, moral psychologists, and machine ethicists care about computational complexity? Debates on whether artificial intelligence (AI) can or should be used to solve problems in ethical domains have mainly been driven by what AI can or cannot do in terms of human capacities. In this paper, we tackle the problem from the other end by exploring what kind of moral machines are possible based on what computational systems can or cannot do. To do so, we analyze normative (...) ethics through the lens of computational complexity. First, we introduce computational complexity for the uninitiated reader and discuss how the complexity of ethical problems can be framed within Marr’s three levels of analysis. We then study a range of ethical problems based on consequentialism, deontology, and virtue ethics, with the aim of elucidating the complexity associated with the problems themselves (e.g., due to combinatorics, uncertainty, strategic dynamics), the computational methods employed (e.g., probability, logic, learning), and the available resources (e.g., time, knowledge, learning). The results indicate that most problems the normative frameworks pose lead to tractability issues in every category analyzed. Our investigation also provides several insights about the computational nature of normative ethics, including the differences between rule- and outcome-based moral strategies, and the implementation-variance with regard to moral resources. We then discuss the consequences complexity results have for the prospect of moral machines in virtue of the trade-off between optimality and efficiency. Finally, we elucidate how computational complexity can be used to inform both philosophical and cognitive-psychological research on human morality by advancing the moral tractability thesis. (shrink)

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)

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence (...) never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact. (shrink)

In this paper, I defend the metalinguistic solution to the problem of mathematical omniscience for the possible-worlds account of propositions by combining it with a computational model of knowledge and belief. The metalinguistic solution states that the objects of belief and ignorance in mathematics are relations between mathematical sentences and what they express. The most pressing problem for the metalinguistic strategy is that it still ascribes too much mathematical knowledge under the standard possible-worlds model of knowledge and belief on which (...) these are closed under entailment. I first argue that Stalnaker's fragmentation strategy is insufficient to solve this problem. I then develop an alternative, computational strategy: I propose a model of mathematical knowledge and belief adapted from the algorithmic model of Halpern et al. which, when combined with the metalinguistic strategy, entails that mathematical knowledge and belief require computational abilities to access metalinguistic information, and thus aren't closed under entailment. As I explain, the computational model generalizes beyond mathematics to a version of the functionalist theory of knowledge and belief that motivates the possible-worlds account in the first place. I conclude that the metalinguistic and computational strategies yield an attractive functionalist, possible-worlds account of mathematical content, knowledge, and inquiry. (shrink)

The present paper provides an analysis of Euler’s solutions to the Königsberg bridges problem. Euler proposes three different solutions to the problem, addressing their strengths and weaknesses along the way. I put the analysis of Euler’s paper to work in the philosophical discussion on mathematical explanations. I propose that the key ingredient to a good explanation is the degree to which it provides relevant information. Providing relevant information is based on knowledge of the structure in question, graphs in the present (...) case. I also propose computational complexity and logical strength as measures of relevant information. (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)

It is often indeterminate what function a given computational system computes. This phenomenon has been referred to as “computational indeterminacy” or “multiplicity of computations.” In this paper, we argue that what has typically been considered and referred to as the challenge of computational indeterminacy in fact subsumes two distinct phenomena, which are typically bundled together and should be teased apart. One kind of indeterminacy concerns a functional characterization of the system’s relevant behavior. Another kind concerns the manner in which the (...) abstract states are interpreted. We discuss the similarities and differences between the two kinds of computational indeterminacy, their implications for certain accounts of “computational individuation” in the literature, and their relevance to different levels of description within the computational system. We also examine the inter-relationships between our proposed accounts of the two kinds of indeterminacy and the main accounts of “computational implementation.”. (shrink)

What does it take to implement a computer? Answers to this question have often focused on what it takes for a physical system to implement an abstract machine. As Joslin observes, this approach neglects cases of software implementation—cases where one machine implements another by running a program. These cases, Joslin argues, highlight serious problems for mapping accounts of computer implementation—accounts that require a mapping between elements of a physical system and elements of an abstract machine. The source of these problems (...) is the complexity introduced by common design features of ordinary computers, features that would be relevant to any real-world software implementation. While Joslin is focused on contemporary views, his discussion also suggests a counterexample to recent mapping accounts which hold that genuine implementation requires simple mappings. In this paper, I begin by clarifying the nature of software implementation and disentangling it from closely related phenomena like emulation and simulation. Next, I argue that Joslin overstates the degree of complexity involved in his target cases and that these cases may actually give us reasons to favor simplicity-based criteria over relevant alternatives. Finally, I propose a novel problem for simplicity-based criteria and suggest a tentative solution. (shrink)

The aim of this paper is to offer a formal criterion for physical computation that allows us to objectively distinguish between competing computational interpretations of a physical system. The criterion construes a computational interpretation as an ordered pair of functions mapping (1) states of a physical system to states of an abstract machine, and (2) inputs to this machine to interventions in this physical system. This interpretation must ensure that counterfactuals true of the abstract machine have appropriate counterparts which are (...) true of the physical system. The criterion proposes that rival interpretations be assessed on the basis of simplicity. Simplicity is construed as the Kolmogorov complexity of the interpretation. This approach is closely related to the notion of algorithmic information distance and draws on earlier work on real patterns. (shrink)

John Searle raised the question whether all computation is observer-relative. Indeed, all of the common views of computation, be they semantical, functional or causal rely on mapping something onto the states of a physical or abstract process. In order to effectively execute such a mapping, this process would have to be observed in some way. Thus a probably syntactical analysis by an observer seems to be essential for judging whether a given process implements some computation or not. In order to (...) be able to explore the nature of these observers in a more formal way, we look at the Computing by Observing paradigm, a theoretical model of computation that includes an observer. We argue that the observers used there, monadic transducers, are good candidates for formalizing the way in which the syntax of a process must be analysed in order to judge whether it is computational. (shrink)

Against Maudlin, I argue that machines which merely reproduce a pre-programmed series of changes ought to be classed with Turing’s O-Machines even if they would counterfactually show Turing Machine-like activity. This can be seen on an interventionist picture of computational architectures, on which basic operations are the primitive loci for interventions. While constructions like Maudlin’s Olympia still compute, then, claims about them do not threaten philosophical arguments that depend on Turing Machine architectures and their computational equivalents.

The main goal of my paper is to argue that data compression is a necessary condition for intelligence. One key motivation for this proposal stems from a paradox about intuition and intelligence. For the purposes of this paper, it will be useful to consider playing board games—such as chess and Go—as a paradigm of problem solving and cognition, and computer programs as a model of human cognition. I first describe the basic components of computer programs that play board games, namely (...) value functions and search functions. I then argue that value functions both play the same role as intuition in humans and work in essentially the same way. However, as will become apparent, using an ordinary value function is just a simpler and less accurate form of relying on a database or lookup table. This raises our paradox, since reliance on intuition is usually considered to manifest intelligence, whereas usage of a lookup table is not. I therefore introduce another condition for intelligence that is related to data compression. This proposal allows that even reliance on a perfectly accurate lookup table can be nonintelligent, while retaining the claim that reliance on intuition can be highly intelligent. My account is not just theoretically plausible, but it also captures a crucial empirical constraint. This is because all systems with limited resources that solve complex problems—and hence, all cognitive systems—need to compress data. (shrink)

Computer scientists have provided a distinct justification of Occam’s Razor. Using the probably approximately correct framework, they provide a theorem that they claim demonstrates that we should favor simpler hypotheses. The argument relies on a philosophical interpretation of the theorem. I argue that the standard interpretation of the result in the literature is misguided and that a better reading does not, in fact, support Occam’s Razor at all. To this end, I state and prove a very similar theorem that, if (...) interpreted the same way, would justify the contradictory Anti-Occam’s Razor—the principle that we should favor more complex hypotheses. (shrink)

Given the difficulties of defining “machine” and “think”, Turing proposed to replace the question “Can machines think?” with a proxy: how well can an agent engage in sustained conversation with a human? Though Turing neither described himself as a philosopher nor published much on philosophical matters, his Imitation Game has stood the test of time. Most understood at that time that success would not come easy, but few would have guessed just how difficult engaging in ordinary conversation would turn out (...) to be. Despite the proliferation of language processing tools, we have seen little progress towards doing well at the Imitation Game. Had Turing instead suggested ability at games or even translation as a proxy for intelligence, his paper might have been forgotten. We argue that these and related problems are amenable to mechanical, though sophisticated, formal techniques. Turing appears to have taken care to select sustained, productive conversation and that alone as his proxy. Even simple conversation challenges a machine to engage in the rich practice of human discourse in all its generality and variety. (shrink)

Marr’s seminal distinction between computational, algorithmic, and implementational levels of analysis has inspired research in cognitive science for more than 30 years. According to a widely-used paradigm, the modelling of cognitive processes should mainly operate on the computational level and be targeted at the idealised competence, rather than the actual performance of cognisers in a specific domain. In this paper, we explore how this paradigm can be adopted and revised to understand mathematical problem solving. The computational-level approach applies methods from (...) computational complexity theory and focuses on optimal strategies for completing cognitive tasks. However, human cognitive capacities in mathematical problem solving are essentially characterised by processes that are computationally sub-optimal, because they initially add to the computational complexity of the solutions. Yet, these solutions can be optimal for human cognisers given the acquisition and enactment of mathematical practices. Here we present diagrams and the spatial manipulation of symbols as two examples of problem solving strategies that can be computationally sub-optimal but humanly optimal. These aspects need to be taken into account when analysing competence in mathematical problem solving. Empirically informed considerations on enculturation can help identify, explore, and model the cognitive processes involved in problem solving tasks. The enculturation account of mathematical problem solving strongly suggests that computational-level analyses need to be complemented by considerations on the algorithmic and implementational levels. The emerging research strategy can help develop algorithms that model what we call enculturated cognitive optimality in an empirically plausible and ecologically valid way. (shrink)

Combining physics, mathematics and computer science, quantum computing and its sister discipline of quantum information have developed in the past few decades from visionary ideas to two of the most fascinating areas of quantum theory. General interest and excitement in quantum computing was initially triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially “speed-up” classical computation and factor large numbers into primes far more efficiently than any (known) classical algorithm. Shor’s algorithm was soon followed by several (...) other algorithms that aimed to solve combinatorial and algebraic problems, and in the years since theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor’s algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premise that all known classical worst-case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in attempts to tackle the technological difficulties that prevent the realisation of a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995; Ekert and Jozsa 1996; Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. -/- The philosophical interest in quantum computing is manifold. From a social-historical perspective, quantum computing is a domain where experimentalists find themselves ahead of their fellow theorists. Indeed, quantum mysteries such as entanglement and nonlocality were historically considered a philosophical quibble, until physicists discovered that these mysteries might be harnessed to devise new efficient algorithms. But while the technology for harnessing the power of 50–100 qubits (the basic unit of information in the quantum computer) is now within reach (Preskill 2018), only a handful of quantum algorithms exist, and the question of whether these can truly outperform any conceivable classical alternative is still open. From a more philosophical perspective, advances in quantum computing may yield foundational benefits. For example, it may turn out that the technological capabilities that allow us to isolate quantum systems by shielding them from the effects of decoherence for a period of time long enough to manipulate them will also allow us to make progress in some fundamental problems in the foundations of quantum theory itself. Indeed, the development and the implementation of efficient quantum algorithms may help us understand better the border between classical and quantum physics (Cuffaro 2017, 2018a; cf. Pitowsky 1994, 100), and perhaps even illuminate fundamental concepts such as measurement and causality. Finally, the idea that abstract mathematical concepts such as computability and complexity may not only be translated into physics, but also re-written by physics bears directly on the autonomous character of computer science and the status of its theoretical entities—the so-called “computational kinds”. As such it is also relevant to the long-standing philosophical debate on the relationship between mathematics and the physical world. (shrink)

Cellular automata (henceforth: CA) are discrete, abstract computational systems that have proved useful both as general models of complexity and as more specific representations of non-linear dynamics in a variety of scientific fields. Firstly, CA are (typically) spatially and temporally discrete: they are composed of a finite or denumerable set of homogeneous, simple units, the atoms or cells. At each time unit, the cells instantiate one of a finite set of states. They evolve in parallel at discrete time steps, following (...) state update functions or dynamical transition rules: the update of a cell state obtains by taking into account the states of cells in its local neighborhood (there are, therefore, no actions at a distance). Secondly, CA are abstract, as they can be specified in purely mathematical terms and implemented in physical structures. Thirdly, CA are computational systems: they can compute functions and solve algorithmic problems. Despite functioning in a different way from traditional, Turing machine-like devices, CA with suitable rules can emulate a universal Turing machine, and therefore compute, given Turing's Thesis, anything computable.... (shrink)

How much value can our decisions create? We argue that unless our current understanding of physics is wrong in fairly fundamental ways, there exists an upper limit of value relevant to our decisions. First, due to the speed of light and the definition and conception of economic growth, the limit to economic growth is a restrictive one. Additionally, a related far larger but still finite limit exists for value in a much broader sense due to the physics of information and (...) the ability of physical beings to place value on outcomes. We discuss how this argument can handle lexicographic preferences, probabilities, and the implications for infinite ethics and ethical uncertainty. (shrink)

The philosophy of mind is traditionally concerned with the study of mental processes, language, the representation of knowledge and the relation of the mind shares with the body; computational complexity theory is related to the classification of computationally solvable problems (be it via execution time, storage requirements, etc...). While there are well-established links between computer science in general & the philosophy of mind, many possible solutions to traditional problems in the philosophy of mind have not yet been analyzed from the (...) more specific lens of computational complexity theory. In his paper "Why Philosophers Should Care about Computational Complexity", Scott Aaronson argues that many conventional theories of epistemology & mind implicitly make the presupposition of omniscience (by supposing that knowing base facts means a knower necessarily understands derivative facts) - he proposes that computational complexity theory could explain why this is not the case. In this paper, I argue for a theory of mental representation & epistemology compatible with Aaronson's observations on complexity theory, overcoming that presupposition of omniscience. (shrink)

The notion of an ideal reasoner has several uses in epistemology. Often, ideal reasoners are used as a parameter of (maximum) rationality for finite reasoners (e.g. humans). However, the notion of an ideal reasoner is normally construed in such a high degree of idealization (e.g. infinite/unbounded memory) that this use is unadvised. In this dissertation, I investigate the conditions under which an ideal reasoner may be used as a parameter of rationality for finite reasoners. In addition, I present and justify (...) the research program of computational epistemology, which investigates the parameter of maximum rationality for finite reasoners using computer simulations. (shrink)

As a philosophy of mathematics, strict finitism has been traditionally concerned with the notion of feasibility, defended mostly by appealing to the physicality of mathematical practice. This has led the strict finitists to influence and be influenced by the field of computational complexity theory, under the widely held belief that this branch of mathematics is concerned with the study of what is “feasible in practice”. In this paper, I survey these ideas and contend that, contrary to popular belief, complexity theory (...) is not what the ultrafinitists think it is, and that it does not provide a theoretical framework in which to formalize their ideas —at least not while defending the material grounds for feasibility. I conclude that the subject matter of complexity theory is not proving physical resource bounds in computation, but rather proving the absence of exploitable properties in a search space. (shrink)

I analyze a recent exchange between Adam Elga and Julian Jonker concerning unsharp (or imprecise) credences and decision-making over them. Elga holds that unsharp credences are necessarily irrational; I agree with Jonker's reply that they can be rational as long as the agent switches to a nonlinear valuation. Through the lens of computational complexity theory, I then argue that even though nonlinear valuations can be rational, they come in general at the price of computational intractability, and that this problematizes their (...) use in defining rationality. I conclude that the meaning of "rationality" may be philosophically vague. (shrink)

I propose to investigate the problem of empirical equivalence by performing numerical calculations, simulating hypothetical physical systems, with known evolution rules, which include a robot performing an experiment. The aim of the experiments of the robot is to discover the rules governing the system in which it is simulated. The proposed numerical calculation is actually a thought experiment: I discuss the principles of how the discussion on the empirical equivalence should be performed; the discussion is based on the evaluation of (...) the complexity classes of problems connected to the numerical calculation. Based on this discussion, I prove a sufficient condition for empirical equivalence, which is based on the existence of a transformation belonging to a given complexity class. (shrink)