Theory Of Computation – A great mathematical deal

Introduction

 

Computers play such an important part in our lives that formulating a“Theory Of Computation” threatens to be a huge project.

To narrow it down, we adopt an approach that seems a little old-fashioned in its simplicity but still allows us to think systematically about what computers do.

Here is the way we will think about a computer: It receives some input, in the form of a string of characters, it performs some sort of “computation”, and it gives us some output.

It’s very easy to try out computer efficiency that we will ask the computer can all be answered either yes or no.

For ex, we might  submit an input string and ask, “Is it a legal algebraic expression? “ At this point, the computer is playing the role of a language acceptor.

The language accepted is the set of strings to which the computer answers yes—in our example, the language of legal algebraic expressions. 

Accepting a language is approximately the same as solving a decision problem, by receiving a string that represents an instance of the problem and answering either yes or no.

Many interesting computational problems can be formulated as decision problems, and we will continue to study them even after we get to models of computation that are capable of producing answers more complicated than yes or no.

Now we look at the computations themselves: to say at the outset how sophisticated the steps carried out by the computer are allowed to be, and to see what sorts of languages can be accepted as a result.

Finite Automaton

 

A finite automaton is characterized by its lack of any auxiliary memory, and a language accepted by such a device can’t require the acceptor to remember very much information during its computation. 

A finite automaton proceeds by moving among a finite number of distinct states in response to input symbols.

Whenever it reaches an accepting state, we think of it as giving a “yes” answer for the string of input symbols it has received so far.

Languages that can be accepted by finite automata are regular languages; they can be described by either regular expressions or regular grammars, and generated by combining one element languages using certain simple operations.

Pushdwn Automaton

A language can be generated by a context-free grammar precisely if it can be accepted by a pushdown automaton, which is similar in some respects to a finite automaton but has an auxiliary memory that operates according to the rules of a stack.

Turing Machine

A Turing machine is not just the next step beyond a pushdown automaton. It is, according to the Church-Turing thesis, a general model of computation, potentially able to execute any algorithm.

Languages

Familiar languages include programming languages such as Java and natural languages like English, as well as unofficial “dialects” with specialized vocabularies, such as the language used in legal documents or the language of mathematics.

Special Thanks To Mr. John C. Martin for writing a book An Introduction to Languages and the Theory of Computation