A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving. A number of "no free lunch" (NFL) theorems are presented which establish that for any algorithm, any elevated performance over one class of problems is offset by performance over another class. These theorems result in a geometric interpretation of what it means for an algorithm to be well suited to an optimization problem. Applications of the NFL theorems to information-theoretic aspects of optimization (...) and benchmark measures of performance are also presented. Other issues addressed include time-varying optimization problems and a priori "head-to-head" minimax distinctions between optimization algorithms, distinctions that result despite the NFL theorems’ enforcing of a type of uniformity over all algorithms. (shrink)

Scientific discourse is rife with passages that appear to be ordinary descriptions of systems of interest in a particular discipline. Equally, the pages of textbooks and journals are filled with discussions of the properties and the behavior of those systems. Students of mechanics investigate at length the dynamical properties of a system consisting of two or three spinning spheres with homogenous mass distributions gravitationally interacting only with each other. Population biologists study the evolution of one species procreating at a constant (...) rate in an isolated ecosystem. And when studying the exchange of goods, economists consider a situation in which there are only two goods, two perfectly rational agents, no restrictions on available information, no transaction costs, no money, and dealings are done immediately. Their surface structure notwithstanding, no competent scientist would mistake descriptions of such systems as descriptions of an actual system: we know very well that there are no such systems. These descriptions are descriptions of a model-system, and scientists use model-systems to represent parts or aspects of the world they are interested in. Following common practice, I refer to those parts or aspects as target-systems. What are we to make of this? Is discourse about such models merely a picturesque and ultimately dispensable façon de parler? This was the view of some early twentieth century philosophers. Duhem (1906) famously guarded against confusing model building with scientific theorizing and argued that model building has no real place in science, beyond a minor heuristic role. The aim of science was, instead, to construct theories, with theories understood as classificatory or representative structures systematically presented and formulated in precise symbolic.. (shrink)

This volume examines the limitations of mathematical logic and proposes a new approach to logic intended to overcome them. To this end, the book compares mathematical logic with earlier views of logic, both in the ancient and in the modern age, including those of Plato, Aristotle, Bacon, Descartes, Leibniz, and Kant. From the comparison it is apparent that a basic limitation of mathematical logic is that it narrows down the scope of logic confining it to the study of deduction, without (...) providing tools for discovering anything new. As a result, mathematical logic has had little impact on scientific practice. Therefore, this volume proposes a view of logic according to which logic is intended, first of all, to provide rules of discovery, that is, non-deductive rules for finding hypotheses to solve problems. This is essential if logic is to play any relevant role in mathematics, science and even philosophy. To comply with this view of logic, this volume formulates several rules of discovery, such as induction, analogy, generalization, specialization, metaphor, metonymy, definition, and diagrams. A logic based on such rules is basically a logic of discovery, and involves a new view of the relation of logic to evolution, language, reason, method and knowledge, particularly mathematical knowledge. It also involves a new view of the relation of philosophy to knowledge. This book puts forward such new views, trying to open again many doors that the founding fathers of mathematical logic had closed historically. (shrink)

Many scientific models lack an established representation relation to actual targets and instead refer to merely possible processes, background conditions, and results. This article shows how such models can be appraised. On the basis of the discussion of how-possibly explanations, five types of learning opportunities are distinguished. For each of these types, an example—from economics, biology, psychology, and sociology—is discussed. Contexts and purposes are identified in which the use of a model offers a genuine opportunity to learn. These learning opportunities (...) offer novel justifications for modeling practices that fall between the cracks of standard representationalist appraisals of models. (shrink)

This accessible book gives a new, detailed and elementary explanation of the Gödel incompleteness theorems and presents the Chaitin results and their relation to the da Costa-Doria results, which are given in full, but with no ...

This chapter explores some fundamental consequences of the correspondence between physical process and computations. Most physical questions may be answerable only through irreducible amounts of computation. Those that concern idealized limits of infinite time, volume, or numerical precision can require arbitrarily long computations, and so be considered formally undecidable. The behavior of a physical system may always be calculated by simulating explicitly each step in its evolution. Much of theoretical physics has, however, been concerned with devising shorter methods of calculation (...) that reproduce the outcome without tracing each step. Computational irreducibility is common among the systems investigated in mathematics and computation theory, but it may well be the exception rather than the rule, since most physical questions may be answerable only through irreducible amounts of computation. (shrink)

Many scientific models are non-representational in that they refer to merely possible processes, background conditions and results. The paper shows how such non-representational models can be appraised, beyond the weak role that they might play as heuristic tools. Using conceptual distinctions from the discussion of how-possibly explanations, six types of models are distinguished by their modal qualities of their background conditions, model processes and model results. For each of these types, an actual model example – drawn from economics, biology, psychology (...) or sociology – is discussed. For each case, contexts and purposes are identified in which the use of such a model offers a genuine opportunity to learn – i.e. justifies changing one’s confidence in a hypothesis about the world. These cases then offer novel justifications for modelling practices that fall between the cracks of standard representational accounts of models. (shrink)