View source for Mathematical theory of computation

The last twenty years have witnessed most vigorous growth in areas of mathematical study connected with computers and computer science. The enormous development of computers and the resulting profound changes in scientific methodology have opened new horizons for the science of mathematics at a speed without parallel during the long history of mathematics.

The following two observations should be kept in mind. First, various developments in mathematics have directly initiated the  "beginning"  of computers and computer science. Secondly, advances in computer science have induced very vigorous developments in certain branches of mathematics. More specifically, the second of these observations refers to the growing importance of discrete mathematics — and only the very beginning of the influence of discrete mathematics is witnessed now (1990).

Because of reasons outlined above, mathematics plays a central role in the foundations of computer science. A number of significant research areas can be listed in this connection. It is interesting to note that these areas also reflect the historical development of computer science.

1) The classical computability theory initiated by the work of K. Gödel, A. Tarski, A. Church, E. Post, A. Turing, and S.C. Kleene occupies a central position. This area is rooted in mathematical logic (cf. [[Computable function|Computable function]]).

2) In classical formal language and automata theory, the central notions are those of an [[Automaton|automaton]], a grammar (cf., e.g., [[Grammar, generative|Grammar, generative]]), and a language (cf., e.g., [[Alphabet|Alphabet]]). Apart from developments in area 1), the work of N. Chomsky on the foundations of natural languages, as well as the work of Post concerning rewriting systems, should be mentioned here. It is, however, fascinating to observe that the modern theory of formal languages and rewriting systems was initiated by the work of the Norwegian mathematician A. Thue at the beginning of the 20th century! (Cf. [[Formal languages and automata|Formal languages and automata]]; [[L-systems|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627301.png" />-systems]].)

3) An area initiated in the 1960s is complexity theory. In it the performance of an algorithm is investigated. The central notions are those of a tractable and an intractable problem. This area is gaining in importance because of several reasons, one of them being the advances in area 4). (Cf. [[Complexity theory|Complexity theory]]; [[Algorithm, computational complexity of an|Algorithm, computational complexity of an]].)

4) Quite recent developments concerning the security of computer systems have increased the importance of cryptography to a great extent. Moreover, the idea of public-key cryptography is of specific theoretical interest and has drastically changed the ideas concerning what is doable in communication systems. (Cf. [[Cryptography|Cryptography]].)

Areas 1) through 4) constitute the core of the mathematical theory of computation. Many other important areas dealing with the mathematical foundations of computer science (e.g., semantics and the theory of correctness of programming languages, the theory of data structures, and the theory of data bases) have been developed.

All the areas listed above comprise a fascinating part of contemporary mathematics that is very dynamic in character, full of challenging problems requiring most interesting and ingenious mathematical techniques.

The basic question in the theory of computing can be formulated in any of the following ways: What is computable? For which problem can one construct effective mechanical procedures that solve every instance of the problem? Which problems possess algorithms for their solution?

Fundamental developments in mathematical logic during the 1930-s showed the existence of unsolvable problems: No [[Algorithm|algorithm]] can possibly exist for the solution of the problem. Thus, the existence of such an algorithm is a logical impossibility — its non-existence has nothing to do with ignorance. This state of affairs led to the present formulation of the basic question in the theory of computing. Previously, people always tried to construct an algorithm for every precisely formulated problem until (if ever) the correct algorithm was found. The basic question is of definite practical significance: One should not try to construct algorithms for an unsolvable problem. (There are some notorious examples of such attempts in the past.)

A model of computation is necessary for establishing unsolvability. If one wants to show that no algorithm for a specific problem exists, one must have a precise definition of an algorithm. The situation is different in establishing solvability: it suffices to exhibit some particular procedure that is effective in the intuitive sense. (The terms  "algorithm"  and  "effective procedure"  are used synonymously.)

One is now confronted with the necessity of formalizing a notion of a model of computation that is general enough to cover all conceivable computers, as well as the intuitive notion of an algorithm. Some initial observations are in order.

Assume that the algorithms that need formalization compute functions mapping the set of non-negative integers into the same set. Although this is not important at this point, one could observe that this assumption is no essential restriction of generality. This is due to the fact that other input and output formats can be encoded into non-negative integers.

After having somehow defined a general model of computation, denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627302.png" />, one observes that each specific instance of the model possesses a finitary description; that is, it can be described in terms of a formula or finitely many words. By enumerating these descriptions, one obtains an enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627303.png" /> of all specific instances of the general model of computation. In this enumeration, each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627304.png" /> represents some particular algorithm for computing a function from non-negative integers into non-negative integers. Denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627305.png" /> the value of the function computed by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627306.png" /> for the argument value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627307.png" />.

Define a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627308.png" /> by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m0627309.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

Clearly, the following is an algorithm (in the intuitive sense) to compute the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273010.png" />. Given an input <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273011.png" />, start the algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273012.png" /> with the input <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273013.png" /> and add one to the output.

However, is there any specific algorithm among the formalized <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273014.png" />-models that would compute the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273015.png" />? The answer is no, and the argument is an indirect one. Assume that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273016.png" /> would give rise to such an algorithm, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273017.png" /> is some natural number. Hence, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273018.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

A contradiction now arises by substituting the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273020.png" /> for the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273021.png" /> in both (a1) and (a2).

This contradiction, referred to as the dilemma of diagonalization, shows that independently of the model of computation — indeed, no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273022.png" />-model was specified — there will be algorithms not formalized by the model.

There is a simple and natural way to avoid the dilemma of diagonalization. So far the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273023.png" />-algorithms are assumed to be defined everywhere: For all inputs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273024.png" />, the algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273025.png" /> produces an output. This assumption is unreasonable from many points of view, one of which is computer programming; one cannot be sure that every program produces an output for every input. Therefore, one should allow also the possibility that some of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273026.png" />-algorithms enter an infinite loop for some inputs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273027.png" /> and, consequently, do not produce any output for such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273028.png" />. Moreover, the set of such values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273029.png" /> is not known a priori.

Thus, some algorithms in the list

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273030.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>

produce an output only for some of the possible inputs; that is, the corresponding functions are not defined for all non-negative integers. The dilemma of diagonalization does not arise after the inclusion of such partial functions among the functions computed by the algorithms of (a3). Indeed, the argument presented above does not lead to a contradiction because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273031.png" /> is not necessarily defined.

The general model of computation, now referred to as a [[Turing machine|Turing machine]], was introduced quite a long time before the advent of electronic computers. Turing machines constitute by far the most widely-used general model of computation. Other general models are Markov algorithms (cf. [[Normal algorithm|Normal algorithm]]), Post systems (cf. [[Post canonical system|Post canonical system]]), grammars, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273032.png" />-systems. Each of these models leads to a list such as (a3), where partial functions are also included. All models are also equivalent in the sense that they define the same set of solvable problems or computable functions.

Only the general question of characterizing the class of solvable problems has been considered here. This question was referred to as basic in the theory of computing. It led to a discussion of general models of computation.

More specific questions in the theory of computing deal with the complexity of solvable problems. Is a problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273033.png" /> more difficult than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273034.png" /> in the sense that every algorithm for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273035.png" /> is more complex (for instance, in terms of time or memory space needed) than a reasonable algorithm for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273036.png" />? What is a reasonable classification of problems in terms of complexity? Which problems are so complex that they can be classified as intractable in the sense that all conceivable computers require an unmanageable amount of time for solving the problem?

Undoubtedly, such questions are of crucial importance from the point of view of practical computing. A problem is not yet settled if it is known to be solvable or computable and remains intractable at the same time. As a typical example, many recent results in cryptography are based on the assumption that the factorization of the product of two large primes is impossible in practice. More specifically, if one knows a large number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273037.png" /> consisting of, for example, 200 digits and if one also knows that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273038.png" /> is the product of two large primes, it is still practically impossible, in general, to find the two primes. This assumption is reasonable because the problem described is intractable, at least in view of the factoring algorithms know at present. Of course, from a merely theoretical point of view where complexity is not considered, such a factoring algorithm can be trivially constructed.

Such specific questions lead to more specific models of computing. The latter are obtained either by imposing certain restrictions on Turing machines or else by some direct construction. Of particular importance is the finite automaton (cf. also [[Automaton, finite|Automaton, finite]]). It is a model of a strictly finitary computing device: The automaton is not capable of increasing any of its resources during the computation.

It is clear that no model of computation is suitable for all situations; modifications and even entirely new models are needed to match new developments. Theoretical computer science by now has a history long enough to justify a discussion about good and bad models. The theory is mature enough to produce a great variety of different models of computation and prove some interesting properties concerning them. Good models should be general enough so that they are not too closely linked with any particular situation or problem in computing — they should be able to lead the way. On the other hand, they should not be too abstract. Restrictions on a good model should converge, step by step, to some area of real practical significance. Typical examples are certain restrictions of abstract grammars especially suitable for considerations concerning parsing. The resulting aspects of parsing are essential in compiler construction.

To summarize: A good model represents a well-balanced abstraction of a real practical situation — not too far from and not too close to the real thing.

Formal languages constitute a descriptive tool for models of computation, both in regard to input-output format and the mode of operation. Formal language theory is by its very essence an interdisciplinary area of science; the need for a formal grammatical description arises in various scientific disciplines, ranging from linguistics to biology.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Salomaa,   "Formal languages" , Acad. Press  (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Rozenberg,   A. Salomaa,   "The mathematical theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062730/m06273039.png" /> systems" , Acad. Press  (1980)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  W. Kuich,   A. Salomaa,   "Semirings, automata, languages" , Springer  (1986)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Salomaa,   "Computation and automata" , Cambridge Univ. Press  (1985)</TD></TR></table>