THE THEORY OF ALGORITHMS

• Document Type: CREST
• Collection: General CIA Records
• Document Number (FOIA) /ESDN (CREST): CIA-RDP80T00246A003500160001-5
• Release Decision: RIPPUB
• Original Classification: C
• Document Page Count: 23
• Document Creation Date: December 21, 2016
• Document Release Date: December 9, 2008
• Sequence Number: 1
• Publication Date: April 21, 1958
• Content Type: REPORT

Approved For Release 2008/12/09: CIA-RDP80T00246AO03500160001-5
Approved For Release 2008/12/09: CIA-RDP80T00246AO03500160001-5
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
THE THEORY OF ALGORITHMS
by
A.A. Markov
1. In mathematics it is accepted to understand by "algorithm" the precise p cription
of a definite calculational process leading from diversified initial data toe sought-
for result.
A typical example of an algorithm is the Euclidean Algorithm finding the
greatest common divisor of two natural numbers. An arbitrary pair of natural !-umbers
plays here the role of initial values; the prescription consists of a sequencelmade
i
up of a decreasing series of numbers, of which the first is the largest of the, two
given numbers, the second the smallest, the third is obtained as the remainder
division of the first by the second, the fourth as the remainder of the divisi
of the second by the third, etc. As long as there is no exact division withou
remainder, then the divisor of the last division is the desired result of the
algorithm - the greatest common divisor of two given natural numbers.
The following
in mathematics:
a) Precision
definiteness
of prescription,
of the algorithm;
b) the possibility of starting out with diversified and known
data -- the generality of the algorithm;
c) the directivity of the algorithm
result, in the long run obtained
of the algorithm.
r^,
2. The description of algorithms just proposed does not pretend to mathematical
preciseness. In recent times, however, mathematicians have contented themselves with
several indistinct notions which correspond to such a description. This was assumed
as soon as the term "algorithm" was met in mathematics only in positive expressions
of the following type: "for solution of such and such a problem one has an algorithm
and it consists of the following." No negative results, no theorems of the
impossibility of algorithms were to be demonstrated. at this stage on the strength of
the lack of precision of the notion of algorithm.
of the
n
algorithms determine their role
its obviou~ntflt
bounded iiiitial
obtaining of the particular desired
 3. In recent times a sequence of authors have been elaborating theories leading
naturally to a more precise notion of an algorithm. We have in view the works of
Kleene in the theory of recursive functions [21, 231, the works of Church in the
theory of A- conversion [14, 15, 17], the work of Turing in the theories of
computable numbers [31] and the work of Post in the theory of "finite conbinatbry
processes". [25]
This gave the possibility of setting up a sequence of important negative
results -- a theory of impossibility of algorithms. From here come almost all the
theorems of Church [16] about the unsolvability of common "decision problems" of
the predicate calculus. In the character of major concrete results it is possible
to produce a demonstration of the undecidability of a sequence of problems of the
general theory of associative systems [3, 5, 6, 7, 10, 20, 281 and theories of
Integral matrices [4, 8, 101. In recent times the most remarkable results of
this kind are possibly the publication of P.S. Novikov on the undecidability of
problems of the general theory of groups [12].
4. All such above mentioned negative results have fundamental values, for the
further development of mathematics, in so far as they show the problematical
dangerous potentialities of blind alleys,, thus preventing the possibility of going
into them.
The whole values for mathematics of the precision of the notion of algorithm
is made apparent, however, in connection with the problems of a constructive basis for
mathematics. As a basis for the precision of the notion of algorithm a definite
const active validity of arithmetic expressions can be given; for them the basis can
be the design and construction of mathematical logic - a constructive calculus of
expressions and a constructive calculus of predicates. Finally, the last field of
expression of the preciseness of the notion of algorithm is undoubtedly going to be
constructive analysis - the constructive theory of computable numbers and functions
of computable variables now being found in a state of intensive investigation.
5. All of the above mentioned theories in point 3 are sufficiently complicated in them-
selves, and they lead to the precision of the notion of algorithm in an indirect
way.
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
The theory of recursive functions [21, 23, 24] at the bottom deals with the
particular occurence of an algoritim, when the natural number play the role of
the initial variable, and the result of its application is a number. The translation
into this general result requires for this the arithmetization of the initial
data and of the results, which is arrived at by means of one or another "Godel
enumeration" [18]- a process consisting of the application of certain very definite,
but sufficiently complex algorithms.
The precision of the theory of algorithms fundamentally requires the theories
of A -conversion of Church, apart from the Godel enumeration, still a cumbersome
formal appartus.
The theory of ?computable numbers" of Turing, fundamentally undecidable in a
constructive manner in the notion of computable numbers,brings the interesting
to us precise notion of algorithm in an indirect way. The account of this theory
is given by its author [31]; the demonstration of Post [28], gives an incomplete
account.
Finally, the theory of finite combinatory processsof Post, closely related
to the theory of Turing, was not completely worked out and consists in the main
point of one definition (25].
In view of all that has been said the author considers it expedient immediately
to study the precision of the notion and to develop the general theory of algorithms
on the basis of this preciseness. Such a goal is pursued in the present monograph.*
The author thinks that he has succeeded satisfactorily in resolving the
setting up of the problem and that the theory of algorithms being given here
proceeds from a sufficiently simple and, together with that, ordinary difinition
of "normal algorithm". In such a measure this pretension justifiedly is left to
the reader to judge.
It was naturally easy to suppose that the theory being stated here of
"normal algorithms" is equivalent to the theory of algorithms based on the notion
of recursive function. It was shown by Y.K. Detlovs that this was actually so [1].
*A short resume of the monograph are given by notes [9] and [10]. In paper
[9] there occurs an annoying misprint: on page 185, in line 3 from the :tam, in
Approved For Release 2008/12/09: CIA-R DP80T00246A003500160001-5 place of ( should
na ri i ro : on aaae Loo Lrnr rv ur OLG{:6 oz nerrod should be a comma.
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
The present monograph is dedicated only to an account of the basic
theory of algorithms and its application to the demonstration of the undecidable
sequence of algorithmic problems. Another application of this theory which is
mentioned in point 4 merits a special book, which the author in the future
hopes to write.
6. The book is divided into six chapters, designated by Roman numerals, the
chapters are divided into sections, and the sections into paragraphs. In each
paragraph assertions (i.e., theorems, lemmas, corollaries) are enumerated
separately and formulas separately.
The numbers of formulas are written at their left and enclosed in
parentheses. The number of the paragraph is repeated at the left before the
number of the assertion - spearated by a period from the number of.the assertion.
The complete reference to an assertion consists of the number of the
chapter, the number of the section (preceded by the symbols 5 s), the number
of the paragraph, and the number of the operation. These numbers are separated
one from the other by periods, and all symbols are enclosed in square brackets.
For example, [i. 1 3.9.31 designates a reference to assertion 3 of paragraph 9
of section 3 of Chapter I. In reference th an assertion in the same chapter the
chapter number is omitted, in reference to an expression in the same, section the
number of the section is omitted.
References to formulae are handled analogouslyip with only the difference
that periods are not included in the parentheses with the number of the formula
and that in reference to a formula in the some paragraph the number of the
paragraph is omitted.
Certain references made simultaneously are enclosed in large square, brackets
and are separated from each other by coamas.
7. The contents of the book were expounded several times by the author in the
courses of lectures given at Leningrad University. As a result of the exchange of
opinion with the listeners and the accumulation of experience, the statement of
the subject was gradually perfected. The author wants with pleasure to think all
his listeners for their many critical cormnents, which played a large positive
role. In particular the author wants to thank R.V. Petropavlovski and N.A, Shanin.
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
Thesupervision of the book was elaborately overseen by V.A. Zalgaller
and N.A. Shanin,, who made a sequence of valuable comsentss having an affect on the
final edited manuscript. The author gives then his highest thanks for their
heavy labours.
The author cordially thanks the Publishing House of the Academy of Sgiences
of the USSR for its attentive, solicitous concern for the book.
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
. j
This chapter has an introductory, auxiliary chara@rs Ih it are
considered a sequence of notions -- "letters", "alphabets', "brordss, 'entkes",
etc. -- playing an essential role id the theory of algorithms.
A part of the material of this chapter is not necessary for our
nearest goal - the formulation of a definite notion of the normal algorithm
[II, f 3), -- but will be used significantly later on [III, f7 IV,f3,
IV. f 4, V, VI]. With this are included 5?5 and 6, as well as lemmas
4.2.2 - 5 4.2.6, 54.5.2 -$4.5.8. To the reader desiring to get mote
quickly into the heart of things -- into "normal algorithms" - we advisei
passing over the entire beginning of this material, to which he can later,
return for the purpose of completeness.
1. Letters
1. By letters we will mean symbols which we will consider in theiic
given application only as a whole.
In writing a book, the parts of the symbol .1 do not interest us, fOr
example, but only the entirety of the symbol. In this sense typographical
symbols are letters.
It is necessary to underline the conditional nature of this notion and
the dependence of its range on an agreed understanding. For example, the',
symbol a' might be considered both as a letter, and as a symbol consisting
of two parts a and t, according to adoption of this form by agreement.
2. In considering two.given letters, we will state that they are
either identical or different. For example, the first and sixth letters of
,the word "identical" are identical, and the first and sixth letters of the
word "different" are different.
The notion of identity and difference of letters is also conditional.
In particular in the identity of printed letters, much more rigid require4ients
are ordinarily presented than with the identity of letters written by hand; the
identity of the first is nearer to a gometrical 'equality" than the identity of
the second. The conditionality of'identity is shown especially sharply in
establishing the identity of printed letters with letters written by handw
 page 2
Approved For Release 2008/12/09 : CIA-RDP80T00246A003500160001-5
The possibility of establishment of the identity of letters allows
us, by the method of abstractive identification i to set up the notion ofl
abstract letters. The application of this abstraction consists in the
given case in that we will begin to talk of two identical letters as one
and the same letter.
For example in place of what would be said, that in the woad 'identicala
two letters enter which are identical with 'i', we shall say, 'the letter4i'
enters twice in the word 'identical'.' We here set up the notion of the abstract
letter III and shall consider the concrete letters identical with cif as
representatives of this one abstract letter. Abstract letters are those
letters which are considered the same to within identity.
Just as the application of abstractive identification is justified !here,
so is the condition observed; every letter being considered is identical with
itself (re9exivity of identity); if one letter is identical with another,
then the latter is identical with the first (symmetry of identity); .two
letters, identical with a third, are identical one to the other'(transitii}ity
of identity). In the following, idealizing several circumstances, we Will
consider these conditions strictly holding.
Developing abstractive identification in relation to.a letter,.we
consider concrete letters as representatives corresponding to the abstract
letter. Two concrete letters then and only-then represent one and the
same abstract letter when they are identical. In other words, the identi$r
of abstract letters will be expressed by the identification of their.
representatives.
#2. Alphabets
1. For every application of letters we deal with a certain not very,
large set of abstract letters. It is impossible to use very large sets of
abstract letters because of the amount of labor arising.in establishing t$e
identity and difference in the letters. In the natural organization
We mean by this that which is ordinarily accepted to be called merely
abstraction, the formation of an abstract notion by means of unification,
identification of objects, connected by *.relation of the type of equality
by means of correspondence (abstraction) from all differences of such obje ts.
Our terminology represents for us the most complete because it is applied n
contemporary mathematics to other types of abstract! s, tha is, correspondences
(ace, in particular, page 15 of the original, i.o. f 3.4 an 3.5.)
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
of the size of letters and the large number of their forms certainly
differences occur, for with difficulty the letters are distinguished-thQ
identity and difference of the letters lose their legibility*.
In place of this, it is impossible to indicate quantitative bound$
for legibility for practical application of sets of abstract letters,
that is, such a number N that sets of N abstract letters possess
practical applications and that such sets of, larger numbers of abstract
letters are impossible. We underline, however, that for every application
of letters we must deal with a certain finite set of abstract letters. Tk-is
finite set may be given in the form of a list of concrete letters, represent-
ing the abstract letters of the set. Lists of such a kind we will call
concrete a ohabets.
Without the existence of a limited community, it is possible to
impose in the concrete alphabet.being considered the condition-of absence
of repetitions, consisting in that, any two letters a,,peari ng in the con
crete alphabet are different. Further we always will suppose the condition
to hold, without stating it.
2. For relations in the concrete alphabet it is also pertinent to
set up an abstract identification. We will in this case abstract from not
only the concreteness of the representation of the abstract letters but
also the order of their appearance in the concrete alphabet. Accordingly
therefore we will agree to call the concrete alphabet A equivalent to the
concrete alphabet B.if every concrete letterer c M ng in B. e d convene .
In other words, we will call A equivalent to B if every abstract letter
represented by a letter occurring in A is represented also by a letter
occurOng in B, and vice versa.
Identifying equivalent concrete alphabets, speaking of two equivalent
concrete alphabets as of one. and the same alphabet, we arrive at the notion
of an abstract alphabet . We will consider every concrete alphabet as
representing a certain abstract alphabet. Two concrete alphabets then
and only then will represent one and the same abstract alphabet when they
are equivalent.
 An abstract alphabet is in essence the same as a set of abstract
letters. In the same way, every abstract alphabet A synonomously define
a set of abstract letters, and similarly a set of these abstract letters
representatives of which are met in some concrete alphabet, represents AJ
Every concrete set of abstract letters is defined in this sense by one and
only one abstract alphabet.
In consideration of abstract letters and abstract alphabets we will
ordinarily omit the auxiliary word "abstract', that is, will write merely
"letters" instead of "abstract letters" and "alphabet" instead of 'abstract
alphabet'. We will also, in speaking of representatives understand by that
those that are being represented. For example, we will, speak of the letter *,
understanding by this the abstract letter being represented by the symbol)
In other words, we will carry out abstractive identification with respect
to letters and alphabets without expressing this clearly, in correspondence
with ordinary practice.
In those cases where we are led to consider concrete letters and
concrete alphabets1 we will express this clearly by making use of the
auxiliary word "concrete'.
3. We will call letters, representatives of which are met in the
representative of the alphabet A, letters the alphabet A.
Every alphabet may, consistent with. the representation, be considered
as a set of letters of the alphabet. Corresponding with this we epeak'of,
the letters of the alphabet A that they represent A.
4. For consideration of arbitrary letters and of arbitrary alphabets
it is customary to make use of letters as symbols of these objects. We
thus used the letters A and B for designating (concrete and abstract)
alphabets. In the future we will designate alphabets by large Russian*
letters, letters by small Greek letters.
In speaking of "the letter a', "the letter Ps, etc,, we will under
stand the letters represented and not the letters a, 0 themselves, etc.
*Translator!s notes We will use instead large Greek letters.
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 In order to avoid confusion we will suppose that neither small
Greek letters nor large Russian* letters belong to the alphabet being
considered, a limit, it is understood, which is inessential.
5. We will use the notation
aEA
for expressing that the letter a belongs to the alphabet At the notation
a"T EA
for expressing that the letter a does not belong to the alphabet A; the
notation
A=8
for the expression of equivalence.of theme alphabets A and B.
6. We will suppose in thfi future that the symbols 2[ e, *.J s, and
do not occur as letters in the alphabet under consideration. We will
make use of these symbols in the following example to record the alphabet
by means of construction of its representatives. Writing one after
another in the same sequence the representatives of all letters of the
alphabet A under consideration, we will separate them by comas and
enclose all of them in curly brackets. This gives us one of the concrete',
alphabets representing A. Corresponding to our agreement, we will, in
speaking of this concrete alphabet, understand the abstract alphabet As,
and likewise consider this concrete alphabet as a record of the abstract
alphabet A.
For example, Is b, I is a concrete alphabet, representing the
abstract alphabet consisting of the letters as b, and c. Corresponding t4
out agreement, we will, however, understand by "the alphabet I a, b, c4 e
just that abstract alphabet, considering a (a, b, cJ s as its record.
The following alphabets will play an essential role in the futures'
A6 do b
A,(a, b, c, d3j
A2 = (a, b, c, d, ej f
A3 = fa, b, co d, e, it g, h, It j, k, 1,
Greek letters - translator.
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
Z= [I,*3;
= ffl, -3; a
M = LIs -: #, ?3,
T = jig - e'er 09
7. We will spaek of the alphabet B that it is an extension of the alphabet
A if every letter of the alphabet A is a letter of the alphabet B.
For example, A,,~is an extension of Ao; A2 is an extension of A1; A3 is
an extension of A2; j~ and are extensions of _ ; M is an extension of both
Si and A. and T is an extension of M.
Limiting consideration to those alphabets which do not contain the symbol
9=y we will use the notation
Ac B
as an expression that the alphabet B is an extension of the alphabet A.
In place of writing
ACB, Bar'
we can write shorter
Ac Ball.
In an analogous fashion we will use the notation
AC BC rc-
Ac Barr-4C E
We have in particular
AoC Ala A2C A3'
MOT
all~M.
The following assertions are evident.
7-1 IfACBa11 , then ACT'.
We will spear of the extension B of the alphabet A that it is an gss*nt&a
'
extension of the alphabet A if it is not identical with A. that is, if A is not
an sxtension of R
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
page 7.
8. Earlier yle.defined a concrete alphabet as. a list of concrete letter$.
In agreement with current understanding of the word "list", something must
always be written down. In the list of families residing in a certain house
there must be at least one family. If the house is empty, then the list of
dwellers ordinarily does not exist. It is possible, however to set up in
this case the list of inhabitants in_the house in the form of a piece of
paper on which is written down only the title "List of dwellers in house
no. 3 on NN street", and further nothing else. The possibility of a similar'
class of "empty" lists is expediently assumed in a definition of a concrete
alphabet, which we will do. This permits us to consider along with the non-,
empty alphabets, possessing at least one letter, the empty alphabet possessing
no letters at all. In our notation this will be written ass
f 31
It is expedient to consider that every alphabet is an extension of the
alphabet (3> .
3.4 words
1. We will call a sequence of concrete letters, written one after the
other a concrete. If the letters making up a concrete work R are represented
j ~.
by letters of the alphabet As, then we shall say that R is .1 concrete word
For example
algorithm
is a concrete word in the English alphabet.
It is evident that every concrete word in an alphabet A S. a concrete word
in every extension of this alphabet.
In writing a concrete word in a given alphabet we will present a serieslof
requirements of distinctness. Because the successive sequence of concrete
letters composing a word plays an essential role, it must be clear in this
sense that for any two such concrete letters, it must be clearly evident whio
of them stands at left (precedes) and which at right (follows).
 The beginning and end of a word must be clearly indicated. We will, to
this end, use quotation marks in ordinary examples, which evidently is
admissible if the quotation marks are not among the letters of the alphabets
being considered. Quotation marks besides are not considered as composing
parts of words, serve only for indicating their limits, and will often be
omitted.
9. That alphabet of all letters contained in at least one of the
alphabets A and B. we will designate as the union of the alphabets A and B;
the alphabet of all letters contained in both those alphabets will be designated
as their intersection. In an analogous manner we will define the union and
intersection of three or more alphabets.
The alphabet consisting of the letters of the alphabet A, but not con-
tained in the alphabet B, we will call the difference of the alphabets A and1B.
Considering only those alphabets in which the symbols N U as sn s,
do not appear, we will use the notation
AUB
to designate the union of the alphabets A and B; the notation
AeV B
for designating their intersection; the notation
A\B
for designating their difference; and the notations
AUB U
A/IB
for corresponding use in designating union and intersection of the alphabets
A, B. and P .
We have, evidently,
E UAUfD?=M
The use of quotation marks gives also the possibility of consideration of
empty words of the form
containing no concrete letters.
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
page 9.
We will consider every empty word as a word in every alphabet.
A very important future requirement will consist in the uniqueness of the
decomposition of a word into representative letters of the given alphabet H
the requirement of impossibility of "variant reading".
This is by no means always observed. For instance,the concrete word
a'a
in the alphabet f as, all, 'a9 can be considered as a sequence of the two concrete
letters representing the letters "a" and "'a" of this alphabet, or as a sequence
of the two concrete letters representing its letters "a'" and "a".
It is necessary to exclude completely the possibility of such varian
ing of words. This can be attained by imposing proper limits in the alphabets.
being considered and in the manner of writing the words in them.
It is possible, for example, to present the following two requirementssl
a) Every letter of the alphabet must be joined, that is, must be
formed without loss of contact of pen with paper;
b) in writing words an interval should be left between every two
neighboring letters.
The first of these two requirements imposes limits on the alphabets be"
considered, and the second on the manner.of writing words. It is clear thati
for observance of these requirements every concrete word in the alphabet being
considered will be decomposed into concrete letters in a unique way.
It is possible to have other systems of requirements, guaranteeing this)
uniqueness. However, requirements a) and b) are convenient in this regard, that
they admit unlimited construction of the union of the alphabets being consid reds
the union of any two alphabets satisfying requirement a) also satisfies that
requirement. Together with this requirement a) does not admit any essentials
limitations on the alphabet, because for every disconnected letter of the
alphabet, evidently, it is always possible to substitute a connected letter,!
different from all the remaining ones.*. henceforth we will understand by
*we remark, however, that the Russian printed alphabet does not satisfy'i
condition a) because of the disconnected letter "bI". Nevertheless, decompo ition
of a word in this alphabet into letters is unique. Ibis shows that conditions
a) and b) are by no means necesssrv for unieue written words.
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 page 10.
"alphabet", an alphabet satisfying condition a), by a "concrete word" a concrete
word written or printed with observance Of condition b), by "letter" a conr.octed
In the future we will designate words.(concrete as well as abstract)
capital English letters, understanding that these letters are not letters o1
the alphabet being considered. In speaking of "the word P," etc., we will
always have in mind the word designated by the letter P (and not the word
composed of the single letter P).
2. We will say of the. concrete words P and Q that they are equal if they.
consist of the identical concrete letters, identically ordered. Two empty
words we will besides also call equal, and an empty and a non-empty word wi41
be called unequal.
The concrete word set apart on a separate line on page 7 , is equal to'Ithe
concrete word "algorithm".
In ascertaining the equivalence of concrete words one can apply the following
method.
Let two concrete words P and Q be given. If they both are empty, then' they
are equal. If one is empty and the other not4 then they are not equal. If'
neither one nor the other of the two words is empty then we.compare their f rot
concrete letters. If they are not identical, then the words P and Q are no
equal. If these letters are shown to be identical, then we transfer into
consideration the concrete words P1 and Q1, obtained from P and Q as a resu#t
of cutting off the first concrete letter (that is, transferring the initial!
quotation mark across the first letter). P and Q are equal then and only
then when P1 and Q1 are equal. Considering P1 and Q1 in the same fashion a$
we considered P and Q, we either establish their equivalence and thus the e~uality
of P and Q; or we establish theirnon-equivalence, and this P and Q are not
equal; or finally we bring into consideration'the words P2 and Q2, obtained,
from P1 and Q1 be means of cutting off their first letter. We deal with th se
as we dealt with P1 and Q1, etc. This process of sequential determination :f
the identity of the first concrete letters must in the end be cut short, be4ause
P1 consists of one less concrete letter. than P, P2 of one less concrete letter
than P1, etc. It terminates in certain concrete words P. and %, for which'it is
Approved For Release 2008/12/09 : CIA=RDP80T00246AO03500160001-5 the initial words P I and
 The just described method of ascertaining the equality of concrete woriis
evidently possesses the three requirements, which we recorded as characteristic
of the features of algorithms [Introductionl]; it takes the form of an obvious
order, not being laid down arbitrarily; it is possible to apply it to different
initial data -- to every pair of concrete words in a given alphabet, it is
directed towards obtaining 'a certain result, being given in the end by the
correctness of the answer "yes" or "no" to the posed question of the equality
of the words. Conserving for the time being the imprecise notation of algorithm,,
we indeed will call this method the algorithm f eauallty 21 words.
It is not difficult to see that the equality of concrete words obeys the
laws of reflexivity, symmetry, and transitivity* even concrete word4s equal
to itself; if the concrete words P and Q are equal then the concrete words C}
and P are equal, to concrete words equal to a third are equal to each other.
2.1 Every concrete word that is e a to a concrete word i_n the aluhatt
Aisaword In A.
This follows immediately from the definition of concrete words in a givhen
alphabet and the equality of concrete words. '
We may now, applying abstractive identification, set forth the notion of
abstract word. The application of this abstraction will consist in a given
case in that we will speak equal concrete words as of one and the same word.
For example, we will say that one and the same word appears on the separate
line on page 7 . This signifies that we have set up the notion of the abstract
word "algorithm", and we are considering just that above-mentioned concrete
word as a representative of that one abstract word.
The application of abstractive identification with respect to words was
justified by the above mentioned laws of reflexivity, symmetryand transitivity
of the equivalence of words. It is connected with consideration of concrete
words as representatives of abstract words. Two concrete words in this case
then and only then represent one and the same abstract word when they are equal.
For expression of equality of concrete words, that is identity of the
abstract words represented by them, we will apply the ordinary symbol of equality.
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 4. Two representatives of one and the same abstract word P consist of
identical concrete letters, identically positioned. Abstract letters are
represented by these concrete letters, one and the same for both representatives,
and are defined, in this way, by the abstract word P. These abstract letter*
we will call letters of the word P.
Because we count any two empty concrete words as equivalent, we must consider
empty concrete words as representatives of one.abstract word - the empty bs a t
wo rd.
The empty abstract word does not have letters.
Understanding that the symbol "A s is not a letter of the alphabet being
considered, we will denote by this sign the empty abstract word.
We will say of the abstract word P. that it is an abstract d In i
alphabet A, if all letters of the word P are letters of the alphabet A. In
other words, the abstract word P is considered an abstract word in the alphabet
A if any (and thus every) representative of the word P is a concrete word in '$.
We will consider the empty abstract word as an abstract word in every
alphabet (even in the empty alphabet).
5. In the future in the consideration of alphabets, words, and algorithrs,
abstraction of ootential feasibility will play an important role.
This consists in abstraction from the real boundaries of our constructive
possibilities which stipulate the limitedrness of our lives in space and in time.
In application to alphabets this abstraction permits us to reason about the
size of the alphabet, and, in particular to be sure that new letters can be
adjoined to every alphabet. In the application to words we get in this way the
possibility to reason about the length of words as about their feasibility.
Their feasibility is potential; their representatives would be practically
feasible, if our life would endure sufficiently long and we would have sufficient
room and material for practical feasibility of these representatives. Adopti~g
these abstractions, we will understand in the future simply by "word' the abstract
otentially feasible word.
We will assume the possibility of reasoning about words (in this sense)
emmnla*alv_ at cn_ na uia raaenn.A nhnu,+ +ha nw.~+lnl ea.eibility of words in
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 which the essence of the abstraction of potential feasibility in a given
application consists. In particular, one may speak of the letters of a word
of its representatives, that It-is a word in a given alphabet, etc.
The abstraction of potential feasibility, as in abstractive identification,
is completely necessary for mathematics. On these two abstractions are based,
in particular, the notion of natural numbers.
6. Attaching on the right some representative of the word Q to sane
representative of the vr.rk P, we get a representative of a certain new word&
The latter, evidently, does not depend on the given set of representatives of
the words P and Q, tr,at is it is completely defined by these words. The word,
obtained in this wuf, resulting from the words P and Cl, we will denote as the
union of the words. P and Q.
For instrence, the word "input" is the union of the words "in" and "put"*
The abstraction of potential feasibility gives the possibility of considering
the union of any two words.
6.1. The union of pan iLvm.W r s ca be formed.
The following assertion is evident.
We will agree at present to designate by the symbol M the union of the
words P and Q.
The associative law of union is evident
(1) FAR = PtM
where P, Cl, and R are any words.
This gives the possibility for operating with the union to leave out the
upper lines, which we will hence forth do. Both parts of the equality (1) 411
be written then identically, in the form PQR. It is evident that PQR is thee,
word, the representative of which is obtained as the result of writing a sequence
at the beginning of which is a representative of the word P, then a certain
representative of the word Q, and filially, a certain representative of a wero R.
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
page 14.
We will call the word PQR the union of the words P. Q. Rz the word P FtS
the union of the words P, Q, R, S, etc.
It is clear that
(2) PA= P,:LL P = P
for every word P.
In the future we will often have to deal with a sequence of words, designated
by letters with numerical indices. The union of such words in a sequence of
increasing indices will be designated in the following manner.
For i > j the symbol
(3) PI ... pj
will always designate the empty word, independent of how the words Pi and are defined. For i = j this symbol will designate the word P11 if that word
is defined. For i < j the symbol (3) will denote the union of the words
Pi' P1+1' etc. through Pi inclusive, if all these words are defined.
We have, in this way
(4) Pi ... P1-1 =.1
(5) Pi ... pj = pi ... Pj-1P3
(6) = pips+l ,..Pj
in which the equalities (5) and (6) take place under the condition that 14 j
and that all words Pk are defined, where I .J k j J.
The union of several words designated by letters with indices will be
designated in a sequence of decreasing indices analogously.
For i < j the symbol
P1 ... Pj
will designate .4.j for 1 = j it will designate Pi, If PI is defined;
for i > j it will designate the union of the words Pia Pi-1' etc., through
Pj, inclusive, if all these words are defined.
We have in this way
P "' P = A
i i+l
Pi ... Pj = PIP1-1 ... Pj
_ Pi ... Pj+1Pj
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
the latter under the condition that 12 j and that all words Pk
are defined,
7. A concrete word, that is a sequence of concrete letters can ih parti-
cular, be one concrete letter. The abstract word representing it is then a~
abstract letter. In this way, every letter is a word, and in particular, every
letter of the alphabet A is a word in A.
Every non-empty word in the alphabet A is, evidently, either a letter of
this alphabet, or the union of several of. these letters; that is, the following
assertion holds.
7.1 Every non-empty word , alphabet A represented in the form
(1) 11 ... tka
where k > 0 and r 1, "'s t k are letters g tl~ia alphabet A1.
In view of requirements le) and lb), guaranteeing the impossibility of ',"variant
readings, the representation of word in the alphabet A in the form (1), where
Ell "'' Lk rr A, is unique, which is expressed by the following assertions
7.2. If ~1 ... tk ll ??`? 111 where k > 09.L > 0 and f ,-s4KJ
l1, ... 3-1 *A, then k =JL and
8. The number k, occuring in the representation (1) of the word defined
consistent with 7.2 synonymously with this word, we will call the length of'the
word P and designate by the symbol
[P' .
The empty word will be given the length zeros
Evidently every letter has length it
(2) [ tt =1 (f,e A).
It is also clear from the definition of.the length of a word that for all
non-empty words P and Q the equality holds
(3) [PQ' _ [p9 + [Q".
 page 16,
On the strength of 6(2) and (1) it is true even in the case when one o
the two words is empty.
8.1. The equality j], hods for art words P an Q.
On the strength of 7.1, (2) and(.% the following lemmae hold.
8.2. Every non-smU Vt word P n ie a habet A cann be reoresented Ste
form Q where 4V A , q j1 a word in A such that
(4) EQ9 = EP a - 1 .
8.3. E T non-emote word P the a et A can be reoresented in O e -Ln form QE where 1 A an g 11.j word in A such that (4) holds.
The following method of proof of general assertions about words in a
given alphabet A can be based on lemma 8.2.
Suppose we want to prove that all words in A possess a certain property 70,
We will prove for this the following two assertions:
1) The empty word possesses the property.p
2) If some word Q in A possesses property P.
then whatever letter t in the alphabet A. the word(Q also possesses the property VO ?
Then we may assert that every word in A possesses the property P.
In this fashion, on the strength of 1), we can assert that every word Of
length Q in A possesses property >0. because. is the only such'word. We{
will assume that we also have demonstrated that every word of length k - i,
for It > 0, possesses property 1? . We consider then some word P in A of length
It. It is empty, and therefore
P=IQ
for a certain letter ~ of the alphabet A and a certain word Q in A satisfying
condition
(4) [8.2]. Because EPa = It, we have
EQ ' = k - I . E(4)]
and this means that by hypothesis, Q possesses the property Consequently,
P possesses it E(5), 2]. By this we have proved that all words of length kin
A possess property A. as soon as every word of length It - 1 in A possesses it.
This permits, step by step, determination sequentially that property 7V is possessed
Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
 Approved For Release 2008/12/09 : CIA-RDP80T00246AO03500160001-5
by all words of length 1 in A, that it is possessed by all words of length
2 in As, etc, up to a word of arbitrary given length n inclusive. Consequen
property) is possessed.by every word in A, which was required to be prove.
The basis of just such methods of proof of general assertions about words
in a given alphabet is a variant of the method of mathematical induction . We
will call this the method of left indruction in A. Completely analogous,
the method of right induction in As obta$ned by replacing I Q in assertion)
2) by Q ? , is based on a similar method with the aid of lemma 8.3.
*we recall in connection with this that the spreading opinion about this,
that the basis of the method of mathematical induction certainly requires albasic
"axiom of mathematical inductions in our opinion, deeply wrong..