﻿

The Theory of Computation is a branch of computer science that deals with the properties, functions, and capabilities of computation. This field strives to understand computation as well as define and implement efficient solutions to the problems of today. It also seeks to discover the potential of computation in addition to its limits. Much of this work is through understanding and devising algorithms to be both efficient and effective. One important tool used in this field is the model of computation. While there are multiple kinds of these models currently being used, the most common model is called the Turing machine. This model is frequently studied because of its simplicity and because it is capable of being analyzed. The Turing machine is considered a very powerful and reasonable model by many. Some other models of computation include the Markov algorithm, lambda calculus, and the register machine.

The theory of computation can be split into three main areas; computability theory, automata theory, and computational complexity theory. Computability theory deals mainly with the limits to which a problem can be solved using a computer. This branch relates to recursion theory which is itself a branch of mathematical logic. Automata Theory focuses on abstract machines known as automata and the problems that can be solved by the use of these machines. Formal language theory is considered to be closely related to automata theory because automata are generally organized based on what languages they can identify. Finally, computational complexity theory is concentrated mainly on the efficiency of solutions not simply whether or not a problem can be solved. The two major aspects of this area are time and space complexity.

One thing that I found interesting about the theory of computation is the fact that it focuses mainly on the abstract and logical qualities of computation rather than the actual programming, networking, or software sides of computation. Another aspect of the theory of computation that I found interesting was the use of the different model including the Turing machine.

My questions:

How are models of computation used to evaluate problems?

What is the halting problem?

What kinds of problems have been solved using abstract machines?

Theory of Computation Tutorials:

Resources

Goldreich, O. (n.d.). A Brief Introduction to the Theory of Computation. Retrieved August 29,

Theory of Computation. (n.d.). Retrieved August 29, 2017, from Wow: