Customer Reviews

Hilbert's 10th Problem (Foundations of Computing)

5 star:		(2)
4 star:		(0)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

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.

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."