## Basics

Theory of computation developed as a field as mathematicians and logicians tackled the question of whether there was a systematic way to solve any and every mathematical problem. The research conducted in the area eventually led to the creation of computers as we know them today.

In its most basic, computation is defined as (source: Merriam Webster) “the act or process of computing or calculating something”. In the context of computer science, when we talk about the theory of computation, we are referring to the area of computer science that focuses on solving problems via algorithms.

Of course, before we can proceed any further, we need to be able to define what an algorithm is.

(Source: Wikipedia) in mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms perform calculation, data processing, and/or automated reasoning tasks.

In simple English, we could consider this as a set of instructions, and in the context of computer science, as a set of instructions used by a computer to solved the problem at hand.

Currently, the most widely used model of computation is the Turing Machine model, named after the mathematician who proposed the concept, Alan Turing.

Theory of computation has three main branches: computability theory, automata theory/formal language theory and complexity theory. All three of these branches are linked by one fundamental problem: what are the limitations of computers.

The object of computability theory is to classify mathematical problems as ‘solvable’ or ‘unsolvable’. Mathematicians Kurt Godel, Alan Turing and Alonzo Church are credited with the discovery that there are certain mathematical problems that simply cannot be solved by computers.

Automata theory is a theoretical branch of computer science. It involves the definitions and properties of different models. These can be models used in text processing, in artificial intelligence, defining programming languages and many others. The primary focus of automata theory is to determine whether any one model is better able to solve problems than another.

Complexity theory is the study of how efficiently a problem can be solved. Problems are classified based on, in layman’s terms, “difficulty” – the more efficiently a problem can be solved, the ‘easier’ it is. This is the main focus of complexity theory – to determine which problems are computationally difficult to solve. This has many implications in a number of fields, e.g. cryptography.

In its most basic, computation is defined as (source: Merriam Webster) “the act or process of computing or calculating something”. In the context of computer science, when we talk about the theory of computation, we are referring to the area of computer science that focuses on solving problems via algorithms.

Of course, before we can proceed any further, we need to be able to define what an algorithm is.

(Source: Wikipedia) in mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms perform calculation, data processing, and/or automated reasoning tasks.

In simple English, we could consider this as a set of instructions, and in the context of computer science, as a set of instructions used by a computer to solved the problem at hand.

Currently, the most widely used model of computation is the Turing Machine model, named after the mathematician who proposed the concept, Alan Turing.

Theory of computation has three main branches: computability theory, automata theory/formal language theory and complexity theory. All three of these branches are linked by one fundamental problem: what are the limitations of computers.

**Computability theory**The object of computability theory is to classify mathematical problems as ‘solvable’ or ‘unsolvable’. Mathematicians Kurt Godel, Alan Turing and Alonzo Church are credited with the discovery that there are certain mathematical problems that simply cannot be solved by computers.

**Automata theory (also known as formal language theory)**Automata theory is a theoretical branch of computer science. It involves the definitions and properties of different models. These can be models used in text processing, in artificial intelligence, defining programming languages and many others. The primary focus of automata theory is to determine whether any one model is better able to solve problems than another.

**Complexity theory**Complexity theory is the study of how efficiently a problem can be solved. Problems are classified based on, in layman’s terms, “difficulty” – the more efficiently a problem can be solved, the ‘easier’ it is. This is the main focus of complexity theory – to determine which problems are computationally difficult to solve. This has many implications in a number of fields, e.g. cryptography.

## Links

https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html

http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf

http://www.cin.ufpe.br/~jjss/Introcuction%20to%20Theory%20of%20computation%20by%20Micheal%20Sipser%20Ist%20Ed..pdf

https://csustan.csustan.edu/~tom/SFI-CSSS/Lecture-Notes/Computation/computation.pdf

https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/basics.html

https://en.wikipedia.org/wiki/Theory_of_computation#History

http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf

http://www.cin.ufpe.br/~jjss/Introcuction%20to%20Theory%20of%20computation%20by%20Micheal%20Sipser%20Ist%20Ed..pdf

https://csustan.csustan.edu/~tom/SFI-CSSS/Lecture-Notes/Computation/computation.pdf

https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/basics.html

https://en.wikipedia.org/wiki/Theory_of_computation#History

## Questions

- When talking about complexity, why does cryptography require computational problems that are hard? Shouldn’t we always be looking for the easiest way to solve a problem?
- The Turing machine…I don’t fully understand it. Especially how it is analogous to computers.
- How do you classify problems as solvable or unsolvable? Try it? Or is there any way to know beforehand?