Namespaces
Variants
Actions

Difference between revisions of "Algorithm, representation of an"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
a0118301.png
 +
$#A+1 = 15 n = 0
 +
$#C+1 = 15 : ~/encyclopedia/old_files/data/A011/A.0101830 Algorithm, representation of an,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''coding of an algorithm''
 
''coding of an algorithm''
  
 
A [[Constructive object|constructive object]] of a certain kind (as a rule, a natural number or a word) containing complete information about the algorithm, coded in accordance with the rules laid down for this type of algorithm. A coding of an algorithm is usually so defined that the procedures for obtaining the coding of the original algorithm and obtaining the original algorithm from its coding are as simple as possible.
 
A [[Constructive object|constructive object]] of a certain kind (as a rule, a natural number or a word) containing complete information about the algorithm, coded in accordance with the rules laid down for this type of algorithm. A coding of an algorithm is usually so defined that the procedures for obtaining the coding of the original algorithm and obtaining the original algorithm from its coding are as simple as possible.
  
The coding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118301.png" /> of a [[Normal algorithm|normal algorithm]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118302.png" /> over an alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118303.png" /> (not containing the letters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118304.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118305.png" />) is defined as a word over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118306.png" /> which is obtained as follows [[#References|[1]]]. In each substitution formula of the scheme of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118307.png" /> the arrow is replaced by the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118308.png" />, the point (if any) by the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a0118309.png" />, and the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183010.png" /> is written at the end of the word thus formed. The resulting words are then written out, one after the other, in the same sequence as that of their respective substitution formulas in the scheme of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183011.png" />. In actual fact, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183012.png" /> is merely a scheme of the normal algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183013.png" />, written in a somewhat different form — viz. as a word. For reasons connected with the technical details of the definition of a normal algorithm, another type of coding of a normal algorithm is somewhat more convenient — the so-called record of a normal algorithm [[#References|[1]]], which is the result of translating the words of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183014.png" /> into some two-letter alphabet (usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011830/a01183015.png" />). The coding of the program of a [[Turing machine|Turing machine]] can be carried out in a similar manner. The role of the coding of a [[Recursive function|recursive function]] is played by the Gödel number of the system of equations which define this function [[#References|[2]]].
+
The coding $  \mathfrak A  ^ {I} $
 +
of a [[Normal algorithm|normal algorithm]] $  \mathfrak A $
 +
over an alphabet $  A $(
 +
not containing the letters $  \alpha , \beta $
 +
and $  \gamma $)  
 +
is defined as a word over the alphabet $  A \alpha \beta \gamma $
 +
which is obtained as follows [[#References|[1]]]. In each substitution formula of the scheme of $  \mathfrak A $
 +
the arrow is replaced by the letter $  \alpha $,  
 +
the point (if any) by the letter $  \beta $,  
 +
and the letter $  \gamma $
 +
is written at the end of the word thus formed. The resulting words are then written out, one after the other, in the same sequence as that of their respective substitution formulas in the scheme of $  \mathfrak A $.  
 +
In actual fact, $  \mathfrak A  ^ {I} $
 +
is merely a scheme of the normal algorithm $  \mathfrak A $,  
 +
written in a somewhat different form — viz. as a word. For reasons connected with the technical details of the definition of a normal algorithm, another type of coding of a normal algorithm is somewhat more convenient — the so-called record of a normal algorithm [[#References|[1]]], which is the result of translating the words of $  \mathfrak A  ^ {I} $
 +
into some two-letter alphabet (usually $  \{ 0, 1 \} $).  
 +
The coding of the program of a [[Turing machine|Turing machine]] can be carried out in a similar manner. The role of the coding of a [[Recursive function|recursive function]] is played by the Gödel number of the system of equations which define this function [[#References|[2]]].
  
 
In any formalization of the general concept of an algorithm, its coding is so defined that it (in fact, the algorithm coded by it) might be included in the inputs for the algorithms of this type. This makes it possible to demonstrate the so-called  "theorems on universal algorithms" , dealing with the realizability of algorithms whose codings model the operation of any algorithm of this type.
 
In any formalization of the general concept of an algorithm, its coding is so defined that it (in fact, the algorithm coded by it) might be included in the inputs for the algorithms of this type. This makes it possible to demonstrate the so-called  "theorems on universal algorithms" , dealing with the realizability of algorithms whose codings model the operation of any algorithm of this type.

Latest revision as of 16:10, 1 April 2020


coding of an algorithm

A constructive object of a certain kind (as a rule, a natural number or a word) containing complete information about the algorithm, coded in accordance with the rules laid down for this type of algorithm. A coding of an algorithm is usually so defined that the procedures for obtaining the coding of the original algorithm and obtaining the original algorithm from its coding are as simple as possible.

The coding $ \mathfrak A ^ {I} $ of a normal algorithm $ \mathfrak A $ over an alphabet $ A $( not containing the letters $ \alpha , \beta $ and $ \gamma $) is defined as a word over the alphabet $ A \alpha \beta \gamma $ which is obtained as follows [1]. In each substitution formula of the scheme of $ \mathfrak A $ the arrow is replaced by the letter $ \alpha $, the point (if any) by the letter $ \beta $, and the letter $ \gamma $ is written at the end of the word thus formed. The resulting words are then written out, one after the other, in the same sequence as that of their respective substitution formulas in the scheme of $ \mathfrak A $. In actual fact, $ \mathfrak A ^ {I} $ is merely a scheme of the normal algorithm $ \mathfrak A $, written in a somewhat different form — viz. as a word. For reasons connected with the technical details of the definition of a normal algorithm, another type of coding of a normal algorithm is somewhat more convenient — the so-called record of a normal algorithm [1], which is the result of translating the words of $ \mathfrak A ^ {I} $ into some two-letter alphabet (usually $ \{ 0, 1 \} $). The coding of the program of a Turing machine can be carried out in a similar manner. The role of the coding of a recursive function is played by the Gödel number of the system of equations which define this function [2].

In any formalization of the general concept of an algorithm, its coding is so defined that it (in fact, the algorithm coded by it) might be included in the inputs for the algorithms of this type. This makes it possible to demonstrate the so-called "theorems on universal algorithms" , dealing with the realizability of algorithms whose codings model the operation of any algorithm of this type.

If a coding of an algorithm is a permissible input for the algorithm, this algorithm is called self-applicable if it is applicable to its own coding, and not self-applicable otherwise. It is possible to show, with the aid of a variant of the Russell paradox (cf. Antinomy), which is applicable to this situation, that the algorithmic problem which then arises — to wit, how to recognize self-applicable algorithms among other algorithms of this type — is not solvable by an algorithm of this type. This result forms the base of numerous theorems on the unsolvability of algorithmic problems.

The length of the code of an (encoding of an) algorithm is a natural measure of the complexity of an algorithm (the amount of memory which is required to remember the program of the algorithm) (cf. Algorithm, computational complexity of an; Algorithm, complexity of description of an).

References

[1] A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[2] S.C. Kleene, "Introduction to metamathematics" , North-Holland & Noordhoff (1951)
How to Cite This Entry:
Algorithm, representation of an. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Algorithm,_representation_of_an&oldid=19157
This article was adapted from an original article by N.M. Nagornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article