Introduction to Theory of Computation
This course is on the Theory of Computation, which tries to answer the following questions:
- What are the mathematical properties of computer hardware and software?
- What is a computation and what is an algorithm ? Can we give rigorous mathematical definitions of these notions?
- What are the limitations of computers? Can "everything" be computed? (As we will see, the answer to this question is "no".)
Purpose of the Theory of Computation: Develop formal mathematical models of computation that reflect real-world computers.
This field of research was started by mathematicians and logicians in the 1930's, when they were trying to understand the meaning of a "computation". A central question asked was whether all mathematical problems can be solved in a systematic way. The research that started in those days led to computers as we know them today.
Nowadays, the Theory of Computation can be divided into the following three areas: Complexity Theory, Computability Theory, and Automata Theory.
The book in numbers
rate scoreNothing yet...