Introduction to Computability

Part of the Algorithms and Computation in Mathematics book series (AACIM, volume 23)

One of the main goals of computability theory is to classify problems according to whether or not they can be solved algorithmically. In fact, such questions existed before computers. A famous example is Hilbert's Tenth Problem:

“Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.” [Bulletin of the AmericanMathematical Society 8 (1902), 437- 479.]

In other words:

Is it algorithmically possible to determine if a given Diophantine equation is solvable?

It is fairly clear what an affirmative answer would mean in this case - an explicit method to check if an equation has a solution. Giving a negative answer (which turns out to be the correct one) requires a more formal definition of “methods” that can be used in the solution - as one would need to prove that none of these methods work.

Such formal models of computation precede modern computers. In 1936 two essentially equivalent models were independently proposed by A. Turing [Tur36] and E. Post [Pos36] (and many others have appeared since). Turing’s work has been the most influential, and his concept of a Turing Machine has become a universally accepted formal model of computation.


Turing Machine Computable Function Diophantine Equation Computable Number Oracle Access 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Copyright information

© Springer-Verlag Berlin Heidelberg 2009

Personalised recommendations