THEORY OF COMPUTATION SUMMARY
Efficient computation is a term every single programmer in general is looking to achieve.
But what about the theory behind it? The Theory of Computation deals with the properties
of computation. It deals with how effecient algorithms are made and executed into actual
solution to a problem and how the the solution actually works.
The complexity of an algorithm is measured using a Model of Computation. A Model of Computation
is a collection of all the operations which can be executed, along with the various restrictions
like cost, time, etc. By understanding a model, one can figure out the required resources and
the limitations of algorithms. Most common/famous model is the Turing Machine. Turing Machine,
physically is a device that changes symbols on a piece of tape, following a set of rules
designed for it. A Turing machine can be used to simulate a computer algorithm.
One of the several applications of the Theory of Computing is programming languages and compilers,
specially Push Down Automation(PDA). PDA employs a stack of data, which is a data type that
has a collection of various elements and can operate in two ways- with a "push", which adds an
element, and "pop", which removes an element. Thus, "Push Down" in PDA refers to the pushing
down of stack, as operations in PDA work only on the top elements.
We may always be able to come up with a working algorithm for a problem that we have. But, what
matters is the effeciency of the algorithm. It may take several years of hard work, constant
stress and use of resources, which, when used on other fields of life may prove to be more
useful. Even after all the trouble, if we do come up with an algorithm, the computer may take
a really long time to interpret, apply and produce the desired results. By "really long time",
we are looking at centuries and even millenia. Thus, the effeciacy of an algorithm is vital.
We must accept the fact that some problems are unsolvable. It is impossible to solve them, even
with the most advanced technological advances in the future.
1. Turing machine
2. Stack (data type)
3. Theory of Computation
1. Is there a way to measure the efficacy of an algorithm without using a model of computation?
2. How can we train ourselves to become better algorithm creators?
3. Are there machines that can produce abstract algorithms to a problem in a language humans can understand?
BACK TO HOMEPAGE