Introduction

The branch of theoretical computer science and mathematics known as theory of computation is concerned with the questions of what kinds of problems can be solved with an algorithm using a model of computation, how effectively they can be solved and to what degree (such as approximate versus precise solutions). There are three main branches to the field: Formal languages, automata theory, computability theory and computational complexity theory are all connected by the question, "which fundamental capabilities and drawbacks do computers have? A mathematical abstraction of computers known as a model of computation is used by computer scientists to carry out a thorough investigation of computation. The turing machine is the model that is examined the most frequently, though there are other models in use. The turing machine is studied by computer scientists because it is easy to formulate, can be analyzed and used to demonstrate results and represents what many people believe to be the most powerful "reasonable" model of computation (see church turing's thesis). Although any decidable problem that can be solved by a Turing machine will always require only a finite amount of memory, it may appear that the potentially infinite memory capacity is an unrealistic property. So, in theory, a computer with a finite amount of memory can solve any problem that a turing machine can solve (decide).

Description

The study of abstract machines or more appropriately, abstract "mathematical" machines or systems as well as the computational problems that these machines can solve is known as automata theory [1]. The term "automata" refers to these abstract machines. The word automata come from the Greek word which means something is doing something independently. Because the automata are frequently categorized according to the class of formal languages they are able to recognize, automata theory is also closely related to formal language theory. A formal language can be represented by an automaton as a finite or infinite set. Proofs of computerability and theoretical models of computing machines are both based on automata [2]. The study of languages as a series of operations performed on an alphabet is the focus of language theory, a mathematical subfield. Because automata are used to generate and recognize formal languages, it is closely related to automata theory. There are several classes of formal languages, each of which corresponds to a class of automata that recognizes it and allows for more complex language specification than the one before it, i.e. the Chomsky hierarchy. For any problem that must be computed, formal languages are the preferred method of specification because automata serve as models for computation. The main focus of computability theory is the extent to which a problem can be solved using a computer [3]. Because it is an illustration of a concrete problem that is both simple to formulate and impossible to solve using a turing machine, the statement that the halting problem cannot be solved by a Turing machine is one of the most significant findings in computability theory. The halting problem result serves as the foundation for a lot of computability theory. Rice's theorem, which states that for all non-trivial properties of partial functions, it is undecidable whether a turing machine can compute a partial function with that property, was another significant development in computability theory [4]. Recursion theory, a subfield of mathematical logic that goes beyond the Turing model as the only model of computation that can be studied, is closely related to computability theory. Computability theory is the term used by many mathematicians and computational theorists who study recursion theory [5]. Complexity theory takes into account not only whether or not a problem can be solved on a computer at all, but also how quickly it can be solved. There are two main considerations: Time complexity and space complexity refer to the number of steps required to carry out a computation and the amount of memory required for that computation, respectively.

Computer scientists express the time or space required to solve the problem as a function of the size of the input problem in order to determine how much time and space an algorithm requires [6]. For instance, as the list of numbers gets longer, it gets harder to find a particular number among them. If we state that the list contains n numbers, it may be necessary to examine each number in order to locate the desired one if the list is not sorted or indexed in any way. As a result, we can say that the computer must take a series of steps that increase in size linearly to solve this problem. Computer scientists have adopted Big O notation, which enables functions to be compared in a manner that ensures that specific aspects of a machine's construction do not need to be taken into consideration, but rather only the asymptotic behavior as problems become larger.

Conclusion

This has been done in an effort to simplify the issue at hand. As a result, the solution to the problem in our previous example calls for displaystyle O(n)O(n) steps. The question of whether a particular broad class of problems, known as NP, can be efficiently solved is perhaps the most pressing open problem in all of computer science. The P versus NP problem was named one of the seven millennium prize problems by the Clay mathematics institute in 2000. This topic is further discussed at complexity classes P and NP. Stephen Cook, the recipient of the turing award, provided the official problem description. A theoretically intriguing idealization of a computer is the register machine. There are a number of variations. The majority of them have only decrementation (combined with a conditional jump) and incrementation (and halting) as instructions and each register can hold a natural number of any size. Godel numbering methods can be used to explain why turing machines do not have an infinite (or dynamically growing) external store: The possibility of representing something complicated (such as a sequence, matrix, etc.) is made possible by the fact that each register contains a natural number by a large enough natural number the number theoretical foundations of these techniques can establish ambiguity in both representation and interpretation.

References

1. Kubica BJ (2012) A class of problems that can be solved using interval algorithms. Computing 94:271-280

   [Crossref] [Google Scholar]

2. Jackson B, Scargle JD, Barnes D, Arabhi S, Alt A, et al. (2005) An algorithm for optimal partitioning of data on an interval. IEEE Signal Process Lett 12:105-108

   [Crossref] [Google Scholar]

3. Hochba DS (1997) Approximation algorithms for NP-hard problems. ACM Sigact News 28:40-52

   [Crossref] [Google Scholar]

4. Surif J, Ibrahim NH, Dalim SF (2014) Problem solving: Algorithms and conceptual and open-ended problems in chemistry. Procedia Soc Behav Sci 116:4955-4963

   [Crossref] [Google Scholar]

5. Villarrubia G, de Paz JF, Chamoso P, de la Prieta F (2018) Artificial neural networks used in optimization problems. Neurocomputing 272:10-16

   [Crossref] [Google Scholar]

6. Wand M (1987) A simple algorithm and proof for type inference. Fundam Inform 10:115-121

   [Crossref] [Google Scholar]