History of theory of computation: Difference between revisions

Revision as of 04:00, 17 December 2009

Revision as of 04:02, 17 December 2009

Line 1:

{{original research|date=December 2009}}

{{unreferenced|date=December 2009}}

'''History of computer theory''' basically starts with in a modernpure 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?"), 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.