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

My Life as a LogicianMartin Davis and Hilbert’s Tenth ProblemThe ProblemMartin Davis ConjectureStatement and CorollariesThe First Step to the ProofA MilestoneThe Last StepFurther Modifications of Original ProofsPell EquationEliminating Bounded Universal QuantifierExistential ArithmetizationImprovementsSingle-Fold Representations Representations with a Small Number of Quantifiers“Positive Aspects of a Negative Solution”Speeding Up Diophantine EquationsUniversal EquationsHilbert’s Eighth and Tenth ProblemsOther ImpossibilitiesThe Number of SolutionsNon-effectivizable EstimatesSolutions in Other RingsReferencesExtensions of Hilbert’s Tenth Problem: Definability and Decidability in Number TheoryThe End of the BeginningDiophantine Subsets of a RingProperties of Diophantine SetsSo What About Q?Z Is Probably Not Existentially Definable over QElliptic Curves and Diophantine ModelsThe Rings Between Z and QDiophantine Properties of Big and Small RingsExistential Models of Z over Big RingsThe Other End of the SpectrumAll Together Now (with Universal Quantifiers) Up and AwayHTP over the Rings of Integers of Number FieldsPositive Stable Rank Condition and Elliptic CurvesBig Rings Inside Number FieldsUniversal and Existential Together in ExtensionsOpen Questions over Number FieldsInfinite ExtensionsDefining Integers Via Norm EquationsDefining Z Using Elliptic Curves with Finitely Generated Groups over the Given Field and One Completely q-Bounded PrimeConverting Definability to Undecidability over infinite extensionsFinal RemarksReferencesA Story of Hilbert’s Tenth ProblemIntroductionThe BeginningYuri MatiyasevichMatiyasevich’s SolutionReferencesHyperarithmetical SetsPreamble: Kleene [15], Post [42] and Mostowski [38]Post’s Degrees of UnsolvabilityKleene’s Arithmetical HierarchyKleene [15] Versus Post [42]Mostowski [38] and the AnalogiesOn into the Transfinite! Notations for Ordinals, Si and OThe Ha-setsMyhill [40]Effective Grounded RecursionThe Basic Facts About HYP (1950-1960)Codings and UniformitiesHYP as Effective BorelLebesgue [28] and Mostowski [39]The Analytical Hierarchy; HYP c A|Kleene’s Theorem, HYP = AAddison [1] and the Revised AnalogiesRelativization and the Kreisel Uniformization TheoremHYP-Quantification and the Spector-Gandy TheoremThe Kleene [22] HYP hierarchyInductive Definability on NHYP as Recursive in 2EConcluding RemarksIND and HYP on Abstract StructuresEffective Descriptive Set TheoryAppendix: Some Basic Facts and NotationReferencesHonest Computability and ComplexityHonesty Is NeededDishonest RepresentationsHonest RepresentationsHonest ImplementationHonest ComputabilityHonest ComparisonsHonest UniversalityHonest ComplexityDishonest DecisionsDiscussionReferencesWhy Post Did [Not] Have Turing’s ThesisIntroductionThe Finiteness Problem for Principia MathematicaCanonical Systems and Their ReductionsReasons for a ThesisAnticipating Turing’s and Godel’s ResultsA Natural Law: Inescapable LimitationsSymbolic Logics: Finitary ConstraintsYes, No, and Broader ContextsReferencesOn Quantum Computation, Anyons, and CategoriesIntroductionQuantum Theory and AnyonsQuantum MechanicsAnyonsAnyons in RealityAnyons in Quantum ComputationModular Tensor CategoriesAdditive StructureMultiplicative StructureDuals, Twists, and ModularityYoneda SimplificationFibonacci AnyonsDefinition and Additive StructureTensor ProductsNotation for Basis VectorsAssociativityBraidingFibonacci Anyons and Quantum ComputationReferencesTaking Physical Infinity SeriouslyIntroductionMultiple Uses of Infinity in physicsBenardete’s ChallengeThe Electron—Getting to the PointNSABack to the Real WorldSummary and DiscussionReferencesBanishing Ultrafilters from Our ConsciousnessIntroductionBasic Construction for Nonstandard AnalysisBounded Formulae and the Transfer PrincipleA Kind of ‘All-at-Once Compactification’Key Application of the Nonstandard MethodsBasic Features of Our Proof CheckerTop-Down Recognition of Superstructure StagesForging Companion Sets of IndividualsSet-Encoding of Bounded-Quantifier FormulaeRelated WorkConcluding RemarksReferencesWhat Is Essential Unification?IntroductionNotions and NotationSignatures, Terms and Term AlgebrasSubstitutionsCongruences and EquationOrdersE-UnificationEssential E-UnificationEssentially Nullary TheoriesWhat Is Currently KnownAssociativity and IdempotencyAssociativityCommutativityIdempotencyConclusionReferencesDPLL: The Core of Modern Satisfiability SolversIntroductionThe DP and DPLL Procedures with Historical ContextThe Long WaitModern Complete SAT SolversKey FeaturesConclusionsReferencesOn Davis’s “Pragmatic Platonism”Martin Davis’s Realism in MathematicsThe Sort of Realism I DefendRelations Between Davis’s and My Forms of Mathematical RealismIndispensability Arguments—What Mine Was, and Are They NecessaryPragmatic PlatonismGodel’s PlatonismGodel Incompleteness and the Metaphysics of ArithmeticInfinity in the Seventeenth CenturyRobustness of FormalismThe Ontology of MathematicsInfinity TodayThe Chimerical Effort to Seek CertaintyReferencesConcluding Comments by MartinComments on Yuri Matiyasevich’s EssayComments on Hilary Putnam’s Remarks on “Pragmatic Platonism”Mathematics and Natural ScienceThe Benacerraf ProblemNew AxiomsModal Logic and Mathematical ExistenceReferencesMartin Davis’s Bibliography 1950-2015