Between Calculability and Non-Calculability. Issues of Calculability and Predictability in the Physics of Complex Systems. The ability to predict has been a very important qualifier of what constitutes scientific knowledge, ever since the successes of Babylonian and Greek astronomy. More recent is the general appreciation of the fact that in the presence of deterministic chaos, predictability is severely limited (the so-called ‘butterfly effect’): Nearby trajectories diverge during time evolution; small errors typically grow exponentially with time. The system obeys deterministic laws (...) and still is unpredictable, seemingly a paradox for the traditional viewpoint of Laplacian determinisms. With the concept of deterministic chaos the epistemological issue about an adequate understanding of predictability is no longer just a mere philosophical topic. Physicists on the one hand recognize the limits of (long term) predictability, computability and even of scientific knowledge, on the other hand they work on concepts for extending the horizon of predictability. It is shown in this paper that physics of complex systems is useful to clarify the jungle of different meanings of the terms ‘predictability’ and ‘computability’ — also with philosophical implications for understanding science and nature. Today, from the physical point of view, the relevance of the concepts of predictability seems to be underestimated by philosophers as a mere methodological topic. In the paper I analyse the importance of predictability and computability in physics of complex systems. I show a way how to cope with problems of unpredictability and noncomputability. Nine different concepts of predictability and computability (i.e. open solution, sensitivity/chaos, redundancy/chance) are presented, compared and evaluated. (shrink)

This article focuses on emergence in social systems. The author begins by proposing a new tool to explore the mechanisms of social emergence: multi agent–based computer simulation. He then draws on philosophy of mind to develop an account of social emergence that raises potential problems for the methodological individualism of both social mechanism and of multi agent simulation. He then draws on various complexity concepts to propose a set of criteria whereby one can determine whether a given social mechanism generates (...) emergent properties, in the sense that their explanation cannot be reduced to a mechanistic account of individuals and their interactions. This combined account helps to resolve the competing claims of methodological individualists and social realists. The author’s conclusion is that the scope of mechanistic explanation may be limited due to the extreme complexity of many social systems. Key Words: emergence • mechanism • computer simulation • methodological individualism • social realism. (shrink)

1. The Physical Church-Turing Thesis. Physicists often interpret the Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system . . . (...) No physically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. (shrink)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

Some have suggested that certain classical physical systems have undecidable long-term behavior, without specifying an appropriate notion of decidability over the reals. We introduce such a notion, decidability in (or d- ) for any measure , which is particularly appropriate for physics and in some ways more intuitive than Ko's (1991) recursive approximability (r.a.). For Lebesgue measure , d- implies r.a. Sets with positive -measure that are sufficiently "riddled" with holes are never d- but are often r.a. This explicates Sommerer (...) and Ott's (1996) claim of uncomputable behavior in a system with riddled basins of attraction. Furthermore, it clarifies speculations that the stability of the solar system (and similar systems) may be undecidable, for the invariant tori established by KAM theory form sets that are not d-. (shrink)

This article focuses on emergence in social systems. The author begins by proposing a new tool to explore the mechanisms of social emergence: multi agent–based computer simulation. He then draws on philosophy of mind to develop an account of social emergence that raises potential problems for the methodological individualism of both social mechanism and of multi agent simulation. He then draws on various complexity concepts to propose a set of criteria whereby one can determine whether a given social mechanism generates (...) emergent properties, in the sense that their explanation cannot be reduced to a mechanistic account of individuals and their interactions. This combined account helps to resolve the competing claims of methodological individualists and social realists. The author’s conclusion is that the scope of mechanistic explanation may be limited due to the extreme complexity of many social systems. (shrink)

The results of Cubitt et al. on the spectral gap problem add a new chapter to the issue of undecidability in physics, as they show that it is impossible to decide whether the Hamiltonian of a quantum many-body system is gapped or gapless. This implies, amongst other things, that a reductionist viewpoint would be untenable. In this paper, we examine their proof and a few philosophical implications, in particular ones regarding models and limitative results. In more detail, we examine the (...) way these theorems model many-body quantum systems, and we question what, if anything, is the physical counterpart of the models used by Cubitt et al. We argue that these models are non-representational and that, even if they are so artificial that it is hard to imagine a physical system arising from them, they nonetheless offer an opportunity to learn about the world and the relation between mathematics and reality. On this basis, we draw the conclusion that their results do not undermine the reductionist viewpoint in a strong sense but leave the question open in a weak sense. (shrink)

I discuss the philosophical implications that the rising new science of quantum computing may have on the philosophy of computer science. While quantum algorithms leave the notion of Turing-Computability intact, they may re-describe the abstract space of computational complexity theory hence militate against the autonomous character of some of the concepts and categories of computer science.

A survey of the field of hypercomputation, including discussion of a variety of objections.

Top-down synthetic biology makes partly synthetic cells by redesigning simple natural forms of life, and bottom-up synthetic biology aims to make fully synthetic cells using only entirely nonliving components. Within synthetic biology the notions of complexity and emergence are quite controversial, but the imprecision of key notions makes the discussion inconclusive. I employ a precise notion of weak emergent property, which is a robust characteristic of the behavior of complex bottom-up causal webs, where a complex causal web is one that (...) is incompressible and its behavior cannot be derived except by crawling through all of the gory details of the interactions in the web. The central thesis of this article is that synthetic biology centrally is the activity of engineering the desired weak emergent properties of synthetic cells. Synthetic biology has many different ways to engineer desired weak emergent properties of synthetic cells, including Edisonian trial and error, standardized parts, refactoring, and reprogramming synthetic genomes. The article ends by noting two philosophical consequences of engineering weak emergence. One is epistemological: synthesis is crucial for discovering weak emergent properties. The other is metaphysical: simple life forms are nothing but complex chemical mechanisms. (shrink)

Weak emergence is the view that a system’s macro properties can be explained by its micro properties but only in an especially complicated way. This paper explains a version of weak emergence based on the notion of explanatory incompressibility and “crawling the causal web.” Then it examines three reasons why weak emergence might be thought to be just in the mind. The first reason is based on contrasting mere epistemological emergence with a form of ontological emergence that involves irreducible downward (...) causation. The second reason is based on the idea that attributions of emergence are always a reflection of our ignorance of non-emergent explanations. The third reason is based on the charge that complex explanations are anthropocentric. Rather than being just in the mind, weak emergence is seen to involve a distinctive kind of complex, macro-pattern in the mind-independent objective micro-causal structure that exists in nature. The paper ends by addressing two further questions. One concerns whether weak emergence applies only or mainly to computer simulations and computational systems. The other concerns the respect in which weak emergence is dynamic rather than static. (shrink)

We analyze the effects of the introduction of new mathematical tools on an old branch of physics by focusing on lattice fluids, which are cellular automata -based hydrodynamical models. We examine the nature of these discrete models, the type of novelty they bring about within scientific practice and the role they play in the field of fluid dynamics. We critically analyze Rohrlich's, Fox Keller's and Hughes' claims about CA-based models. We distinguish between different senses of the predicates “phenomenological” and “theoretical” (...) for scientific models and argue that it is erroneous to conclude, as they do, that CA-based models are necessarily phenomenological in any sense of the term. We conversely claim that CA-based models of fluids, though at first sight blatantly misrepresenting fluids, are in fact conservative as far as the basic laws of statistical physics are concerned and not less theoretical than more traditional models in the field. Based on our case-study, we propose a general discussion of the prospect of CA for modeling in physics. We finally emphasize that lattice fluids are not just exotic oddities but do bring about new advantages in the investigation of fluids' behavior. (shrink)

In this paper I argue that whether or not a computer can be built that passes the Turing test is a central question in the philosophy of mind. Then I show that the possibility of building such a computer depends on open questions in the philosophy of computer science: the physical Church-Turing thesis and the extended Church-Turing thesis. I use the link between the issues identified in philosophy of mind and philosophy of computer science to respond to a prominent argument (...) against the possibility of building a machine that passes the Turing test. Finally, I respond to objections against the proposed link between questions in the philosophy of mind and philosophy of computer science. (shrink)

The enduring problem of free will has defied resolution across centuries. There is reason to believe that novel factors must be integrated into the analysis to make progress. Within the current physicalist framework, these factors encompass emergence and information theory, in the context of constraints imposed by physical limits on the representation of information. Furthermore the common, but vague, characterization of free will as 'being able to act differently' is rephrased into an explicatum more suitable for formal analysis. It is (...) argued that the mind is an ontologically open system; a causal high-level system, the dynamics of which cannot be reduced to the states of its associated low-level neural systems, not even if it is rendered physically closed. A positive answer to the question of free will for conscious agents is subsequently outlined. (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)

The problem of free will has persistently resisted a solution throughout centuries. There is reason to believe that new elements need to be introduced into the analysis in order to make progress. In the present physicalist approach, these elements are emergence and information theory in relation to universal limits set by quantum physics. Furthermore the common, but vague, characterization of free will as "being able to act differently" is, in the spirit of Carnap, rephrased into an explicatum more suitable for (...) formal analysis. It is argued that the mind is an ontologically open system; a causal high-level system, the future of which cannot be reduced to the states of its associated low-level neural systems, not even if it is rendered physically closed. A positive answer to the question of free will is subsequently outlined. (shrink)

We examine the question of whether scientific theories can ever be complete. For two closely related reasons, we will argue that they cannot. The first reason is the inability to determine what are “valid empirical observations”, a result that is based on a self-reference Gödel/Tarski-like proof. The second reason is the existence of “meta-empirical” evidence of the inherent incompleteness of observations. These reasons, along with theoretical incompleteness, are intimately connected to the notion of belief and to theses within the philosophy (...) of science: the Quine-Duhem (and underdetermination) thesis and the observational/theoretical distinction failure. Some puzzling aspects of the philosophical theses will become clearer in light of these connections. Other results that follow are: no absolute measure of the informational content of empirical data, no absolute measure of the entropy of physical systems, and no complete computer simulation of the natural world are possible. The connections with the mathematical theorems of Gödel and Tarski reveal the existence of other connections between scientific and mathematical incompleteness: computational irreducibility, complexity, infinity, arbitrariness and self-reference. Finally, suggestions will be offered of where a more rigorous (or formal) “proof” of scientific incompleteness can be found. (shrink)

This article tells the story of Ed Fredkin, a pilot, programmer, engineer, hardware designer and entrepreneur, whose work inside and outside academia has influenced major developments in computer science and in the foundations of theoretical physics for the past fifty years.