GentleRex
Induction example
Intro to Theory of Computation
Reg lang properties
Pumping Lemma
decidability and MORE..
   
 


The subject matter that is associated to the above titles all deals with the construction of an idealized computer called a computational model. The simpliest model is called the finite state machine or finite automaton. There are really three central areas that are related and support each other when you investigate concepts around the subject of  computation which is automata, computability and complexity. They all support one fundamental question:

What can i do with a computer?

Examining from the position of Complexity theory you examine the perspective of :

What is a hard problem and what is not?

To completely define this question really takes you well into the topic... a long story short is that some problems have well defined answers (like 1+1) but others are not so straghtforward and may take exhaustive computational resources to provide a solution. As such we rely on a taxonomy-based approach to define what can and cannot be solved (easily) and more specifically what properties do they have that support this position.

Computability takes this further by categorizing problems that cannot be proved to be answered- it is important to note that such problems scale up so fast that even with our ever increasing power of computers we still cannot solve them. to the complete understanding and master of this subject matter is to ultimately come up to the conclusion that there are problems that will never be solved - not now or 1M years from now - now that is really HARD (actually well beyond it)! Therein lies the distinction between these two subcategories of computation as complexity determines between easy and hard , but computability determines between solvable or unsolvable (decidable!).

Automata Theory is the means of representing mathematical models that ultimately lead to conclusions of complexity and computability. To begin to study the subject of computation this is your starting point - as you begin to learn about languages (as automata supports what we know about language definitions - not just computer programming languages - every language in the world can be represented in such a fashion) you see the means of distinction ultimately lead to the definition and realization of what we can do with computers and what we cannot (didn't a famous actor quote " every man needs to know his limitations" ?