History of theory of computation: Difference between revisions

Revision as of 03:54, 17 December 2009

Revision as of 03:54, 17 December 2009

Line 1:

'''History of computer theory''' basically starts with or is revolutionized by in a modern 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 computer or not?").

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 computer theory that takes 100 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 problem.