Martin Davis on Computability, Computational Logic, and Mathematical Foundations - Martin Davis on Computability, Computational Logic, and Mathematical Foundations -

My Life as a Logician Martin Davis and Hilbert’s Tenth Problem The Problem Martin Davis Conjecture Statement and Corollaries The First Step to the Proof A Milestone The Last Step Further Modifications of Original Proofs Pell Equation Eliminating Bounded Universal Quantifier Existential Arithmetization Improvements Single-Fold Representations Representations with a Small Number of Quantifiers “Positive Aspects of a Negative Solution”Speeding Up Diophantine Equations Universal Equations Hilbert’s Eighth and Tenth Problems Other Impossibilities The Number of Solutions Non-effectivizable Estimates Solutions in Other Rings References Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory The End of the Beginning Diophantine Subsets of a Ring Properties of Diophantine Sets So What About Q?Z Is Probably Not Existentially Definable over Q Elliptic Curves and Diophantine Models The Rings Between Z and Q Diophantine Properties of Big and Small Rings Existential Models of Z over Big Rings The Other End of the Spectrum All Together Now (with Universal Quantifiers) Up and Away HTP over the Rings of Integers of Number Fields Positive Stable Rank Condition and Elliptic Curves Big Rings Inside Number Fields Universal and Existential Together in Extensions Open Questions over Number Fields Infinite Extensions Defining Integers Via Norm Equations Defining Z Using Elliptic Curves with Finitely Generated Groups over the Given Field and One Completely q-Bounded Prime Converting Definability to Undecidability over infinite extensions Final Remarks References A Story of Hilbert’s Tenth Problem Introduction The Beginning Yuri Matiyasevich Matiyasevich’s Solution References Hyperarithmetical Sets Preamble: Kleene [15], Post [42] and Mostowski [38]Post’s Degrees of Unsolvability Kleene’s Arithmetical Hierarchy Kleene [15] Versus Post [42]Mostowski [38] and the Analogies On into the Transfinite! Notations for Ordinals, Si and O The Ha-sets Myhill [40]Effective Grounded Recursion The Basic Facts About HYP (1950-1960)Codings and Uniformities HYP as Effective Borel Lebesgue [28] and Mostowski [39]The Analytical Hierarchy; HYP c A|Kleene’s Theorem, HYP = A Addison [1] and the Revised Analogies Relativization and the Kreisel Uniformization Theorem HYP-Quantification and the Spector-Gandy Theorem The Kleene [22] HYP hierarchy Inductive Definability on N HYP as Recursive in 2E Concluding Remarks IND and HYP on Abstract Structures Effective Descriptive Set Theory Appendix: Some Basic Facts and Notation References Honest Computability and Complexity Honesty Is Needed Dishonest Representations Honest Representations Honest Implementation Honest Computability Honest Comparisons Honest Universality Honest Complexity Dishonest Decisions Discussion References Why Post Did [Not] Have Turing’s Thesis Introduction The Finiteness Problem for Principia Mathematica Canonical Systems and Their Reductions Reasons for a Thesis Anticipating Turing’s and Godel’s Results A Natural Law: Inescapable Limitations Symbolic Logics: Finitary Constraints Yes, No, and Broader Contexts References On Quantum Computation, Anyons, and Categories Introduction Quantum Theory and Anyons Quantum Mechanics Anyons Anyons in Reality Anyons in Quantum Computation Modular Tensor Categories Additive Structure Multiplicative Structure Duals, Twists, and Modularity Yoneda Simplification Fibonacci Anyons Definition and Additive Structure Tensor Products Notation for Basis Vectors Associativity Braiding Fibonacci Anyons and Quantum Computation References Taking Physical Infinity Seriously Introduction Multiple Uses of Infinity in physics Benardete’s Challenge The Electron—Getting to the Point NSA Back to the Real World Summary and Discussion References Banishing Ultrafilters from Our Consciousness Introduction Basic Construction for Nonstandard Analysis Bounded Formulae and the Transfer Principle A Kind of ‘All-at-Once Compactification’Key Application of the Nonstandard Methods Basic Features of Our Proof Checker Top-Down Recognition of Superstructure Stages Forging Companion Sets of Individuals Set-Encoding of Bounded-Quantifier Formulae Related Work Concluding Remarks References What Is Essential Unification?Introduction Notions and Notation Signatures, Terms and Term Algebras Substitutions Congruences and Equation Orders E-Unification Essential E-Unification Essentially Nullary Theories What Is Currently Known Associativity and Idempotency Associativity Commutativity Idempotency Conclusion References DPLL: The Core of Modern Satisfiability Solvers Introduction The DP and DPLL Procedures with Historical Context The Long Wait Modern Complete SAT Solvers Key Features Conclusions References On Davis’s “Pragmatic Platonism”Martin Davis’s Realism in Mathematics The Sort of Realism I Defend Relations Between Davis’s and My Forms of Mathematical Realism Indispensability Arguments—What Mine Was, and Are They Necessary Pragmatic Platonism Godel’s Platonism Godel Incompleteness and the Metaphysics of Arithmetic Infinity in the Seventeenth Century Robustness of Formalism The Ontology of Mathematics Infinity Today The Chimerical Effort to Seek Certainty References Concluding Comments by Martin Comments on Yuri Matiyasevich’s Essay Comments on Hilary Putnam’s Remarks on “Pragmatic Platonism”Mathematics and Natural Science The Benacerraf Problem New Axioms Modal Logic and Mathematical Existence References Martin Davis’s Bibliography 1950-2015