Hilbert's tenth problem for a theory T asks if there is an algorithm which decides for a given polynomial p() from [] whether p() has a root in some model of T. We examine some of the model-theoretic consequences that an affirmative answer would have in cases such as T = Open Induction and others, and apply these methods by providing a negative answer in the cases when T is some particular finite fragment of the weak theories IE1 (...) or IU-1. (shrink)

We show that if R is a nonconstant regular (semi-)local subring of a rational function field over an algebraically closed field of characteristic zero, Hilbert's Tenth Problem for this ring R has a negative answer; that is, there is no algorithm to decide whether an arbitrary Diophantine equation over R has solutions over R or not. This result can be seen as evidence for the fact that the corresponding problem for the full rational field is also unsolvable.

Classical results of additive number theory lead to the undecidability of the existence of solutions for diophantine equations in given special sets of integers. Those sets which are images of polynomials are covered by a more general result in the second section. In contrast, restricting diophantine equations to images of exponential functions with natural bases leads to decidable problems, as proved in the third section.

The paper establishes lower bounds on the provability of.

Neil D. Jones, Computability and Complexity. From a Programming Perspective.Neil D. Jones, T. AE. Mogensen, Computability by Functional Languages.M. H. Sorensen, Hilbert's Tenth Problem.A. M. Ben-Amram, The Existence of Optimal Algorithms.

We show the algorithmic unsolvability of a number of decision procedures in ordinary two dimensional Euclidean geometry, involving lines and integer points. We also consider formulations involving integral domains of characteristic 0, and ordered rings. The main tool is the solution to Hilbert's Tenth Problem. The limited number of facts used from recursion theory are isolated at the beginning.

We show that the $\mathrm{D_A}$-unification problem is undecidable. That is, given two binary function symbols $\bigoplus$ and $\bigotimes$, variables and constants, it is undecidable if two terms built from these symbols can be unified provided the following $\mathrm{D_A}$-axioms hold: \begin{align*}(x \bigoplus y) \bigotimes z &= (x \bigotimes z) \bigoplus (y \bigotimes z),\\x \bigotimes (y \bigoplus z) &= (x \bigotimes y) \bigoplus (x \bigotimes z),\\x \bigoplus (y \bigoplus z) &= (x \bigoplus y) \bigoplus z.\end{align*} Two terms are $\mathrm{D_A}$-unifiable (i.e. an (...) equation is solvable in $\mathrm{D_A}$) if there exist terms to be substituted for their variables such that the resulting terms are equal in the equational theory $\mathrm{D_A}$. This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which an undecidability result has been obtained. (shrink)

For a ring R, Hilbert’s Tenth Problem $HTP$ is the set of polynomial equations over R, in several variables, with solutions in R. We view $HTP$ as an enumeration operator, mapping each set W of prime numbers to $HTP$, which is naturally viewed as a set of polynomials in $\mathbb {Z}[X_1,X_2,\ldots ]$. It is known that for almost all W, the jump $W'$ does not $1$ -reduce to $HTP$. In contrast, we show that every Turing degree contains (...) a set W for which such a $1$ -reduction does hold: these W are said to be HTP-complete. Continuing, we derive additional results regarding the impossibility that a decision procedure for $W'$ from $HTP$ can succeed uniformly on a set of measure $1$, and regarding the consequences for the boundary sets of the $HTP$ operator in case $\mathbb {Z}$ has an existential definition in $\mathbb {Q}$. (shrink)

We show that the D A -unification problem is undecidable. That is, given two binary function symbols $\bigoplus$ and $\bigotimes$ , variables and constants, it is undecidable if two terms built from these symbols can be unified provided the following D A -axioms hold: \begin{align*}(x \bigoplus y) \bigotimes z &= (x \bigotimes z) \bigoplus (y \bigotimes z),\\x \bigotimes (y \bigoplus z) &= (x \bigotimes y) \bigoplus (x \bigotimes z),\\x \bigoplus (y \bigoplus z) &= (x \bigoplus y) \bigoplus z.\end{align*} Two (...) terms are D A -unifiable (i.e. an equation is solvable in D A ) if there exist terms to be substituted for their variables such that the resulting terms are equal in the equational theory D A . This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which an undecidability result has been obtained. (shrink)

We explore the possibility of using quantum mechanical principles for hypercomputation through the consideration of a quantum algorithm for computing the Turing halting problem. The mathematical noncomputability is compensated by the measurability of the values of quantum observables and of the probability distributions for these values. Some previous no-go claims against quantum hypercomputation are then reviewed in the light of this new positive proposal.

This dissertation examines several of the problems that Hilbert discovered in the foundations of mathematics, from a metalogical perspective. The problems manifest themselves in four different aspects of Hilbert’s views: (i) Hilbert’s axiomatic approach to the foundations of mathematics; (ii) His response to criticisms of set theory; (iii) His response to intuitionist criticisms of classical mathematics; (iv) Hilbert’s contribution to the specification of the role of logical inference in mathematical reasoning. This dissertation argues that Hilbert’s axiomatic (...) approach was guided primarily by model theoretical concerns. Accordingly, the ultimate aim of his consistency program was to prove the model-theoretical consistency of mathematical theories. It turns out that for the purpose of carrying out such consistency proofs, a suitable modification of the ordinary first-order logic is needed. To effect this modification, independence-friendly logic is needed as the appropriate conceptual framework. It is then shown how the model theoretical consistency of arithmetic can be proved by using IF logic as its basic logic. Hilbert’s other problems, manifesting themselves as aspects (ii), (iii), and (iv)—most notably the problem of the status of the axiom of choice, the problem of the role of the law of excluded middle, and the problem of giving an elementary account of quantification—can likewise be approached by using the resources of IF logic. It is shown that by means of IF logic one can carry out Hilbertian solutions to all these problems. The two major results concerning aspects (ii), (iii) and (iv) are the following: (a) The axiom of choice is a logical principle; (b) The law of excluded middle divides metamathematical methods into elementary and non-elementary ones. It is argued that these results show that IF logic helps to vindicate Hilbert’s nominalist philosophy of mathematics. On the basis of an elementary approach to logic, which enriches the expressive resources of ordinary first-order logic, this dissertation shows how the different problems that Hilbert discovered in the foundations of mathematics can be solved. (shrink)

This paper has two parts, a historical and a systematic. In the historical part it is argued that the two major axiomatic approaches to relativistic quantum field theory, the Wightman and Haag-Kastler axiomatizations, are realizations of the program of axiomatization of physical theories announced by Hilbert in his 6th of the 23 problems discussed in his famous 1900 Paris lecture on open problems in mathematics, if axiomatizing physical theories is interpreted in a soft and opportunistic sense suggested in 1927 by (...) Hilbert, Nordheim, and von Neumann. To show this, Section 2 recalls first some of Hilbert's views about the axiomatic approach to physical theories as these were formulated in his 6th problem. It will be .. (shrink)

We show that elliptic curves whose Mordell–Weil groups are finitely generated over some infinite extensions of ${\mathbb {Q}}$ , can be used to show the Diophantine undecidability of the rings of integers and bigger rings contained in some infinite extensions of rational numbers.

We recall the characterisation of positive definite polynomial functions over a real closed ring due to Dickmann, and give a new proof of this result, based upon ideas of Abraham Robinson. In addition we isolate the class of convexly ordered valuation rings for which this characterisation holds.

We show that a solution to Hilbert's Tenth Problem in the rings of algebraic integers and bigger subrings of number fields where it is currently not known, is equivalent to a problem of bounding archimedean valuations over non-real number fields.

This paper provides the first examples of rings of algebraic numbers containing the rings of algebraic integers of the infinite algebraic extensions of where Hilbert's Tenth Problem is undecidable.

Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of homology (...) n-spheres {P k e } k ∈ ω which are also hypersurfaces, such that P k e is diffeomorphic to the standard n-sphere S n (denoted P k e ≈ diff S n ) iff T e halts on input k, and in this case the connected sum N k e =M ♯ P k e ≈ diff M , so N k e ∈ Met(M), and N k e is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time σ e (k) of T e on inputs y i } ∈ ω of c.e. sets so that for all i the settling time of the associated Turing machine for A i dominates that for A i + 1 , even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization." From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {A i } i ∈ ω above, not merely G öodel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T 5 (see §). (shrink)

This paper surveys the recent developments in the area that grew out of attempts to solve an analog of Hilbert's Tenth Problem for the field of rational numbers and the rings of integers of number fields. It is based on a plenary talk the author gave at the annual North American meeting of ASL at the University of Notre Dame in May of 2009.

For any subset $Z \subseteq {\mathbb {Q}}$, consider the set $S_Z$ of subfields $L\subseteq {\overline {\mathbb {Q}}}$ which contain a co-infinite subset $C \subseteq L$ that is universally definable in L such that $C \cap {\mathbb {Q}}=Z$. Placing a natural topology on the set ${\operatorname {Sub}({\overline {\mathbb {Q}}})}$ of subfields of ${\overline {\mathbb {Q}}}$, we show that if Z is not thin in ${\mathbb {Q}}$, then $S_Z$ is meager in ${\operatorname {Sub}({\overline {\mathbb {Q}}})}$. Here, thin and meager both mean “small”, (...) in terms of arithmetic geometry and topology, respectively. For example, this implies that only a meager set of fields L have the property that the ring of algebraic integers $\mathcal {O}_L$ is universally definable in L. The main tools are Hilbert’s Irreducibility Theorem and a new normal form theorem for existential definitions. The normal form theorem, which may be of independent interest, says roughly that every $\exists $-definable subset of an algebraic extension of ${\mathbb Q}$ is a finite union of single points and projections of hypersurfaces defined by absolutely irreducible polynomials. (shrink)

Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating properties. (...) Although these computability results had been announced earlier, their proofs have been deferred until this paper. Computably enumerable sets have long been used to prove undecidability of mathematical problems such as the word problem for groups and Hilbert's Tenth Problem. However, this example by Nabutovsky and Weinberger is perhaps the first example of the use of c.e. sets to demonstrate specific mathematical or geometric complexity of a mathematical structure such as the depth and distribution of local minima. (shrink)

This book presents a set of historical recollections on the work of Martin Davis and his role in advancing our understanding of the connections between logic, computing, and unsolvability. The individual contributions touch on most of the core aspects of Davis’ work and set it in a contemporary context. They analyse, discuss and develop many of the ideas and concepts that Davis put forward, including such issues as contemporary satisfiability solvers, essential unification, quantum computing and generalisations of Hilbert’s (...) class='Hi'>tenth problem. The book starts out with a scientific autobiography by Davis, and ends with his responses to comments included in the contributions. In addition, it includes two previously unpublished original historical papers in which Davis and Putnam investigate the decidable and the undecidable side of Logic, as well as a full bibliography of Davis’ work. As a whole, this book shows how Davis’ scientific work lies at the intersection of computability, theoretical computer science, foundations of mathematics, and philosophy, and draws its unifying vision from his deep involvement in Logic. (shrink)

In 2000, a draft note of David Hilbert was found in his Nachlass concerning a 24th problem he had consider to include in the his famous problem list of the talk at the International Congress of Mathematicians in 1900 in Paris. This problem concerns simplicity of proofs. In this paper we review the traces of this problem which one can find in the work of Hilbert and his school, as well as modern research started on it (...) after its publication. We stress, in particular, the mathematical nature of the problem.1. (shrink)

It is not yet clear just what the most illuminating ways of rigorously stating the Incompleteness Theorems are. This is particularly true of the Second. Also I believe that there are more illuminating proofs of the Second that have yet to be uncovered.

Putnam’s most famous contribution to mathematical logic was his role in investigating Hilbert’s Tenth Problem; Putnam is the ‘P’ in the MRDP Theorem. This volume, though, focusses mostly on Putnam’s work on the philosophy of logic and mathematics. It is a somewhat bumpy ride. Of the twelve papers, two scarcely mention Putnam. Three others focus primarily on Putnam’s ‘Mathematics without foundations’ (1967), but with no interplay between them. The remaining seven papers apparently tackle unrelated themes. Some of (...) this disjointedness would doubtless have been addressed, if Putnam had been able to compose his replies to these papers; sadly, he died before this was possible. In this review, I do my best to tease out some connections between the paper; and there are some really interesting connections to be made. (shrink)

This book continues from where the authors' previous book, Structural Proof Theory, ended. It presents an extension of the methods of analysis of proofs in pure logic to elementary axiomatic systems and to what is known as philosophical logic. A self-contained brief introduction to the proof theory of pure logic is included that serves both the mathematically and philosophically oriented reader. The method is built up gradually, with examples drawn from theories of order, lattice theory and elementary geometry. The aim (...) is, in each of the examples, to help the reader grasp the combinatorial behaviour of an axiom system, which typically leads to decidability results. The last part presents, as an application and extension of all that precedes it, a proof-theoretical approach to the Kripke semantics of modal and related logics, with a great number of new results, providing essential reading for mathematical and philosophical logicians. (shrink)

The theory that ``consistency implies existence'' was put forward by Hilbert on various occasions around the start of the last century, and it was strongly and explicitly emphasized in his correspondence with Frege. Since (Gödel's) completeness theorem, abstractly speaking, forms the basis of this theory, it has become common practice to assume that Hilbert took for granted the semantic completeness of second order logic. In this paper I maintain that this widely held view is untrue to the facts, and that (...) the clue to explain what Hilbert meant by linking together consistency and existence is to be found in the role played by the completeness axiom within both geometrical and arithmetical axiom systems. (shrink)

We investigate the issues of Diophantine definability over the non-finitely generated version of non-degenerate modules contained in the infinite algebraic extensions of the rational numbers. In particular, we show the following. Let k be a number field and let K inf be a normal algebraic, possibly infinite, extension of k such that k has a normal extension L linearly disjoint from K inf over k. Assume L is totally real and K inf is totally complex. Let M inf be a (...) non-degenerate O k -module, possibly non-finitely generated and contained in O Kinf . Then M inf contains a submodule M¯ inf such that M inf /M¯ inf is torsion and O k has a Diophantine definition over M¯ inf. (shrink)

Let ∃n denote the set of all formulas ∃x1…∃xn[P = 0], where P is a polynomial with integer coefficients. We prove a new relation-combining theorem from which it follows that if ∃n is undecidable over N, then ∃2n+2 is undecidable over Z.

S. Negri and J. von Plato, Proof Analysis. A Contribution to Hilbert's Last Problem. Cambridge University Press: Cambridge, 2011. 278 pp. $90.00. ISBN:978-1-107-00895-3. Reviewed by F. Poggiolesi,...

In the present paper, these authors argue on actual reasons why Hilbert’s axiomatic program to unify gravitation theory and electromagnetism failed completely. An outline of plausible resolution of this problem is given here, based on: a) Gödel’s incompleteness theorem, b) Newton’s aether stream model. And in another paper we will present our calculation of receding Moon from Earth based on such a matter creation hypothesis. More experiments and observations are called to verify this new hypothesis, albeit it is (...) inspired from Newton’s theory himself. (shrink)

Hilbert's plan for understanding the concept of infinity required the elimination of non‐finitist machinery from proofs of finitist assertions. The failure of the original plan leads to a hierarchy of progressively less elementary, but still constructive methods instead of finitist ones . A mathematical proof of this failure requires a definition of « finitist ».—The paper sketches the three principal methods for the syntactic analysis of non‐constructive mathematics, the resulting consistency proofs and constructive interpretations, modelled on Herbrand's theorem, and their (...) mathematical and logical consequences. A characterization of finitist proofs is sketched. A remark on the completeness of the predicate calculus concludes the paper. Throughout open problems and alternative approaches are emphasized.ZusammenfassungHilbert sah das Verstehen des Begriffs des Unendlichen in der Eliminierung nichtfiniter Methoden aus Beweisen finiter Sätze. Das Versagen dieses Unternehmens führt zu einer Hierarchic progressiv weniger elementarer, aber noch konstruktiver Methoden, statt der finiten . Ein Unmöglichkeitsbeweis des ursprünglichen Planes setzt eine Definition von « finit » voraus.—Die drei wichtigsten Methoden der syntaktischen Analyse nichtkonstruktiver mathematischer Theorien, die daraus gewonnenen Widerspruchsfreiheitsbeweise and konstruktiven Interpretationen and deren mathematische and logische Anwendungen werden besprochen. Eine Prazisierung des Begriffs « finit » wird skizziert. Eine Bemerkung zur Vollstandigkeit des engeren Funktionenkalküls beschliesst die Abhandlung.—Oflene Fragen and komplementare Fragestellungen werden betont. (shrink)

Formalism in the philosophy of mathematics has taken a variety of forms and has been advocated for widely divergent reasons. In Sects. 1 and 2, I briefly introduce the major formalist doctrines of the late nineteenth and early twentieth centuries. These are what I call empirico-semantic formalism, game formalism and instrumental formalism. After describing these views, I note some basic points of similarity and difference between them. In the remainder of the paper, I turn my attention to Hilbert’s instrumental (...) formalism. My primary aim there will be to develop its formalist elements more fully. These are, in the main, its rejection of the axiom-centric focus of traditional model-construction approaches to consistency problems, its departure from the traditional understanding of the basic nature of proof and its distinctively descriptive or observational orientation with regard to the consistency problem for arithmetic. More specifically, I will highlight what I see as the salient points of connection between Hilbert’s formalist attitude and his finitist standard for the consistency proof for arithmetic. I will also note what I see as a significant tension between Hilbert’s observational approach to the consistency problem for arithmetic and his expressed hope that his solution of that problem would dispense with certain epistemological concerns regarding arithmetic once and for all. (shrink)

David Hilbert's finitistic standpoint is a conception of elementary number theory designed to answer the intuitionist doubts regarding the security and certainty of mathematics. Hilbert was unfortunately not exact in delineating what that viewpoint was, and Hilbert himself changed his usage of the term through the 1920s and 30s. The purpose of this paper is to outline what the main problems are in understanding Hilbert and Bernays on this issue, based on some publications by them which have so far received (...) little attention, and on a number of philosophical reconstructions of the viewpoint (in particular, by Hand, Kitcher, and Tait). (shrink)