Theory of computation

   首页  History
 
History

History of computer theory basically starts with in a pure sense by Alan Turing, who devised notion of Turing machine, Turing thesis, Church-Turing hypothesis. Earlier form of computer theory might've existed before Alan Turing and others, but Turing is considered by substantial number of people today to be a important figure in pure computer theory ("Can it be computed or not?"), but not necessarly in computing something for practical purposes ("Can it be computed quickly?").

The goal of computer theory is to answer the question, "What is computable?" There are many different ways to answer the question taking into account space and time needed to compute the problem, but the central question in computer theory is "What can be computed efficiently within a certain and time constraints?" This tries to focus computer theory to practical purposes and applications, instead of studying about a Turing machine that takes 200 years to compute something, which isn't practical in real world. The ultimate answer from the Turing machine test is that anything can be computed by ignoring time and space. From this the area of algorithm design came about to give solutions and basically to create faster and efficient algorithm to compute a real world problem.


版权所有 © Theory of computation