Formal Models and Computability

Authored by: Tao Jiang , Ming Li , Bala Ravikumar

Computing Handbook

Print publication date:  May  2014
Online publication date:  May  2014

Print ISBN: 9781439898529
eBook ISBN: 9781439898536
Adobe ISBN:


 Download Chapter



The concept of algorithms is perhaps almost as old as human civilization. The famous Euclid algorithm is more than 2000 years old. Angle trisection, solving Diophantine equations, and finding polynomial roots in terms of radicals of coefficients are some well-known examples of algorithmic questions. However, until the 1930s, the notion of algorithms was used informally (or rigorously but in a limited context). It was a major triumph of logicians and mathematicians of the last century to offer a rigorous definition of this fundamental concept. The revolution that resulted in this triumph was a collective achievement of many mathematicians, notably Church, Gödel, Kleene, Post, and Turing. Of particular interest is a machine model proposed by Turing (1936), which has come to be known as the Turing machine (TM).

Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.