永恒的图灵：20位科学家对图灵思想的解构与超越英文版.pdf

发布时间：2022-06-06 发布人：admin 分类：说明书资料大小：14.34M 资料格式：pdf 举报版权申诉

heaven_sent-11249636-4744302543313930077.pdf-第1页.png

第1页 / 共397页

heaven_sent-11249636-4744302543313930077.pdf-第2页.png

第2页 / 共397页

heaven_sent-11249636-4744302543313930077.pdf-第3页.png

第3页 / 共397页

heaven_sent-11249636-4744302543313930077.pdf-第4页.png

第4页 / 共397页

heaven_sent-11249636-4744302543313930077.pdf-第5页.png

第5页 / 共397页

heaven_sent-11249636-4744302543313930077.pdf-第6页.png

第6页 / 共397页

heaven_sent-11249636-4744302543313930077.pdf-第7页.png

第7页 / 共397页

heaven_sent-11249636-4744302543313930077.pdf-第8页.png

第8页 / 共397页

01.0_pp_i_iv_Frontmatter

02.0_pp_v_viii_Contents

03.0_pp_ix_x_Contributors

04.0_pp_xi_xii_Preface

05.0_pp_xiii_xviii_Introduction

06.0_pp_1_3_Inside_Our_Computable_World_and_the_Mathematics_of_Universality

06.1_pp_4_19_Algorithms_Equations_and_Logic

06.2_pp_20_33_The_Forgotten_Turing

06.3_pp_34_52_Turing_and_the_Primes

06.4_pp_53_77_Cryptography_and_Computation_after_Turing

06.5_pp_78_89_Alan_Turing_and_Enigmatic_Statistics

07.0_pp_90_91_The_Computation_of_Processes_and_Not_Computing_the_Brain

07.1_pp_92_105_What_Alan_Turing_Might_Have_Discovered

07.2_pp_106_116_Designed_versus_Intrinsic_Computation

07.3_pp_117_128_Dull_Rigid_Human_meets_Ace_Mechanical_Translator

08.0_pp_129_130_The_Reverse_Engineering_Road_to_Computing_Life

08.1_pp_131_143_Turings_Theory_of_Developmental_Pattern_Formation

08.2_pp_144_159_Walking_the_Tightrope_The_Dilemma_of_Hierarchical_Instabilities_in_Turings_Morphogenesis

09.0_pp_160_162_Biology_Mind_and_the_Outer_Reaches_of_Quantum_Computation

09.1_pp_163_192_Answering_Descartes_Beyond_Turing

09.2_pp_193_296_The_Ghost_in_the_Quantum_Turing_Machine

10.0_pp_297_299_Oracles_Infinitary_Computation_and_the_Physics_of_the_Mind

10.1_pp_300_334_Turings_Oracle_From_Absolute_to_Relative_Computability_and_Back

10.2_pp_335_360_Turing_Transcendent_Beyond_the_Event_Horizon

10.3_pp_361_378_On_Attempting_to_Model_the_Mathematical_Mind

11.0_pp_379_379_Afterword

THE ONCE AND FUTURE TURING: COMPUTING THE WORLD Alan Turing (1912–1954) made seminal contributions to mathematical logic, computation, computer science, artiﬁcial intelligence, cryptography and theoretical biology. In this volume, outstanding scientiﬁc thinkers take a fresh look at the great range of Turing’s contributions, on how the subjects have developed since his time, and how they might develop still further. These specially commissioned essays will provoke and engross the reader who wishes to understand better the lasting signiﬁcance of one of the twentieth century’s deepest thinkers. Until his death in 2015, S . B A R R Y C O O P E R was Professor of Mathematical Logic at the University of Leeds. He was both a leading ﬁgure in the theory of Turing computability, and a noted advocate of multidisciplinary research, especially in connection with the theoretical and practical limits of the computable. As President of Computability in Europe, he was responsible for many international conferences. He chaired the Turing Centenary Committee, and edited the prize-winning critical edition of Turing’s publications: Alan Turing – His Work and Impact. A N D R E W H O D G E S is a Senior Research Fellow at Institute, University of Oxford. His main research is in fundamental physics, as a colleague of Roger Penrose, but he is also the biographer of Alan Turing. His book Alan Turing: The Enigma (1983) has reached a wide audience and has inspired works of drama, music, art and ﬁlm. the Mathematical

THE ONCE AND FUTURE TURING Computing the World S. BARRY COOPER University of Leeds ANDREW HODGES University of Oxford

University Printing House, Cambridge CB2 8BS, United Kingdom Cambridge University Press is part of the University of Cambridge. It furthers the University’s mission by disseminating knowledge in the pursuit of education, learning and research at the highest international levels of excellence. www.cambridge.org Information on this title: www.cambridge.org/9781107010833 c Cambridge University Press 2016 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 2016 Printed in the United Kingdom by Clays, St Ives plc A catalogue record for this publication is available from the British Library ISBN 978-1-107-01083-3 Hardback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

Contents Contributors Preface Introduction Part One: Inside Our Computable World, and the Mathematics of Uni- page ix xi xiii 1 2 3 4 versality Algorithms, Equations, and Logic Martin Davis References The Forgotten Turing J.M.E. Hyland References Turing and the Primes Andrew R. Booker References Cryptography and Computation after Turing Ueli Maurer 4.1 4.2 Cryptography 4.3 Computation 4.4 4.5 Discrete logarithms and other computational problems on The Difﬁe–Hellman key-agreement protocol Introduction groups 4.6 Discrete logarithm algorithms 4.7 Abstract models of computation 4.8 4.9 Conclusions References Proving security: lower bounds for complexity v 1 4 18 20 32 34 52 53 54 55 57 58 62 63 66 68 75 76

vi 5 Introduction Contents Alan Turing and Enigmatic Statistics Kanti V. Mardia and S. Barry Cooper 5.1 5.2 Weight of evidence and empirical Bayes 5.3 Alignment of letters 5.4 Release by GCHQ of two key Turing reports 5.5 5.6 Morphogenesis, statistics, and Alan Turing’s AI References Turing’s statistics in context Part Two: The Computation of Processes, and Not Computing the Brain 6 What Alan Turing Might Have Discovered Stephen Wolfram References Designed versus Intrinsic Computation Christof Teuscher 7.1 7.2 7.3 7.4 7.5 Outlook References Dull Rigid Human meets Ace Mechanical Translator Douglas Richard Hofstadter Top-down versus bottom-up design Intrinsic versus designed computation Turing’s bottom-up computing approach From intrinsic to designed computation 7 8 Part Three: The Reverse Engineering Road to Computing Life 9 Turing’s Theory of Developmental Pattern Formation Philip K. Maini, Thomas E. Woolley, Eamonn A. Gaffney and Ruth E. Baker 9.1 Introduction Some developmental applications 9.2 9.3 Extending Turing 9.4 Critiquing Turing 9.5 References The impact of Turing 10 Walking the Tightrope: The Dilemma of Hierarchical Instabilities in Turing’s Morphogenesis Richard Gordon References 78 78 80 81 83 84 87 88 90 92 105 106 106 107 108 111 113 115 117 129 131 131 135 137 138 141 142 144 155

11 12 tation Answering Descartes: Beyond Turing Stuart Kauffman References The Ghost in the Quantum Turing Machine Scott Aaronson 12.1 Introduction 12.2 FAQ 12.3 Knightian uncertainty and physics 12.4 Freedom from the inside out 12.5 Further objections 12.6 Comparison with Penrose’s views 12.7 ‘Application’ to Boltzmann brains 12.8 Indexicality and freebits 12.9 Is the freebit picture falsiﬁable? 12.10 Conclusions 12A Appendix: Deﬁning ‘freedom’ 12B Appendix: Prediction and Kolmogorov complexity 12C Appendix: Knightian quantum states References 195 202 226 242 249 261 267 269 273 275 280 287 291 292 Part Five: Oracles, Inﬁnitary Computation, and the Physics of the Mind 297 13 Turing’s ‘Oracle’: From Absolute to Relative Computability and Back Solomon Feferman 13.1 Introduction 13.2 ‘Absolute’ effective computability 13.3 Relative effective computability over the natural numbers 13.4 Uniform relative computability over the natural numbers 13.5 Generalized recursion theory 13.6 The role of notions of relative computability in actual vii 160 163 189 193 300 300 301 306 313 316 323 330 331 335 335 341 Part Four: Biology, Mind, and the Outer Reaches of Quantum Compu- Contents computation 14 Postscript References Turing Transcendent: Beyond the Event Horizon P.D. Welch 14.1 The beginning 14.2 Limit decidable

viii 15 Contents 14.3 Malament–Hogarth spacetimes 14.4 Inﬁnite ordinals: beyond arithmetical 14.5 Returning to MH spacetimes 14.6 The ℵ0-mind 14.7 Inﬁnite-time Turing machines 14.8 Register machines and other generalisations 14.9 Conclusions References On Attempting to Model the Mathematical Mind Roger Penrose 15.1 Turing’s ordinal logics 15.2 Mathematical trust 15.3 Physical processes underlying mathematical understanding? 15.4 Π-sentences 15.5 Cautious oracles 15.6 The operation of cautious-oracle devices 15.7 A G¨odel-type theorem for cautious-oracle devices 15.8 Physical implications? References Afterword 342 344 348 349 351 356 359 360 361 361 363 365 367 369 371 374 375 377 379

分享到：

赞收藏

资料库

永恒的图灵：20位科学家对图灵思想的解构与超越英文版.pdf

相关推荐

安全技术

热门标签

最新资料