Theory of Computation: Layman’s view

Introduction

Theory of computation is a subject to understand if

” A problem can be solved by models of computation”

if a problem can be solved then

“how efficiently the problem can be solved by models of computation”

Models of Computations

Set of certain operations used in computation and their costs

e.g.

Turing Machine

http://www.worldofcomputing.net/theory/turing-machine.html

Finite State Machines

http://infolocata.com/cgi-sys/suspendedpage.cgi

Recursive Functions

https://mitpress.mit.edu/sicp/full-text/sicp/book/node15.html

Lambda Calculus

http://wiki.western.edu/mcis/index.php?title=CIS_Seminar/Lambda_Calculus

Combination Logic

http://www.tutorialbyte.com/academics/DM/Logic/Tautology.aspx

Cellular Automation

http://natureofcode.com/book/chapter-7-cellular-automata/

Abstraction Rewriting System

Branches of Theory of Computation:

• Theory of Computation
  • Automatat Theory & Languages
  • Computability Theory
  • Computational Complexity Theory

” WHAT ARE THE FUNDAMENTAL CAPABILITIES AND LIMITATIONS OF COMPUTERS ?”