Alan Turing. His work and impact

Front Cover......Page 1
Alan Turing: His Work and Impact......Page 4
Copyright......Page 5
List of Contributors......Page 6
Introduction......Page 12
Table of Contents......Page 14
Part I: How Do We Compute? What Can We Prove?......Page 24
A Comment on Newman\'s Biographical Memoir......Page 26
Alan Mathison Turing......Page 28
\'1. Computing machines......Page 30
3. Computing machines......Page 33
4. Chemical theory of morphogenesis......Page 34
Bibliography......Page 35
Alan and I......Page 36
1. Computing machines......Page 39
Computing machines......Page 40
3. Examples of computing machines......Page 41
4. Abbreviated tables......Page 43
Further examples......Page 44
5. Enumeration of computable sequences......Page 46
6. The universal computing machine......Page 47
7. Detailed description of the universal machine......Page 48
Subsidiary skeleton table......Page 49
8. Application of the diagonal process......Page 51
9. The extent of the computable numbers......Page 53
10. Examples of large classes of numbers which are computable......Page 56
Computable convergence......Page 58
11. Application to the Entscheidungsproblem......Page 60
Computability and effective calculability......Page 63
On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction......Page 65
The Importance of Universal Computation......Page 67
The Entscheidungsproblem......Page 72
1. Church\'s Proof......Page 73
3. The should-have-been Gödel–Kleene Proof......Page 74
References......Page 75
2. Why Do We Compute?......Page 76
Problem 2......Page 77
3. What Do We Compute?......Page 78
References......Page 79
1. Introduction......Page 80
2. Formal definition of the Turing machine......Page 81
3. Computability thesis and the universal Turing machine......Page 82
4. Undecidability of the halting problem......Page 83
5. Complexity of computations......Page 84
6. Importance of the Turing machine......Page 85
From the Halting Problem to the Halting Probability\r......Page 86
2. Defining the effectively calculable functions......Page 88
3. Why Turing and not Church?......Page 89
4. Why Michelangelo and not Donatello?......Page 90
5.2. Composition and balance......Page 91
References......Page 92
2. The object......Page 94
2.1. Hardware layout......Page 95
3.1. Universal Turing machines and Jones–Matiyasevich-masking......Page 96
3.2. On the early history of register machines......Page 97
5. State machine......Page 98
References......Page 99
Reflections on Wittgenstein\'s Debates with Turing During his Lectures on the Foundations of Mathematics\r......Page 100
References......Page 102
1. Introduction......Page 103
2.2. Red-green Turing machines......Page 104
3. Significance of the result......Page 105
References......Page 107
Turing\'s Approach to Modelling States of Mind......Page 108
Acknowledgements......Page 113
References......Page 114
2. The Turing machine: processes and computation......Page 115
3. The neural Turing machine......Page 116
4. Conscious cognition: discrete temporal frames......Page 117
5. Conscious cognition: mind states......Page 118
References......Page 119
2. Virtuality......Page 120
3. Causation and computation......Page 121
4. Causation in RVMs......Page 122
5. Implementable but irreducible......Page 123
6. Implications......Page 124
NOT......Page 125
1. Introduction......Page 128
3. Resources......Page 129
4. Halting time......Page 130
References......Page 131
Toward the Unknown Region: On Computing Infinite Numbers......Page 132
References......Page 138
Church\'s Review of Computable Numbers......Page 140
Reference......Page 141
2.1. Features from lambda calculus......Page 144
2.2. Features beyond lambda calculus......Page 145
3. Types......Page 146
4. Input/output......Page 147
6. History and perspective......Page 148
References......Page 149
1. Definition of λ-K-definability......Page 150
2. Abbreviations......Page 152
3. Mechanical conversion......Page 154
4. Computability of λ-K-definable functions......Page 157
5. Recursiveness of computable functions.......Page 159
1.1. Lambda terms, reduction, and conversion......Page 162
1.2. Fixed points......Page 163
2.2. The proof of weak normalisation......Page 164
References......Page 166
The p-Function in λ-K-Conversion......Page 167
Turing\'s Thesis: Ordinal Logics and Oracle Computability......Page 168
1. From Cambridge to Princeton......Page 169
2. Turing in Princeton......Page 170
3. The thesis: ordinal logics......Page 171
4. Ordinal logics redux......Page 172
References......Page 173
Systems of Logic Based on Ordinals......Page 174
1. The calculus of conversion. Gödel representations.......Page 175
2. Effective calculability. Abbreviation of treatment.......Page 177
3. Number-theoretic theorems.......Page 179
4. A type of problem which is not number-theoretic.......Page 182
6. Logic formulae.......Page 183
7. Ordinals.......Page 185
8. Ordinal logics.......Page 193
Definition of completeness of an ordinal logic......Page 199
Invariance of ordinal logics......Page 200
Incompleteness theorems.......Page 203
11. The purpose of ordinal logics.......Page 209
12. Gentzen type ordinal logics.......Page 211
Index of definitions.......Page 218
Bibliography......Page 220
1. Realisability......Page 221
2. Heyting arithmetic in higher types......Page 222
3. Realisability relative to an oracle......Page 223
References......Page 224
Truth and Turing......Page 225
1. Turing\'s oracles......Page 229
2. Value indefiniteness and the Kochen–Specker Theorem......Page 230
3. An example of a quantum random oracle......Page 231
References......Page 232
Preface......Page 234
1. The nested-type system for a finite universe......Page 236
2. Formal account of the nested-type system......Page 241
3. Equivalence with Church\'s system......Page 243
4. Relaxation of type notation......Page 245
Turing\'s dots......Page 250
General bracketing theory......Page 252
Second form of rule......Page 253
Equivalence theorem......Page 254
Jutaxposition and omitted points......Page 256
Application to Church\'s system......Page 257
Examples......Page 258
Computation, Mathematical Notation and Linguistics......Page 262
References......Page 267
The Reform of Mathematical Notation and Phraseology......Page 268
Free and bound variables. Deduction theorem. Constants and parameters......Page 269
Theory of types and domains of definition......Page 270
Discussion of the system and application to normal mathematics......Page 271
Turing, Wittgenstein and Types: Philosophical Aspects of Turing\'s \'The Reform of Mathematical Notation and Phraseology\' (1944–5)......Page 273
References......Page 276
Part II: Hiding and Unhiding Information: Cryptology, Complexity and Number Theory......Page 278
1. Introduction......Page 280
2. The central limit theorem......Page 281
3.1. Basic structure of the paper......Page 282
3.2. The Quasi–necessary conditions......Page 283
3.3. The sufficient conditions......Page 284
References......Page 285
Turing\'s \'Preface\' (1935) to \'On the Gaussian error function\'......Page 287
2. Recollection of some basics......Page 288
3. On Turing\'s computations of the zeta function......Page 290
4. On Turing\'s early work with zeta......Page 292
5. A return to basics......Page 294
6. Turing\'s skepticism about the RH......Page 300
References......Page 301
A Few Comments About  Turing\'s Method......Page 302
References......Page 306
Introduction......Page 307
2. The approximate functional equation......Page 308
3. Principles of the calculations......Page 311
4. Evaluation of N(t)......Page 312
1. Essentials of the Manchester computer......Page 319
2. Outline of calculation method......Page 320
References......Page 322
2. Outline of the method......Page 323
3. Formal preliminaries......Page 324
4. Results with a special kernel......Page 327
5. The Diophantine approximation......Page 334
6. Computational Diophantine approximation......Page 337
7. Case where the Riemann hypothesis is … false (positively?)......Page 338
References......Page 343
Turing\'s Small Gem......Page 344
1. Substitution puzzles......Page 355
2. Puzzles: analyzed......Page 357
3. Substitution puzzles: generalised......Page 359
References......Page 361
Turing on \'Solvable and Unsolvable Problems\' and Simon on \'Human Problem Solving\'......Page 362
References......Page 364
Finding the Halting Problem and the Halting Probability\rin Traditional Mathematics......Page 366
Introduction to the mathematics\r......Page 367
2. The word problem......Page 368
3. Computing machines......Page 369
4. The semi-group ?......Page 371
5. Sufficiency in Theorem 1......Page 373
6. The necessity in Theorem 1.......Page 375
References......Page 380
Introduction......Page 382
Technique for investigating any particular upright U......Page 383
U with no beetle......Page 386
U with a beetle......Page 387
The detailed search......Page 388
Case of symmetric and alternating groups......Page 399
1. Introduction......Page 400
2. Rounding-off errors in matrix processes......Page 401
3. Turing and the matrix condition number......Page 402
4. Turing\'s evolving perspective on computing over the reals......Page 404
5. Postscript: who invented the condition number?......Page 405
References......Page 407
1. Measure of work in a process......Page 408
Theorem on Triangular Resolution.......Page 409
4. The elimination method......Page 410
5. Jordan\'s method for inversion......Page 412
6. Other methods involving the triangular resolution......Page 413
7. Measure of the magnitude of a matrix......Page 415
8. Ill-conditioned matrices and equations......Page 416
10. General remarks on error estimates: the error in a reputed inverse......Page 418
11. Rounding-off errors in Jordan\'s method......Page 419
12. Errors in the Gauss elimination process......Page 423
13. Errors in the unsymmetrical Choleski method......Page 424
References......Page 425
Computable Numbers and Normal Numbers......Page 426
References......Page 427
A Note on Normal Numbers......Page 428
Turing\'s Note on Normal Numbers......Page 431
References......Page 434
2. Turing declassified......Page 436
4. Rebuilding on old foundations......Page 437
5. Inventing modern tools......Page 438
References......Page 439
1. Excerpt 1......Page 440
2. Excerpt 2......Page 442
3. Excerpt 3......Page 444
4. Excerpt 4......Page 445
5. Excerpt 5......Page 446
6. Excerpt 6......Page 447
1. Letter pairs......Page 449
2. Letter loops......Page 452
3. The Bombe......Page 453
4. The Diagonal Board......Page 454
1. Why did the Germans overlook Enigma weaknesses?......Page 455
2. Too many cooks spoiled the broth......Page 459
References......Page 460
The Secrets of Hanslope Park 1944–1945......Page 462
Suggested Form of Key......Page 463
Alan Turing and Voice Encryption: A Play in Three Acts......Page 465
Delilah Rebuild Project......Page 474
3. Combiner......Page 475
5. The project......Page 477
1. Context......Page 478
3. Turing\'s contribution......Page 479
4. What came after 1949?......Page 481
5. Assessment......Page 482
References......Page 483
Friday, 24th June. Checking a large routine. by Dr. A. Turing......Page 484
2. The Baby......Page 488
3. The early Manchester machines......Page 490
4. The Manchester University Inaugural Conference......Page 491
5. The programmers\' handbook for the Ferranti Mark 1......Page 492
7. Suggestions for further reading......Page 493
References......Page 494
Programming principles......Page 495
Part III: Building a Brain: Intelligent Machines, Practice and Theory......Page 502
Alan Turing: Mathematical Mechanist......Page 504
References......Page 508
Lecture to the London Mathematical Society on 20 February 1947......Page 509
The Case for Embodied Intelligence......Page 522
Abstract......Page 524
Varieties of machinery......Page 525
Logical computing machines (LCMs)......Page 526
Practical computing machines (PCMs)......Page 527
Unorganised machines......Page 528
Interference with machinery. Modifiable and self-modifying machinery......Page 530
Man as a machine......Page 531
Education of machinery......Page 532
Organizing unorganised machinery......Page 533
Experiments in organizing: pleasure–pain systems......Page 534
The P-type unorganised machine......Page 535
Intellectual, genetical and cultural searches......Page 538
References......Page 539
1. Introduction......Page 540
3. Contemporary impact......Page 541
4. Future developments and conclusion......Page 542
References......Page 543
1. Science as cryptanalysis......Page 544
2. At the National Physical Laboratory......Page 545
3. A computational world......Page 548
References......Page 552
Intelligence and the\rComputational Universe......Page 553
Cognition: Discrete or Continuous Computation?......Page 555
References......Page 561
Alan Turing at the NPL 1945–47......Page 562
The impact of the Pilot Ace on the parent Maths Division......Page 563
Turing\'s Legacy to NPL......Page 564
Thoughts on post-war computing at NPL......Page 565
Appendix 1: On \"Faster than Thought\"......Page 566
Appendix 2: References......Page 567
1. The universal machines that surround us......Page 568
2. The unexpectedness of universality......Page 569
3. Universal beings......Page 571
Mechanical Intelligence\rversus Uncomputable Creativity......Page 574
2. Critique of the New Problem.......Page 575
3. The Machines concerned in the Game.......Page 576
4. Digital Computers.......Page 577
5. Universality of Digital Computers.......Page 579
6. Contrary Views on the Main Question.......Page 580
(2)  The \'Heads in the Sand\' Objection.......Page 581
(3)  The Mathematical Objection.......Page 582
(5)  Arguments from Various Disabilities.......Page 583
(6)  Lady Lovelace\'s Objection.......Page 585
(8)  TheArgument from Informality of Behaviour.......Page 586
7. Learning Machines.......Page 587
Bibliography......Page 591
Turing\'s\r\"Strange Inversion of Reasoning\"......Page 592
References......Page 596
1. Introduction......Page 597
2. Epigenesis: Bodies, behaviours and minds......Page 598
3. The evolution of organisms with qualia......Page 599
4. What next?......Page 601
References......Page 602
The Phenomenal Case of the Turing Test and the Chinese Room......Page 603
1. A thinking machine?......Page 604
2. The Chinese Room Argument......Page 605
2.1. The\r\'translation reply\'......Page 606
2.2. The\r\'logical reply\'......Page 607
3. On consciousness and the metaphysical sensation of the inner......Page 608
References......Page 609
1. Intelligence before Turing......Page 610
2. Turing machines, intuition pumps and a word of caution......Page 611
3. Turing machines, new paradigms and open texture......Page 613
4. Intelligence and consciousness......Page 616
5. Information processing and phenomenology......Page 617
6. Evaluating the Turing test: the lessons of ELIZA......Page 619
7. Conclusion: The Turing test and the Tutoring test......Page 622
References......Page 623
1. Introduction......Page 624
2. Turing\'s idea of level of abstraction......Page 625
3. The method......Page 626
5. State and state-transitions......Page 627
References......Page 628
2. Turing\'s 1950 paper......Page 629
4. Turing\'s predictions......Page 630
5. Turing\'s error about human-like learning......Page 631
6. Dichotomies and continua......Page 632
References......Page 633
1. The grand challenge......Page 634
2. Measuring success......Page 635
3. Modifications to Turing\'s test......Page 636
1. Introduction......Page 637
2. Turing\'s early imitation game......Page 638
3. Turing\'s imitation game 1950......Page 640
4. Turing\'s later imitation game scholarship......Page 641
References......Page 642
Turing\'s Future......Page 643
References......Page 644
Turing and Chess......Page 646
References......Page 648
Digital Computers Applied to Games......Page 649
Chess......Page 650
The Manchester University Machine......Page 655
Draughts......Page 657
Basic Programme For Draughts......Page 658
Valuation of Positions and Strategy......Page 659
Nim......Page 662
Alan Turing on Computer Chess......Page 667
References......Page 673
1. Introduction......Page 674
2. Physics and uncomputability: a brief history......Page 675
3. Turing on physics and uncomputability......Page 679
4. Uncomputability and freewill......Page 680
References......Page 681
Can Digital Computers Think?......Page 683
Intelligent Machinery: A Heretical Theory......Page 687
Can Automatic Calculating Machines Be Said To Think?......Page 690
Quantum Complexity and the Foundations of Computing......Page 700
Part IV: The Mathematics of Emergence: The Mysteries of Morphogenesis......Page 704
Alan Turing\'s Work in Biology......Page 706
Turing\'s Theory of Morphogenesis......Page 707
References......Page 710
1. A model of the embryo: Morphogens......Page 712
3. Chemical reactions......Page 714
4. The breakdown of symmetry and homogeneity......Page 716
5. Left-handed and right-handed organisms......Page 718
6. Reactions and diffusion in a ring of cells......Page 720
7. Continuous ring of tissue......Page 723
8. Types of asymptotic behaviour in the ring after a lapse of time......Page 724
9. Further consideration of the mathematics of the ring......Page 728
10. A numerical example......Page 734
11. Restatement and biological interpretation of the results......Page 740
12. Chemical waves on spheres: Gastrulation......Page 743
References......Page 745
1. The article and its style......Page 746
2. A brief history of reaction–diffusion equations......Page 749
3. Instability and symmetry breaking......Page 751
4. Turing\'s paper in perspective......Page 753
References......Page 755
2. Stable pattern and travelling waves by two-component systems......Page 756
4. Wave formation by three-component systems......Page 758
5. An example......Page 759
References......Page 761
1. Introduction......Page 762
2. How the leopard gets its spots......Page 764
3. Experimentally verified prediction of a reaction–diffusion pattern formation model and resolution of a controversy......Page 770
4. Concluding discussion......Page 773
References......Page 775
2. The argument from design......Page 776
References......Page 778
The Mechanisms of Biology......Page 779
Reference......Page 781
Four Traditions of Emergence: Morphogenesis,  Ulam-von Neumann Cellular Automata, The Fermi-Pasta-Ulam Problem, and British.........Page 782
Reference......Page 785
From Turing to Metabiology and Life as Evolving Software......Page 786
2. Radiolaria......Page 788
3. The differential equation......Page 791
4. The solutions of the equations......Page 792
6. Comparisons with the marine species Radiolaria......Page 793
References......Page 794
Part I.\rGeometrical and Descriptive Phyllotaxis......Page 796
1. A description of certain leaf distribution patterns......Page 798
2. Helical coordinates for a phyllotactic system......Page 800
3. Parastichies and parastichy numbers......Page 801
4. Phyllotactic systems as lattices. The principal congruences......Page 802
5. The measurement of the phyllotaxis parameters......Page 803
7. The bracket and the fractional notations......Page 805
8. Naturally occurring phyllotactic patterns......Page 806
9. Lattice parameters......Page 807
10. Continued fraction properties......Page 809
11. Continuously changing phyllotaxis......Page 812
12. The inverse lattice......Page 814
13. Flow matrices......Page 816
14. The touching circles phyllotaxis......Page 817
15. The lattice described by its twist and other coordinates......Page 820
16. The optimum packing problem......Page 822
17. Comparison of methods of describing lattices......Page 824
18. Variation principle theories. Equilateral lattices......Page 825
1. Morphogen equations for an assembly of cells. The linear case......Page 827
2. Assumptions concerning the chemistry of phyllotaxis......Page 830
4. The equations applied to a plane......Page 834
6. Effects of random disturbances......Page 835
1. Reduction of the differential equation......Page 841
2. Solutions of the simultaneous equations......Page 844
3. Comparison with physical species......Page 847
Appendix......Page 848
Phyllotaxis:......Page 850
The Fibonacci sequence:......Page 853
Bibliography......Page 855
1. Introduction......Page 857
2. Modelling Fibonacci phyllotaxis......Page 858
3. Lattices on cylinders......Page 859
3.2. Finding the principal parastichy vectors......Page 861
4. Exploring the Hypothesis of Geometrical Phyllotaxis......Page 862
4.2. Fourier representations of functions with lattice symmetries......Page 863
5. The figures......Page 864
6. Seeing spots and making sense of life......Page 869
References......Page 871
1. Introduction: Types of emergence......Page 872
2. Layered computational emergence......Page 873
3. Meta-morphogenesis and biological complexity......Page 874
4. Less blind evolutionary transitions......Page 875
5. From morphogenesis to meta-morphogenesis......Page 876
6. Evolved information processing: beyond Gibson......Page 877
7. Monitoring and controlling virtual machinery......Page 878
References......Page 879
An Editorial Note......Page 881
Outline of the Development of the Daisy......Page 883
1. Considerations governing the choice of parameters......Page 885
2. Early stages in pattern formation......Page 887
History of the Publication of the Collected Works of Alan M. Turing......Page 891
Obituary: Robin Gandy......Page 893
2. Turing as a computer designer and user: the first facet of a genius......Page 895
4. Turing\'s work on Morphogenesis: the third facet of a genius......Page 897
References......Page 898
A Bibliography of Publications of Alan Mathison Turing......Page 900
A......Page 902
B......Page 903
C......Page 904
D......Page 908
E......Page 910
F......Page 911
G......Page 913
H......Page 914
I......Page 915
L......Page 917
M......Page 918
N......Page 921
O......Page 922
P......Page 923
R......Page 926
S......Page 928
T......Page 931
U......Page 934
W......Page 935
Z......Page 936