Theory of Computation

Theory of Computation is a branch of computer science that is primarily concerned with how problems can be solved using algorithms. These studies are used to understand the way an algorithm is meant to function, and to actually prove it works through analyzing problems that may occur with the technique used and finding solutions to these problems. Additionally, on how efficiently problems can be solved on a model of computation, using an algorithm.

In this precise field of study, computer scientists work using a model of computation. The preferred model currently is the Turing machine model. This is because it is fairly simple, can be analyzed and used to prove results. Theory of Computation is a massive field to study from. Therefore, it is divided into three different branches: Computability theory, automata theory, and computational complexity theory.

So, the first branch mainly deals with the question of the extent to which a problem is solvable on a computer. Also, it is sort of related to the branch of mathematical logic given the term recursion theory, which eliminates the restriction of studying only models of computation, which are reducible to the Turing model. Lots of mathematicians and computational thinkers who study recursion theory refer to it as computability theory.

Then we have Automata theory, which is a study of abstract machines (or more suitably, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these devices. These abstract machines are called automata.Which means that something is doing something by itself. Automata theory is also closely linked to formal language theory, as the automata are often classified by the class of formal languages they are able to recognize.

And the Third one is, The Computational complexity theory takes into consideration whether a problem can be solved at all on a computer, in addition to how efficiently the problem can be solved. The two main aspects in this process are: time complexity and space complexity. Time complexity is how many steps does it take to perform a computation, and Space complexity is how much memory is needed to carry out that computation.

Also there is something called model of computation. Which is the description of the tasks used in computation. It is used to measure the complexity of an algorithm in execution period and memory space. Examples of models of computation other than Turing machines are: finite state machines, combinatory logic, lambda calculus, recursive functions, and abstract rewriting systems.

To sum up all, theory of computation allows us to discover the nature of computations in a higher level to understand new ideas and apply them to computer science.


For more information about Theory of Computation :

  • Cin
  • Youtube
  • Youtube
  • Wikipedia
  • wisdom

  • Questions :

    What part of TOC are we going to study in the future?and in which year?

    Who came up with the idea of TOC?

    Which branch does the professor finds interesting?


    Programming Language and Verification

    “Everybody in this country should learn how to program a computer because it teaches you . how to think” – Steve Jobs

    Cloud Computing

    Cloud computing is a new type of network based computing which takes place over the Internet. it’s supposed to store and access data and programs over the internet instead of your computer’s hard drive.