View source for Computable function

A function the values of which may be computed with the aid of an effective procedure which is given in advance or by an [[Algorithm|algorithm]]. The characteristic feature of computational processes is the fact that the unknown quantities of the problem are successively computed from the given initial values by definite, pre-determined rules and instructions. The numerous available examples of computational processes in mathematics gave rise to an intuitive concept of a computational procedure. In the context of the general program for the foundation of mathematics, embarked upon in the 20th century, the need arose for an exact, as distinct from an intuitive, notion of algorithm. Exact definitions of computable functions, effective procedures and algorithms were given in various forms by D. Hilbert, K. Gödel, A. Church, S.C. Kleene, E.L. Post, A.M. Turing, and A.A. Markov.

The general idea underlying the different approaches to the establishment of rigorous mathematical definitions may be stated as follows. A detailed analysis is conducted of computational processes which are already known or which are conceivable, the important characteristics of these processes are revealed, and suitable mathematical analogues are found of these processes and their characteristic features. The realization of the different aspects of this idea is not unambiguous and results in different versions of the mathematical concept of an algorithm. The basic mathematical models of the concept of an algorithm are Turing machines, partial recursive functions, the normal algorithms of Markov, and others.

==Turing machines.==
Algorithms used in mathematics resemble machines working on separate lines which respond after a finite number of lines. Turing and Post described the concepts of abstract computers (cf. [[Computer, abstract|Computer, abstract]]) on which the computational processes may be modelled. A Turing machine (or a Turing–Post machine) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243301.png" /> consists of:

a) a finite alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243302.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243303.png" /> are arbitrary symbols; finite ordered sequence of symbols of the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243304.png" /> are called words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243305.png" />; the words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243306.png" /> serve to encode the initial problems, the intermediate computations and the answers obtained;

b) a finite list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243307.png" /> of elementary states which can be assumed by machine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243308.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c0243309.png" /> is considered to be the initial state of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433010.png" /> when it begins working, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433011.png" /> is the final state: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433012.png" /> is brought to state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433013.png" />, it ceases operating;

c) programs, consisting of individual commands <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433014.png" /> which have one of the forms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433015.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433017.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433018.png" /> is one of the symbols of motion — <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433019.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433020.png" />.

The configuration of the machine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433021.png" /> at a given moment of time is encoded by a word of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433022.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433024.png" /> are certain words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433025.png" /> (the empty word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433026.png" /> is written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433027.png" />). The configuration of the machine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433028.png" /> at a subsequent moment of time (after the completion of one time of work) is also coded by the word depending on the command <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433029.png" />:

if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433030.png" />, the word obtained is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433031.png" />;

if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433032.png" />, the word obtained is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433033.png" />;

if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433035.png" />, the word obtained is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433036.png" />;

if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433038.png" /> is the empty word, the word obtained is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433039.png" />.

The mode of operation of the machine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433040.png" /> may be described as follows. The inputs are coded with the aid of some initial configuration (here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433041.png" />); in accordance with the program of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433042.png" /> the following configuration is obtained, etc.; if at a certain moment the configuration obtained contains the final state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433043.png" />, the computation ends; the final configuration is decoded and constitutes the answer; if the machine never stops, the answer to the problem is considered to be indefinite.

Any computational procedure which may be reduced to the operation of a suitable Turing machine is intuitively effective. The converse of this proposition is the so-called Turing thesis: Any effective computational procedure can be realized on an appropriate machine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433044.png" />. This thesis cannot be demonstrated, since it contains two concepts — the rigorous mathematical definition of a Turing machine and the vague, intuitive concept of an effective procedure. If the Turing machines are made to model the computation of the values of a function whose domain of definition and whose range are sets of natural numbers, then one arrives at the concept of a computable function (on a Turing machine). See also [[Turing machine|Turing machine]].

==Partial recursive functions.==
All known examples of algorithms may be reduced to the problem of computing the values of a suitable function. Taking this feature as the fundamental property, Church, Gödel and Kleene defined a wide class of functions, which they named partial recursive. Let $F$ be the class of partial functions, with domains of definition and ranges of values in the set of natural numbers. The following operations are defined on the set $F$:

a) superposition (composition) of functions: If $f,\alpha_1,\ldots,a_m \in F$, then one says that the function
$$
\phi(x_1,\ldots,x_n) = f(\alpha_1(x_1,\ldots,x_n),\ldots,\alpha_m(x_1,\ldots,x_n))
$$
is obtained from $f,\alpha_1,\ldots,a_m$ by composition;

b) the $\mu$ or [[least-number operator]]: Let $f_1,f_2 \in F$; one says that a function $\psi$ is obtained from $f_1$ and $f_2$ with the aid of the $\mu$-operator, written as
$$
\psi(x_1,\ldots,x_n) = \mu y [f_1,f_2,(x_1,\ldots,x_n),y]
$$
if $f_1(x_1,\ldots,x_n,z)$ and $f_2(x_1,\ldots,x_n,z)$ are defined and are unequal for $z<y$ and if
$$
f_1(x_1,\ldots,x_n,y) = f_2(x_1,\ldots,x_n,y)
$$
and then 
$$
\psi(x_1,\ldots,x_n) = y \ .
$$

Clearly, if these operations are applied to functions the values of which one can compute, then there exist algorithms for computing the values of the functions $\phi$ and $\psi$. The following functions are considered to be the simplest: ${+},{\times}$, $\mathrm{pr}_i : ( x_1,\ldots,x_n) \mapsto x_i$, and
$$
k(x,y) = \begin{cases} 1 & \ \text{if}\  x < y \\ 0 & \ \text{otherwise} \end{cases} \ .
$$

There exist easy algorithms which serve to compute the values of the simplest functions.

A function $f$ is called partial recursive if it can be obtained by a finite number of steps from the simplest functions using the composition and the $\mu$-operator. A partial recursive function which is everywhere defined is called general recursive. The value of any partial recursive function may be effectively computed in the intuitive sense. The converse of this statement is known as Church's thesis: Any function the value of which can be effectively computed is partial recursive. Thus, according to Church's thesis, computable functions are partial recursive.

==The normal algorithms of Markov.==
Any given algorithm involves a certain alphabet, and the solution of a given problem is reduced to the processing of the words over this alphabet according to certain rules specified in advance. This approach to the theory of algorithms was developed by Markov, who presented the concept of a normal algorithm as the mathematical model of the concept of a computational procedure.

A normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433070.png" /> consists of a certain alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433071.png" /> and a finite ordered list of rules of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433072.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433073.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433074.png" /> are certain words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433075.png" />. Some of the rules are distinguished as final. A rule <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433076.png" /> is applied to a word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433077.png" /> as follows: The word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433078.png" /> is represented in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433079.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433080.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433081.png" /> are words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433082.png" /> which may also be empty; out of all such representations the one in which the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433083.png" /> is shortest is selected, and the result of the application of this rule to the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433084.png" /> is said to be the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433085.png" />. A normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433086.png" /> is applied to the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433087.png" /> as follows: The first rule which is applicable to the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433088.png" /> is applied, so a word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433089.png" /> is obtained; the first rule which is applicable to the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433090.png" /> is applied, so a word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433091.png" /> is obtained, etc. The result is a sequence of words which terminates after some final rule has been applied.

If the information is suitably coded, normal algorithms may be applied to the solution of various algorithmic problems. Any computational procedure modelled on a normal algorithm is effective in the intuitive sense. The converse of this statement is known as Markov's thesis: Any effective computational procedure can be modelled by a suitable normal algorithm. If the computation of the values of functions in the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433092.png" /> is modelled by normal algorithms, another concept of a computable function is obtained. Other more precise definitions of the concept of algorithms have been proposed (cf. [[Algorithm|Algorithm]]; [[Normal algorithm|Normal algorithm]]).

The following result on the equivalence of the various conceptions of the notion of algorithm has been demonstrated: The classes of functions computable on Turing machines and the partial recursive functions which are computable by Markov's normal algorithms (or similar classes of functions for other conceptions of the notion of algorithm) are identical. In the view of most mathematicians of our time, this class of functions may serve as the class of intuitively computable functions and is identified with it. Such an identification makes it possible to treat algorithmic problems as mathematical problems.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.I. Mal'tsev,   "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.M. Turing,   "On computable numbers, with an application to the Entscheidungsproblem"  ''Proc. London Math. Soc. (2)'' , '''42'''  (1937)  pp. 230–265</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  S.C. Kleene,   "Introduction to metamathematics" , North-Holland  (1951)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A.A. Markov,   "Theory of algorithms" , Israel Program Sci. Transl.  (1961)  (Translated from Russian)  (Also: Trudy Mat. Inst. Steklov. 42 (1954))</TD></TR></table>



====Comments====
The  "symbols of motion"  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024330/c02433093.png" /> stand for  "left" ,  "right"  and  "no move"  ( "stand" ), respectively.

More information can be found in the article [[Mathematical theory of computation|Mathematical theory of computation]].