Theory of computation
History
Computability theory
Complexity theory
Other formal definitions of computation
Theoretical foundation of computing
Further reading
今天是
课程描述
History
Computability theory
Complexity theory
Other formal definitions of computation
Theoretical foundation of computing
Further reading
导航
Main page
Contents
Featured content
Current events
外部链接
Welcome to Theory of computation
The theory of computation or computer theory is the branch of computer science and mathematics that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into two major branches: computability theory and complexity theory, but both branches deal with formal models of computation. In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine. A Turing machine can be thought of as a desktop PC with a potentially infinite memory capacity, though it can only access this memory in small discrete chunks. Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" model of computation. It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any decidable problem solved by a Turing machine will always require only a finite amount of memory. So in principle, any problem that can be solved (decided) by a Turing machine can be solved by a computer that has a bounded amount of memory.
课程图片
滚动新闻
关于申报教育部基础教育课程改革教学研究成果的通知（续）
2010教学团队申报通知
2010年上海市精品课程申报通知
2010年教育部双语教学示范课程申报通知
关于申报教育部基础教育课程改革教学研究成果的通知（续）
2010教学团队申报通知
2010年上海市精品课程申报通知
2010年教育部双语教学示范课程申报通知
热门文章
站内搜索
版权所有 ©
Theory of computation
