Namespaces
Variants
Actions

Difference between revisions of "Normal algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
{{TEX|done}}
 
The name attached to algorithms (cf. [[Algorithm|Algorithm]]) of a certain precisely characterized type. Together with recursive functions (cf. [[Recursive function|Recursive function]]) and Turing machines (cf. [[Turing machine|Turing machine]]), normal algorithms have become known as one of the most suitable refinements of the general intuitive idea of an algorithm. The concept of a normal algorithm was developed in 1947 by A.A. Markov in the course of his research on the identity problem for associative systems (see [[Associative calculus|Associative calculus]]). The detailed definition and general theory of normal algorithms are set forth in [[#References|[1]]] (Chapts. I–V); see also [[#References|[2]]] (Chapts. I–VII).
 
The name attached to algorithms (cf. [[Algorithm|Algorithm]]) of a certain precisely characterized type. Together with recursive functions (cf. [[Recursive function|Recursive function]]) and Turing machines (cf. [[Turing machine|Turing machine]]), normal algorithms have become known as one of the most suitable refinements of the general intuitive idea of an algorithm. The concept of a normal algorithm was developed in 1947 by A.A. Markov in the course of his research on the identity problem for associative systems (see [[Associative calculus|Associative calculus]]). The detailed definition and general theory of normal algorithms are set forth in [[#References|[1]]] (Chapts. I–V); see also [[#References|[2]]] (Chapts. I–VII).
  
Every normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673901.png" /> works in a certain [[Alphabet|alphabet]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673902.png" /> and gives rise to a well-defined process performed on words (cf. [[Word|Word]]). The specification of this alphabet occurs in the definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673903.png" /> as an obligatory constituent part, and in the situation in question one says of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673904.png" /> that it is a normal algorithm in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673905.png" />. Every normal algorithm in a fixed alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673906.png" /> is completely determined by indicating its scheme — an ordered finite list of substitution formulas in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673907.png" />. Every such formula is in essence an ordered pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673908.png" /> of words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n0673909.png" />. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739010.png" /> is called the left and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739011.png" /> the right part of the formula. Among the formulas of a given scheme some are specially distinguished and are declared to be conclusive. As a rule, in the scheme of a normal algorithm a conclusive formula is written in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739012.png" /> and an inconclusive one in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739013.png" />.
+
Every normal algorithm $\mathfrak A$ works in a certain [[Alphabet|alphabet]] $A$ and gives rise to a well-defined process performed on words (cf. [[Word|Word]]). The specification of this alphabet occurs in the definition of $\mathfrak A$ as an obligatory constituent part, and in the situation in question one says of $\mathfrak A$ that it is a normal algorithm in the alphabet $A$. Every normal algorithm in a fixed alphabet $A$ is completely determined by indicating its scheme — an ordered finite list of substitution formulas in $A$. Every such formula is in essence an ordered pair $(U,V)$ of words in $A$. Here $U$ is called the left and $V$ the right part of the formula. Among the formulas of a given scheme some are specially distinguished and are declared to be conclusive. As a rule, in the scheme of a normal algorithm a conclusive formula is written in the form $U\to\cdot V$ and an inconclusive one in the form $U\to V$.
  
A normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739014.png" /> in an alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739015.png" /> is a prescription for constructing, starting from an arbitrary word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739016.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739017.png" />, a sequence of words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739018.png" /> according to the following rule. The word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739019.png" /> is taken as the initial term <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739020.png" /> of the sequence and the construction process continues. Suppose that for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739021.png" /> the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739022.png" /> has been constructed and that the process of constructing the sequence in question is not yet complete. If in the scheme of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739023.png" /> there are no formulas with left parts occurring in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739024.png" />, then one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739025.png" /> equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739026.png" />, and the process of constructing the sequence is considered complete. But if in the scheme of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739027.png" /> there are formulas with left parts occurring in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739028.png" />, then one takes as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739029.png" /> the result of substituting the right part of the first of these formulas for the first occurrence of its left part in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739030.png" /> (cf. [[Imbedded word|Imbedded word]]); here the process of constructing the sequence is taken to be complete if the substitution formula to be applied at this stage is conclusive and it continues otherwise. If the process of constructing the relevant sequence terminates, then one says that the normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739031.png" /> in question is applicable to the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739032.png" />. The last term <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739033.png" /> of the sequence is the result of applying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739034.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739035.png" /> and is denoted by the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739036.png" />. One says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739037.png" /> transforms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739038.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739039.png" /> and writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739040.png" />. A normal algorithm in any extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739041.png" /> is said to be a normal algorithm over this alphabet.
+
A normal algorithm $\mathfrak A$ in an alphabet $A$ is a prescription for constructing, starting from an arbitrary word $P$ in $A$, a sequence of words $P_i$ according to the following rule. The word $P$ is taken as the initial term $P_0$ of the sequence and the construction process continues. Suppose that for some $i\geq0$ the word $P_i$ has been constructed and that the process of constructing the sequence in question is not yet complete. If in the scheme of $\mathfrak A$ there are no formulas with left parts occurring in $P_i$, then one puts $P_{i+1}$ equal to $P_i$, and the process of constructing the sequence is considered complete. But if in the scheme of $\mathfrak A$ there are formulas with left parts occurring in $P_i$, then one takes as $P_{i+1}$ the result of substituting the right part of the first of these formulas for the first occurrence of its left part in $P_i$ (cf. [[Imbedded word|Imbedded word]]); here the process of constructing the sequence is taken to be complete if the substitution formula to be applied at this stage is conclusive and it continues otherwise. If the process of constructing the relevant sequence terminates, then one says that the normal algorithm $\mathfrak A$ in question is applicable to the word $P$. The last term $Q$ of the sequence is the result of applying $\mathfrak A$ to $P$ and is denoted by the symbol $\mathfrak A(P)$. One says that $\mathfrak A$ transforms $P$ into $Q$ and writes $\mathfrak A(P)=Q$. A normal algorithm in any extension of $A$ is said to be a normal algorithm over this alphabet.
  
There are strong reasons to suppose that the concept of a normal algorithm is an adequate precise version (formalization) of the general idea of an [[Algorithm in an alphabet|algorithm in an alphabet]]. More accurately, one may assume that for every algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739042.png" /> in any alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739043.png" /> one can construct a normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739044.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739045.png" /> that transforms an arbitrary word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739046.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739047.png" /> into the same result as the original algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067390/n06739048.png" />. This convention is known in the theory of algorithms as the normalization principle. The formalization of the concept of an algorithm on the basis of that of a normal algorithm turns out to be equivalent to other known formalizations (see, for example, [[#References|[3]]]). As a consequence, this normalization principle turns out to be equivalent to the [[Church thesis|Church thesis]], which proposes to assume that the concept of a [[Partial recursive function|partial recursive function]] is an adequate formalization of the non-formal, intuitive, concept of a computable arithmetic function (cf. [[Computable function|Computable function]]).
+
There are strong reasons to suppose that the concept of a normal algorithm is an adequate precise version (formalization) of the general idea of an [[Algorithm in an alphabet|algorithm in an alphabet]]. More accurately, one may assume that for every algorithm $\mathfrak A$ in any alphabet $A$ one can construct a normal algorithm $\mathfrak B$ over $A$ that transforms an arbitrary word $P$ in $A$ into the same result as the original algorithm $\mathfrak A$. This convention is known in the theory of algorithms as the normalization principle. The formalization of the concept of an algorithm on the basis of that of a normal algorithm turns out to be equivalent to other known formalizations (see, for example, [[#References|[3]]]). As a consequence, this normalization principle turns out to be equivalent to the [[Church thesis|Church thesis]], which proposes to assume that the concept of a [[Partial recursive function|partial recursive function]] is an adequate formalization of the non-formal, intuitive, concept of a computable arithmetic function (cf. [[Computable function|Computable function]]).
  
 
Originating in the first instance in connection with algebraic problems, normal algorithms have proved to be a convenient working tool in much research requiring a precise notion of an algorithm, especially when the basic objects of study are not of arithmetical nature and allow for an appropriate representation in the form of words in certain alphabets (such as situations in [[Constructive analysis|constructive analysis]], for example).
 
Originating in the first instance in connection with algebraic problems, normal algorithms have proved to be a convenient working tool in much research requiring a precise notion of an algorithm, especially when the basic objects of study are not of arithmetical nature and allow for an appropriate representation in the form of words in certain alphabets (such as situations in [[Constructive analysis|constructive analysis]], for example).

Latest revision as of 15:08, 24 December 2018

The name attached to algorithms (cf. Algorithm) of a certain precisely characterized type. Together with recursive functions (cf. Recursive function) and Turing machines (cf. Turing machine), normal algorithms have become known as one of the most suitable refinements of the general intuitive idea of an algorithm. The concept of a normal algorithm was developed in 1947 by A.A. Markov in the course of his research on the identity problem for associative systems (see Associative calculus). The detailed definition and general theory of normal algorithms are set forth in [1] (Chapts. I–V); see also [2] (Chapts. I–VII).

Every normal algorithm $\mathfrak A$ works in a certain alphabet $A$ and gives rise to a well-defined process performed on words (cf. Word). The specification of this alphabet occurs in the definition of $\mathfrak A$ as an obligatory constituent part, and in the situation in question one says of $\mathfrak A$ that it is a normal algorithm in the alphabet $A$. Every normal algorithm in a fixed alphabet $A$ is completely determined by indicating its scheme — an ordered finite list of substitution formulas in $A$. Every such formula is in essence an ordered pair $(U,V)$ of words in $A$. Here $U$ is called the left and $V$ the right part of the formula. Among the formulas of a given scheme some are specially distinguished and are declared to be conclusive. As a rule, in the scheme of a normal algorithm a conclusive formula is written in the form $U\to\cdot V$ and an inconclusive one in the form $U\to V$.

A normal algorithm $\mathfrak A$ in an alphabet $A$ is a prescription for constructing, starting from an arbitrary word $P$ in $A$, a sequence of words $P_i$ according to the following rule. The word $P$ is taken as the initial term $P_0$ of the sequence and the construction process continues. Suppose that for some $i\geq0$ the word $P_i$ has been constructed and that the process of constructing the sequence in question is not yet complete. If in the scheme of $\mathfrak A$ there are no formulas with left parts occurring in $P_i$, then one puts $P_{i+1}$ equal to $P_i$, and the process of constructing the sequence is considered complete. But if in the scheme of $\mathfrak A$ there are formulas with left parts occurring in $P_i$, then one takes as $P_{i+1}$ the result of substituting the right part of the first of these formulas for the first occurrence of its left part in $P_i$ (cf. Imbedded word); here the process of constructing the sequence is taken to be complete if the substitution formula to be applied at this stage is conclusive and it continues otherwise. If the process of constructing the relevant sequence terminates, then one says that the normal algorithm $\mathfrak A$ in question is applicable to the word $P$. The last term $Q$ of the sequence is the result of applying $\mathfrak A$ to $P$ and is denoted by the symbol $\mathfrak A(P)$. One says that $\mathfrak A$ transforms $P$ into $Q$ and writes $\mathfrak A(P)=Q$. A normal algorithm in any extension of $A$ is said to be a normal algorithm over this alphabet.

There are strong reasons to suppose that the concept of a normal algorithm is an adequate precise version (formalization) of the general idea of an algorithm in an alphabet. More accurately, one may assume that for every algorithm $\mathfrak A$ in any alphabet $A$ one can construct a normal algorithm $\mathfrak B$ over $A$ that transforms an arbitrary word $P$ in $A$ into the same result as the original algorithm $\mathfrak A$. This convention is known in the theory of algorithms as the normalization principle. The formalization of the concept of an algorithm on the basis of that of a normal algorithm turns out to be equivalent to other known formalizations (see, for example, [3]). As a consequence, this normalization principle turns out to be equivalent to the Church thesis, which proposes to assume that the concept of a partial recursive function is an adequate formalization of the non-formal, intuitive, concept of a computable arithmetic function (cf. Computable function).

Originating in the first instance in connection with algebraic problems, normal algorithms have proved to be a convenient working tool in much research requiring a precise notion of an algorithm, especially when the basic objects of study are not of arithmetical nature and allow for an appropriate representation in the form of words in certain alphabets (such as situations in constructive analysis, for example).

References

[1] A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[2] A.A. Markov, N.M. [N.M. Nagornyi] Nagorny, "The theory of algorithms" , Kluwer (1988) (Translated from Russian)
[3] E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)


Comments

In 1936–1937 A.M. Turing formulated the thesis that his formalization of the intuitive notion of effective computation in terms of Turing numbers coincided precisely with the intuitive notion of computability. After several different formalizations turned out to be equivalent, A. Church extended Turing's thesis to the effect that all strong enough formalizations will turn out to cover precisely Turing's concept (Church's thesis).

How to Cite This Entry:
Normal algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Normal_algorithm&oldid=43554
This article was adapted from an original article by N.M. Nagornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article