Induction, Algorithmic Learning Theory, and Philosophy (Logic, Epistemology, and the Unity of Science)

INDUCTION, ALGORITHMIC LEARNING THEORY, AND PHILOSOPHY

LOGIC, EPISTEMOLOGY, AND THE UNITY OF SCIENCE VOLUME 9

Editors Shahid Rahman, University of Lille III, France John Symons, University of Texas at El Paso, U.S.A. Editorial Board Jean Paul van Bendegem, Free University of Brussels, Belgium Johan van Benthem, University of Amsterdam, the Netherlands Jacques Dubucs, University of Paris I-Sorbonne, France Anne Fagot-Largeault, Collège de France, France Bas van Fraassen, Princeton University, U.S.A. Dov Gabbay, King’s College London, U.K. Jaakko Hintikka, Boston University, U.S.A. Karel Lambert, University of California, Irvine, U.S.A. Graham Priest, University of Melbourne, Australia Gabriel Sandu, University of Helsinki, Finland Heinrich Wansing, Technical University Dresden, Germany Timothy Williamson, Oxford University, U.K.

Logic, Epistemology, and the Unity of Science aims to reconsider the question of the unity of science in light of recent developments in logic. At present, no single logical, semantical or methodological framework dominates the philosophy of science. However, the editors of this series believe that formal techniques like, for example, independence friendly logic, dialogical logics, multimodal logics, game theoretic semantics and linear logics, have the potential to cast new light on basic issues in the discussion of the unity of science. This series provides a venue where philosophers and logicians can apply specific technical insights to fundamental philosophical problems. While the series is open to a wide variety of perspectives, including the study and analysis of argumentation and the critical discussion of the relationship between logic and the philosophy of science, the aim is to provide an integrated picture of the scientific enterprise in all its diversity.

Induction, Algorithmic Learning Theory, and Philosophy Edited by

Michèle Friend George Washington University, Washington, D.C., U.S.A.

Norma B. Goethe National University of Cordoba, Cordoba, Argentina

Valentina S. Harizanov George Washington University, Washington, D.C., U.S.A.

A C.I.P. Catalogue record for this book is available from the Library of Congress.

ISBN 978-1-4020-6126-4 (HB) ISBN 978-1-4020-6127-1 (e-book) Published by Springer, P.O. Box 17, 3300 AA Dordrecht, The Netherlands. www.springer.com

Printed on acid-free paper

Cover image: Adaptation of a Persian astrolabe (Brass 1712-13), from the collection of the Museum of the History of Science, Oxford. Reproduced by permission

All Rights Reserved c 2007 Springer  No part of this work may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work.

To Hilary Putnam

Contents

Editors’ Preface

ix

Acknowledgments

xi

Contributors

xii

1 Introduction to the Philosophy and Mathematics of Algorithmic Learning Theory VALENTINA S. HARIZANOV, NORMA B. GOETHE and MICHÈLE FRIEND

1

Part I: Technical Papers 2 Inductive Inference Systems for Learning Classes of Algorithmically Generated Sets and Structures VALENTINA S. HARIZANOV 3 Deduction, Induction, and beyond in Parametric Logic ERIC MARTIN, ARUN SHARMA, and FRANK STEPHAN 4 How Simplicity Helps You Find the Truth without Pointing at It KEVIN T. KELLY 5 Induction over the Continuum IRAJ KALANTARI

27 55

111 145

Part II: Philosophy Papers 6 Logically Reliable Inductive Inference OLIVER SCHULTE vii

157

viii 7 Some Philosophical Concerns about the Confidence in ‘Confident Learning’ MICHÈLE FRIEND

Contents

179

8 How to do Things with an Infinite Regress KEVIN T. KELLY

199

9 Trade-Offs CLARK GLYMOUR

219

10 Two Ways of Thinking About Induction NORMA B. GOETHE

233

11 Between History and Logic BRENDAN LARVOR

259

Index

279

Editors’ Preface

The idea of the present volume emerged in 2002 from a series of talks by Frank Stephan in 2002, and John Case in 2003, on developments of algorithmic learning theory. These talks took place in the Mathematics Department at the George Washington University. Following the talks, Valentina Harizanov and Michèle Friend raised the possibility of an exchange of ideas concerning algorithmic learning theory. In particular, this was to be a mutually beneficial exchange between philosophers, mathematicians and computer scientists. Harizanov and Friend sent out invitations for contributions and invited Norma Goethe to join the editing team. The Dilthey Fellowship of the George Washington University provided resources over the summer of 2003 to enable the editors and some of the contributors to meet in Oviedo (Spain) at the 12th International Congress of Logic, Methodology and Philosophy of Science. The editing work proceeded from there. The idea behind the volume is to rekindle interdisciplinary discussion. Algorithmic learning theory has been around for nearly half a century. The immediate beginnings can be traced back to E.M. Gold’s papers: “Limiting recursion” (1965) and “Language identification in the limit” (1967). However, from a logical point of view, the deeper roots of the learningtheoretic analysis go back to Carnap’s work on inductive logic (1950, 1952). In the context of his goal to construct a system of inductive logic that may take its rightful place beside the formal systems of deductive logic, Carnap asked whether inductive procedures are less regulated by exact rules than deductive procedures. In the Schilpp volume devoted to Carnap’s philosophy (1963), Reichenbach’s student H. Putnam published his seminal article “ ‘Degree of confirmation’ and inductive logic”. According to Carnap’s reply to Putnam (included by Schilpp), the young critic had already advanced his objections in conversation in 1953; the paper was written around 1955–6. ix

x

Editors’ Preface

Relying upon recursion theory, Putnam argued that Carnap’s project of defining a quantitative concept of ‘degree of confirmation’ is completely misguided. Thus, a radically new, alternative perspective on induction saw the light for the first time. In the same year, Putnam published a second article “Probability and confirmation” (1963). Relying on his previous results, Putnam now called Carnap’s goal into question, on the ground that his ‘universal learning machine’ is “a learning device of very low power”. Nonetheless, Putnam concluded optimistically that even if present-day “inductive logics are learning devices of very low power”, in the future, “the development of a powerful mathematical theory of inductive inference, of ‘machines that learn’, and of better mathematical models for human learning may all grow out of this enterprise”. Much of the subsequent work done in the area of algorithmic learning theory grows out of this spirit. Only two years later, Putnam published a third important paper closely related to the new perspective on induction, entitled “Trial and error predicates and a solution to a problem of Mostowski” (1965), which coincidentally appears in the same issue of the Journal of Symbolic Logic as Gold’s first paper. The reaction to the paper from philosophers partly consisted in tempering the imagination of popularisers of the technical work. The popularisers had started making claims about computers learning, and that it followed that computers have a brain, or something approaching free will. This led to speculation about moral obligations towards computers (as autonomous beings with rights). One can see, in retrospect at least, why these speculations needed reining in. The mathematicians and computer scientists have moved on. They have been mapping out the territory of limitations to learning, developing definitions, combining ideas and changing the parameters of the discussion to give an intricate and rigorous understanding of the phenomenon we call “learning”. There has been some serious philosophical work in the area since Putnam and Gold published their papers, for instance, by K.T. Kelly, C. Glymour, O. Schulte, and others. Otherwise, the thread of philosophical reactions to the developments in the mathematical sphere has been much thinner than the potential significance the work warrants. It is time to thicken the thread. Harizanov, Goethe and Friend diagnosed that one of the contributing factors to the lack of communication between the mathematical and philosophical communities has been the plethora of technical terms which have accompanied the development of the mathematics. We address this problem here by giving some definitions explicitly in many of the papers. We hope that this will help bridge the gap between the mathematicians and the philosophers.

Acknowledgments

We should like to acknowledge the funding received from the Dilthey Faculty Fellowship Award of the George Washington University. This is an award whose primary purpose is to stimulate interdisciplinary work that requires crossing disciplines to achieve an integrated perspective and analysis. The funding was enough to spare Michèle Friend and Valentina Harizanov their teaching duties in the summer of 2003. Norma B. Goethe should like to acknowledge the support of her research by a grant of FONCyT (Buenos Aires, Argentina). We should also like to thank the contributors for their valuable and prompt contributions, and all the reviewers. We should especially like to thank John Case for his useful advice and support, especially at the beginning of the project. We should like to thank Sarah Pingrey for help with the final proofreading of several papers, and for her valuable assistance with TEX and assembling the volume. Sarah Pingrey was partially supported by Harizanov’s George Washington University UFF grant. We should also like to thank Ed Canavan for his continuing support. Finally, Harizanov is most grateful to her daughters, Sofija and Kalina, for their constant encouragement and endless inspiration. Washington, DC Cordoba, R. A. June 2006

V. S. H., M. F. N. B. G.

xi

Contributors

Michèle Friend, Department of Philosophy, George Washington University, Washingon DC 20052, USA, [email protected] Clark Glymour, Department of Philosophy, Carnegie Mellon University, Pittsburgh, PA 15213, USA, [email protected] Norma B. Goethe, School of Philosophy, National University of Cordoba, 5000 Cordoba, Argentina, [email protected] Valentina Harizanov, Department of Mathematics, George Washington University, Washington DC 20052, USA, [email protected] Iraj Kalantari, Department of Mathematics, Western Illinois University, Macomb, IL 61455, USA, [email protected] Kevin T. Kelly, Department of Philosophy, Carnegie Mellon University, Pittsburg, PA 15213, USA, [email protected] Brendan Larvor, School of Humanities, University of Hertfordshire, Hatfield AL10 9AB, Hertfordshire, United Kingdom, [email protected] Eric Martin, School of Computer Science and Engineering, National ICT Australia, UNSW Sydney, NSW 2052, Australia, [email protected] Oliver Schulte, Department of Philosophy and School of Computing Science, Simon Fraser University, Burnaby, B.C. V5A 1S6, Canada, [email protected] xii

Contributors

xiii

Arun Sharma, Division of Research and Commercialisation, Queensland University of Technology, 2 George Street, GPO Box 2434, Brisbane QLD 4001, Australia, [email protected] Frank Stephan, Department of Mathematics and School of Computing, National University of Singapore, Singapore 117543, [email protected]