Hilbert's 10th Problem (Foundations of Computing) [Hardcover]

Yuri Matiyasevich (Author), Martin Davis (Foreword), Hilary Putnam (Foreword)

Book Description

Series: Foundations of Computing | Publication Date: October 13, 1993

At the 1900 International Congress of Mathematicians, held that year in Paris, the German mathematician David Hilbert put forth a list of 23 unsolved problems that he saw as being the greatest challenges for twentieth-century mathematics. Hilbert's 10th problem, to find a method (what we now call an algorithm) for deciding whether a Diophantine equation has an integral solution, was solved by Yuri Matiyasevich in 1970. Proving the undecidability of Hilbert's 10th problem is clearly one of the great mathematical results of the century.This book presents the full, self-contained negative solution of Hilbert's 10th problem. In addition it contains a number of diverse, often striking applications of the technique developed for that solution (scattered previously in journals), describes the many improvements and modifications of the original proof - since the problem was "unsolved" 20 years ago, and adds several new, previously unpublished proofs.Included are numerous exercises that range in difficulty from the elementary to small research problems, open questions,and unsolved problems. Each chapter concludes with a commentary providing a historical view of its contents. And an extensive bibliography contains references to all of the main publications directed to the negative solution of Hilbert's 10th problem as well as the majority of the publications dealing with applications of the solution.Intended for young mathematicians, Hilbert's 10th Problem requires only a modest mathematical background. A few less well known number-theoretical results are presented in the appendixes. No knowledge of recursion theory is presupposed. All necessary notions are introduced and defined in the book, making it suitable for the first acquaintance with this fascinating subject.Yuri Matiyasevich is Head of the Laboratory of Mathematical Logic, Steklov Institute of Mathematics, Russian Academy of Sciences, Saint Petersburg.

Editorial Reviews

Language Notes

Text: English (translation)
Original Language: Russian

About the Author

This book presents the full, self-contained negative solution of Hilbert's 10th problem.

Product Details

• Hardcover: 288 pages
• Publisher: The MIT Press (October 13, 1993)
• Language: English
• ISBN-10: 0262132958
• ISBN-13: 978-0262132954
• Product Dimensions: 9.3 x 7.4 x 0.8 inches
• Shipping Weight: 1.3 pounds (View shipping rates and policies)
• Average Customer Review: 5.0 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #1,154,443 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

2 of 2 people found the following review helpful:

5.0 out of 5 stars Masterful and elucidating on many levels, April 5, 2008

By 

terrence--76 - See all my reviews

Amazon Verified Purchase

This review is from: Hilbert's 10th Problem (Foundations of Computing) (Hardcover)

Hilbert's 10th problem was solved, as well explicated in this book, but many of the ramifications of this solution were very unexpected and almost surprising beyond belief!

This book is not easy, but it is also not hard in the way if many advanced mathematical texts. The authors have done a great service by presenting proofs well within the range of non-experts with a general college level of mathematical sophistication. They are truly to be congratulated for this unique and priceless contribution to mathematical literature. No one had any idea of the rich results that would ensue on the solution to this seemingly simple to state problem, and the not so surprising result that the answer was in the negative. If you like mathematics, you will find many delightful and surprising results presented here in a way very comprehensible to those willing to work through these proofs designed for the most general audience possible.

3 of 4 people found the following review helpful:

5.0 out of 5 stars Algorithm, Turing Machine, Turing Decidable, Solvability, May 2, 2008

By 

Man Kam Tam (Calexico, CA USA) - See all my reviews
(REAL NAME)   

Amazon Verified Purchase

This review is from: Hilbert's 10th Problem (Foundations of Computing) (Hardcover)

Yuri V. Matiyasevich's "Hilbert's Tenth Problem" has two parts. "The first part, consisting of Chapters 1-5, presents the solution of Hilbert's Tenth Problem." The second part (Chapters 6-10) is "devoted to application."

Hilbert's Tenth Problem is about the "determination of the solvability of a Diophantine equation." To be specific, the problem asked for "devise a process ... which ... can ... [determine in] a finite number of operations whether the equation is solvable in ... integers." David Hilbert posted the problem in 1900. "Today ... the words `devise a process' ... mean `find an algorithm.' When Hilbert's Problem was posed, there was no ... rigorous ... notion of algorithm ... [Until 1930s] Kurt Godel, Alonzo Church, Alan Turing, and other logicians provided a rigorous formulation ... of computability; [then] ... it [is] possible to establish algorithmic insolvability ... "

The problem was considered solved by Yuri Matiyasevich in 1970. In short, Matiyasevich proved the Martin Davis's conjecture. The readers will find Matiyasevich's "Hilbert's Tenth Problem: What can we do with Diophantine equations?" helpful. Martin Davis's conjecture states that a set is Diophantine if and only if it is list-able. There is a classical result in the computability theory: there exists an un-decidable list-able set. The un-decidability of the set implies that there is no algorithm to determine [the] values of the parameters [of] the Diophantine representation [so that the representation] has a solution.

On the other hand, the material on the book is more technical. "... we can reformulate Hilbert's Tenth Problem in the following ... way: is the set of codes of all solvable Diophantine equations ... Turing decidable? ... the complement of [the set of codes] is not Diophantine. This implies that [the set] is not Turing decidable. In other words, it is impossible to construct a Turing machine that ... will halt after a finite number of steps in state q2 [yes] or q3 [no], depending on whether the equation ... is or is not solvable."

In terms of application, "we can construct a Diophantine equation whose un-solvability is equivalent to the Riemann Hypothesis." Similar utilization can be applied to number theory, calculus, and game theory problems. But we have no obvious way to restate the twin prime conjecture ... as the problem of the solvability or un-solvability of a particular Diophantine equation."