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:

https://www.youtube.com/playlist?list=PL601FC994BDD963E4

Resources

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

2017, from http://www.wisdom.weizmann.ac.il/~oded/toc-bi.html

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

http://www.wow.com/wiki/Theory_of_computation