## Thursday, 1 October 2020

Theory of computation, computing theory, computational theory, or computational theory in computer science studies the possibility of efficiently solving presented problems with the help of a computer and studies what a computer can do a calculation now and the possibility of its development in the future.

### So it can be divided into:

Computational theory and computational complexity theory. And they both deal with mathematical models of computation.

To accomplish a systematic study of computation, computer scientists create abstract mathematical models from computers called computation model.

There are several types of these models in use, but the most important and common one is the Turing machine.

A Turing machine can be imagined as a home computer with limited memory capacity, and only small scattered segments of this memory can be accessed.

Turing machines are easy to visualize and design and can be analyzed and studied to demonstrate the expected results and thus represent a reasonable model for the calculation process.

The condition of limited memory is very necessary because this is what makes the Turing machine realistic, and makes the predictions of the Turing machine acceptable. Any problem that can be solved by Allow Turing can also be solved by any personal computer with sufficient memory.

In theoretical computer science and mathematics, computing theory is the discipline concerned with the effectiveness of solving problems through a computational model using an algorithm. This field is divided into three main sections:

Autonomous operation theory and languages, computational theory, and the theory of computational complexity, which are related to the following question: «What are the basic capabilities and limitations of computer devices?

In order to make an accurate study of computing, computer scientists work with a mathematical abstraction of computers called model computing.

Several models are used but the most popular is the Turing machine. Computer scientists study the Turing machine because it is easy to configure, can be analyzed and used to prove results, and because it represents what many consider to be the most powerful "logical" arithmetic model possible.

The possibility of infinite memory capacity seems to be an unattainable advantage, but any problem resolved by a Turing machine will always require only a limited amount of memory. So in principle, any problem that can be (decided) solved by a Turing machine can thus be solved by a computer that has a limited amount of memory.

### Formal language theory

Language theory Of Computation is the branch of mathematics concerned with describing languages ​​as a set of operations on the alphabet. It is closely related to autonomous theory because autonomous machines are used to generate and recognize formal languages. There are many types of formal languages, each of which gives the language more complex specifications than the previous one, for example:

Chomsky's hierarchy and each corresponds to a pattern of recognizable autonomous machines. Formal languages ​​are the preferred method for describing any problem that needs to be computed because autonomous machines are used as models for computation.

### Computational theory

The computational theory deals primarily with the question of the extent to which a problem is solvable on a computer. The assertion that the stopping issue is not possible to solve with a Turing machine is one of the most important results in computer theory, as it is an example of a concrete problem that is easy to occur but impossible to solve with a Turing machine. The computational theory relies for the most part on the results of the stopping problem.

Another important step in computational theory is Rice's mathematical view, which demonstrates that for all the non-trivial properties of subfunctions, a decision cannot be made whether a Turing machine computes a fractional function by means of that property.

The computational theory is closely related to the branch of mathematical logic called the theory of regression, which removes the limitations on the study of computation models only that can be reduced to Turing's model. Many mathematicians and computational theorists who study regression theory refer to it as computational theory.