top of page

A Brief Introduction to Theory of Computation



Theory of Computation is Computer Science branch which is concerned with how the problems can be solved using Algorithms and how efficiently they can be solved. It allow us to search and explore the nature of computations more closer to find out new theories and apply them to computer science.


Here are some of the Computational problems that are considered:

  1. What can and what cannot be computed.

  2. what is the speed of the computation.

  3. How much amount of memory is used during such computations.


Importance:

  1. Write efficient algorithms that can run in computing devices.

  2. Programming Language research and development.

  3. Efficient compiler design and construction.


Below are some of the basic terminologies used in Theory of Computation.

  • symbols: Symbols is the smallest building block which can be any alphabet, letter or picture.

  • Alphabets : These are set of symbols which are always finite.

  • String: String is finite sequence of symbols from some alphabet. String is generally denoted as 'w' and length of string as |w|

  • Note: If the number of Σ’s is represented by |Σ|, then number of strings of length n, possible over Σ is |Σ|n.

  • Languages: A language is a set of strings, chosen from some Σ* or we can say- A language is a subset of Σ* . A language which can be formed over ‘ Σ ‘ can be Finite or Infinite.


Types of Theory of Computation:

The Theory of Computation is made up of 3 branches.

  1. Automata Theory

  2. Computability Theory

  3. Complexity Theory


Automata Theory:

This is for designing and analyzing computing devices such as biocomputers and quantum computers. These models are essential in several areas of computation. Through automata, computer scientists are able to understand how machines compute functions and solve problems and more importantly, what it means for a function to be defined as computable or for a question to be described as decidable .


This automaton consists of states and transitions. The State is represented by circles, and the Transitions is represented by arrows.


There are four major families of automaton :

  • Finite-state machine

  • Pushdown automata

  • Linear-bounded automata

  • Turing machine


Computability Theory:

Computability Theory defines whether a problem is solvable by any machine. There are many problems which are computable and some are not. Computations are done by various computation models depending on the nature of problem.


Complexity Theory:

Complexity theory is to study the cost of solving the problem with resources like time and space; needed as the metric. The running time of algorithm varies with the inputs and usually grows with the size of input.



Models of Computation Machines :

1- Turing machines : It is the most common machine used in imperative programming languages in computation, it has an unlimited supply of paper tape that can write on and read back. It takes an input symbol and does 3 thing according to the symbol and the current state. The first thing is that it prints something on the tape, then it moves the tape either left or right by one cell, and then convert it to a new state.

2- Combinatory logic : A theory that is connected to logic, has many applications in computer science and mathematics disciplines.

3- Lambda calculus : functional programming languages are based on Lambda-calculus computational model, in functional programming we only need to modify the representation of the information, but we do not have to produce anything in general programming.

4- Abstract rewriting systems (ARS) : It is the most general notion that can be applied on a set of objects and rules to specify transform them. In history, there have been some formalizations of rewriting in abstract setting, this is due to the fact that some notions are equivalent.




The Tech Platform



0 comments
bottom of page