Reasons of Studying Automata Theory

• to we of us know how we can computes the different problems given
• to study about its theory
• to we know behind the people who made this theory
• to know its different definitions
• to defined how importannt it is in our course we took
• to study the word problems

Computability Theory

       According to Herbert B. Enderton about his Computability theory, 
it  is the area of mathematics dealing with the concept of
an effective procedure—a procedure that can be carried out by following specific
rules. For example, we might ask whether there is some effective procedure—
some algorithm—that, given a sentence about the positive integers, will decide
whether that sentence is true or false. In other words, is the set of true sentences
about the positive integers decidable? Or for a much simpler example, the set of
prime numbers is certainly a decidable set. That is, there are quite mechanical
procedures, which are taught in the schools, for deciding of any given positive
integer whether or not it is a prime number.
More generally, consider a set S, which can be either a set of natural numbers
(the natural numbers are 0, 1, 2, . . .), or a set of strings of letters from a finite
alphabet. (These two situations are entirely interchangeable. A set of natural
numbers is very much like a set of base-10 numerals, which are strings of digits.
And in the other direction, a string of letters can be coded by a natural number
in a variety of ways. The best way is, where the alphabet has k symbols, to
utilize k-adic notation, which is like base-k numerals except that the k digits
represent 1, 2, . . . , k, without a 0 digit.) We say that S is a decidable set if
there exists an effective procedure that, given any natural number (in the first
case) or string of letters (in the second case) will eventually end by supplying
the answer: “Yes” if the given object is a member of S and “No” if it is not a member of S.

Complexity Theory

•        It may refer to Computational Complexity Theory a field in theoretical computer science and mathematics.

       It is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty. In this context, a computational problem is understood to be a task that is in principle amenable to being solved by a computer (which basically means that the problem can be stated by a set of mathematical instructions). Informally, a computational problem consists of problem instances and solutions to these problem instances. For example, primality testing is the problem of determining whether a given number is prime or not. The instances of this problem are natural numbers, and the solution to an instance is yes or no based on whether the number is prime or not.

•        The study of complex systems

• Complexity theory and organizations, the application of complexity theory to strategy

                Complexity theory has been used extensively in the field of strategic management and organizational studies. It is used in these domains to understand how organizations or firms adapt to their environments. The theory treats organizations and firms as collections of strategies and structures. When the organization or firm shares the properties of other complex adaptive systems - which is often defined as consisting of a small number of relatively simple and partially connected structures - they are more likely to adapt to their environment and, thus, survive. Complexity-theoretic thinking has been present in strategy and organizational studies since their inception as academic disciplines.

• Complexity economics, the application of complexity theory to economics

                   Complexity economics is the application of complexity science to the problems of economics. It is one of the four C's of a new paradigm surfacing in the field of economics. The four C's are complexity, chaos, catastrophe and cybernetics. This new mode of economic thought rejects traditional assumptions that imply that the economy is a closed system that eventually reaches an equilibrium. Instead, it views economies as open complex adaptive systems with endogenous evolution . Complex systems do not necessarily settle to equilibrium — even ideal deterministic models may exhibit chaos, which is distinct from both random (nondeterministic) and analytic behavior.

Automata Theory

        Automata are abstract mathematical models of machines that perform computations on an input by moving through a series of states or configurations. If the computation of an automaton reaches an accepting configuration it accepts that input. At each stage of the computation, a transition function determines the next configuration on the basis of a finite portion of the present configuration.
       Turing machines are the most general automata. They consist of a finite set of states and an infinite tape which contains the input and is used to read and write symbols during the computation. Since Turing machines can leave symbols on their tape at the end of the computation, they can be viewed as computing functions: the partial recursive functions. Despite the simplicity of these automata, any algorithm that can be implemented on a computer can be modeled by some Turing machine.
       Turing machines are used in the characterization of the complexity of problems. The complexity of a problem is determined by the efficiency of the best algorithm that solves it. Measures of an algorithm's efficiency are the amount of time or space that a Turing machine requires to implement the algorithm. A computation's time is the number of configurations involved in that computation, and its space corresponds to the number of positions on its tape that were used.