An approach to proving the fundamental results of the theory of recursive functions using specific algorithms is consider. For this, the basic constructions of the algorithm are describing exactly and Church's thesis for more narrow classes of algorithmically computational functions is specified (concretized). Using this approach, the belonging of functions to classes of algorithmically computable is argued by the construction of the corresponding algorithms. Ключові слова: теза Чорча, розв'язність, універсальна функція. Ключевые слова: тезис Черча, разрешимость, универсальная функция.
1) We assume that the simplest functions are calculated by the algorithms defined everywhere without using the operator while … do, and therefore belong to this class..
2) All functions that are calculated by the algorithms defined everywhere without using an operator while … do and in their calculation auxiliary functions use, which are calculated by the algorithms defined everywhere without using of the operator while … do also belong to this class. Thus, the following thesis is true.
Thesis 1. A class of functions which are calculated by algorithms defined everywhere without using of an operator while … do coincides with the class of primitive recursive functions.
2. A class of functions which are calculated by algorithms defined everywhere. This class is described as follows: 1) All primitively recursive functions belong to this class.
2) All functions which are calculated by algorithms defined everywhere and at their calculation the functions which are calculated by algorithms defined everywhere are used also belong to this class.. Thus, the following thesis is true.
Thesis 2. The class of functions which are calculated by algorithms defined everywhere coincides with the class of recursive functions.
3. A class of functions which are calculated by arbitrary algorithms. This class is described as follows: 1) All recursive functions belong to this class.
2) All functions which are calculated by arbitrary algorithms and at their calculation the functions which are calculated by arbitrary algorithms are used also belong to this class. Thus, the following thesis is true.
Thesis 3. The class of functions calculated by arbitrary algorithms coincides with the class of partially recursive functions.
Computability
We show how to prove the algorithmic computability of functions using the above theses. Suppose we need to prove that function
[ x / y], y 0 f ( x, y)
x, y 0 is primitive recursive function.
Consider the sequence Since the fraction [x/y] means how many times the number y is "placed" in the number x, then [x/y] is equal to the number of zeros in this sequence. Really, if, for example, y is twice "placed" in the number x, then 1y x, 2y x, … , [x/y] x, … , xy
x. 1y x = 0, 2y x = 0, а 3y x 0.
Therefore, the algorithm for calculating the function is as follows: function f(x, y) begin s = 0 if y = 0 then f = x else {for i = 1 to x if iy x = 0 then s = s + 1 f = s} end. Hence the function f(x, y) is primitive recursive function.
If all pairs of natural numbers are arranged in sequence
<0, 0>, <0, 1>, <1, 0>, <0, 2>, <1, 1>, <2, 0>, <0, 3>, … , that is, arrange all the pairs so that the pair <x, y> goes earlier than a pair <u, v> if or if then the relation
x + y < u + v, x + y = u + v and x < u,
<x, y> n, where n is the pair number in this sequence, specifies the bijection between the set of pairs and the set of natural numbers,.
This bijection is called the Cantor numbering of pairs of numbers and is denoted c(x, y), that is c(x, y) is the number of pair <x, y> in the Cantor sequence. The left and right elements of the pair <x, y> with number n define the functions l(n) and r(n), which are called the left and right coordinate functions.
We show that the functions с(x, y), l(n), r(n) are primitive recursive function. Really, the function с(x, y) is calculated by the following algorithm:
Given that l(n) n, r(n) n function l(n) is calculated by the algorithm: function с(x, y) begin
s = 0 for i = 0 to (x + y)
s = s + i for i = 0 to (x + y) {j = (x + y) i if x = i y = j then k = i} с = s + k end. function l(n) begin for i = 0 to n for j = 0 to n
if с(i, j) = n then l = i function r(n) begin for i = 0 to n for j = 0 to n
if с(i, j) = n then r = j end, end. and the function r(n) is calculated by an algorithm:
So, с(x, y), l(n) and r(n) are primitive recursive functions.
We show that the function
f(x) = [ex] is primitive recursive functions.
xSn < ex < x(Sn + 1/n!n), e = 1 + 1/1! + 1/2! + … + 1/n! + /n!n, 0 < <1,
Sn = 1 + 1/1! + 1/2! + … + 1/n!. lim (x(Sn 1/ n!n) x Sn ) 0 , then n [x(Sn 1/ n!n)] [x Sn )] 0 for some n, that is [x(Sn 1/ n!n)] [x Sn )] for some n.
So, in order to find the value of [ex], it is necessary to find the minimum n for which the previous equality is fulfilled and to put
[ex] = [хSn].
The graph of the function F(x1, …, xn) [1-3] is the set <x1, …, xn, F(x1, … , xn)>. We show that if the graph Gf of the everywhere defined function f(x1, … , xn) is a recursively enumerable set [1-3], then the function f is recursive Really, the graph Gf is a set of the form:
<f1(t), … , fn (t), g(t)>, where fi, g are primitive recursive functions. Then the value of the function f at any point can be calculated using the following algorithm: function f(x1, … , xn) begin i = 0 while f1(i) x1 … fn(i) xn
do i = i +1 f = g(i) end, hence, the function f is recursive.
Fundamental results of the theory of algorithms
Let be a system of partial functions of one argument. A partial function F(x, y) of two variables is called universal for the family if the following conditions are satisfied: 1. For each fixed i the function F(i, y) belongs to ; 2. For each function f(y) from there exists a number i such that for all y equality F(i, y) = f(y) is fulfilled.
It is known [1] that for the class of partially recursive functions of one argument there is a universal partially recursive function Kleene K(n, x).
If we mapp every natural number into the set of partially recursive functions K(n, x) then we get the numbering of the Kleene of partially recursive functions. The number n is called the Kleene number of the function K(n, x), which is also denoted by Kn.
Rice's theorem is true: the set A of Kleene numbers of functions belonging to a nonempty family of partially recursive functions of one argument which are differed from the set of all such functions, cannot be recursive. This theorem is used to substantiate the results on the algorithmic computability of functions.
For example, show that function f ( x ) 1, K ( x ,x )1
0 , in other cases is not algorithmically computational.
For this purpose the set M = {n0, n1, … } of Kleene numbers of partially recursive functions K(n0, x), K(n1, x), … such that K(n0, n0) = 1, K(n1, n1) = 1, … is considered. By Rice's theorem, the set M is nonrecursive. Suppose that there exists an algorithm which calculates the function f(x). Then the set M will be recursive. We receive a contradiction.
Algorithmic solvability. Consider problems for which there are no algorithms. Such problems will be called algorithmically unsolvable.
One of such algorithmically unsolvable problems is the stopping problem [1,3,5] which consists in the following: it is necessary to answer the question of whether there is an algorithm whose output for an arbitrary pair x, y of input natural numbers is 0, if K(x, y) is defined and 1 if K(x, y) is undefined. The existence of such an algorithm is equivalent to the existence of an algorithm whose output for an arbitrary pair x, y of input natural numbers is 0, if the algorithm for calculating partially recursive function f with Kleene number x stops at input y and 1, if the algorithm for calculating partially recursive function f with Kleene number x at input y works indefinitely. That is why this problem is called the stop problem.
Theorem 1. The stopping problem is algorithmically unsolvable.
Proof. It follows that the domain of the function K(x, y) is a nonrecursive recursively enumerable set.
Another algorithmically unsolvable problem is the belonging problem, which is as follows: it is necessary to answer the question about existence of an algorithm whose output for an arbitrary pair x, y of input natural numbers is 0 if x y and 1 if x y.
Theorem 2. The belonging problem is algorithmically unsolvable.
Proof. Really, the solvability of the affiliation problem means the recursiveness of the set of pairs <x, y> for which the equation K(x, t) = y has a solution. But it is not so.
Universal numerical sets. The set U of pairs of numbers (i, x) such that K(i, x) = 1 will be called the universal numerical set [4], that is
Theorem 3. The problem of belonging to the universal numerical set is algorithmically unsolvable. Proof. Really, the solvability of this problem means that the characteristic function
U = {(i, x), K(i, x) = 1}.
1, K (i, x) 1 U(i, x) =
0, K (i, x) 1 function f(x) begin . . . . . .
f = . . .
end, function f(x) begin i := 0 while U(x, x) = 1 do
i := i + 1 f := 1 end, is recursive. Let's show that this is not so. Really, if this function is recursive, then the function f (x), which is calculated by the algorithm is partially recursive functions, and, therefore, f(x) = K(n, x), for some n. Calculate this function for x equal to n.
If U(n, n) = 1, then it means, on the one hand, that K(n, n) is not defined (f(n) = K(n, n)). On the other hand, since U(n, n) = 1 K(n, n) = 1, then K(n, n) is defined. If U(n, n) 1, then it means, on the one hand, that K(n, n) is defined and K(n, n) = 1. On the other hand K(n, n) 1.
Universal set.of words. Let = {a1, …, an} be an alphabet. Each grammar above the alphabet can be represented by a word in the alphabet N, where N = { S, , , *}. For example, grammar G with rules {S aABb|Bbb, Bb C, AC aac} can be represented by a word
A1A2 … A4, where A1 = S a SSb, A2 = S Sbb, A3 = Sb S, A4 = SS aac.
The set of all such words will be called the base.
Universal set.of words [4] we will be called the set V of words A1A2 … Anw such that the word w is infered in the grammar G with rules A1, A2, … , An, that is
V = {A1A2 … Anw, S G w}.
It is clear that each grammar G generates recursively enumerable set (the set of all words that are infered in the grammar).
Therefore, a universal set.of words is a set of words A1A2 … Anw such that w belongs to the recursively enumerable set, which is generated by the grammar with rules A1, A2, … , An, that is
V = {A1A2 … Anw, w recursively enumerable set, which is generated G}.
We can show that the theorem 4 holds.
Theorem 4. The problem of belonging to a universal set of words is algorithmically unsolvable.
The Post correspondence problem. Let's look at another example of an algorithmically unsolvable problem. It is called the Post correspondence problem [4].
Let is a set of pairs of words in the alphabet . It is said that a set of pairs of words have a solution if there exist such a sequence
P = {(v1, w1), (v2, w2), … , (vn, wn)} (vi1 , wi1 ),(vi2 , wi2 ),..., (vik , wik )
vi1vi2 ... vik wi1 wi2 ... wik , of pairs of words that that is, the word formed by the left coordinates of the sequence of pairs coincides with the word formed by the right coordinates of the sequence of pairs.
Post correspondence problem is to answer the question of the existence of an algorithm whose output for an arbitrary input set P of word pairs is 0 if P has a solution and 1 if P has no solution.
Theorem 5. Post correspondence problem is algorithmically unsolvable.
Proof. By an arbitrary word A1A2 … Anw of universal set.of words we build Post correspondence problem according to the following rules: – a pair (FS, F), where F is a special symbol, is added to the set of pairs of words; – for each symbol a of the alphabet we add pairs (a, a) to the set of pairs of words; – for each nonterminal symbol S, S, …, S… we add pairs (S, S), (S, S), …, (S…, S…) to the set of pairs of words; – for the word w we add a pair (E, wE) to the set of pairs of words, where E is a special symbol; – for each rule Ai = u v we add a pair (v, u) to the set of pairs of words; – we add a pair (, ) to the set of pairs of words.
It can be shown that
A1A2 … Anw V the set of pairs has a solution.
Therefore, if the Post correspondences problem is algorithmically solvable, then the problem of belonging to a universal set.of words will also be algorithmically solvable. And this is not so.
Unsolvability in the class of context-free grammars (problem of ambiguity). This problem is to answer the question of the existence of an algorithm whose output for an arbitrary input context-free grammar G is 0 if G is ambiguous and 1 otherwise.
Let
Q = {(v1, w1), (v2, w2), … , (vn, wn)} is a set of pairs of words in the alphabet . For the set A = {v1, v2, … , vn} of the left components of the elements from Q we construct the context-free grammar GA with one nonterminal A and a set of terminal symbols I, where I = {a1, a2, … , an} and I = . Alphabet I is called the alphabet of index symbols. The rules of grammar GA have the following form: This grammar generates language
A v1Aa1 v2Aa2 … vnAan v1a1 v2a2 … vnan.
L(GA ) { i1 ... im aim ... ai1 , 1 i1, ..., im n} .
B w1Ba1 w2Ba2 … wnBan w1a1 w2a2 … wnan.
L(GB ) {wi1 ...wim aim ... ai1 , 1 i1, ..., im n} .
Similarly for the set B = {w1, w2, … , wn} of right components from Q we build a context-free grammar GB with one nonterminal B and a set of rules
GAB = ({S, A, B}, {a1, a2, … , an}, P(GA) P(GB), S).
The following theorem holds.
Theorem 6. Grammar GAB is ambiguous Q has a solution.
Proof. Let i1, …, im is a solution of a set of pairs of words Q. Consider two inferences in grammar GAB: S A i1 Aai1 i1 i2 Aai2 ai1 ... i1 i2 ... im aim ... ai2 ai1 , S B wi1 Bai1 wi1 wi2 Bai2 ai1 ... wi1 wi2 ... wim aim ... ai2 ai1 .
Since i1, …, im is a solution, then
i1 i2 ... im wi1 wi2 ... wim , that is, these two inferences generate the same word. Because these inferences are different, the grammar GAB is ambiguous.
On the other hand, for a given terminal word, there is no more than one inference in the grammar GA and no more than one inference in the grammar GB. Therefore, a terminal word can have two different inference only if one of them begins with S A and continues with the inference in the grammar GA, and the other begins with S B and continues with the inference in the grammar GB.
This word ends with symbols aim ... ai1 for some m 1. Since
i1 i2 ... im wi1 wi2 ... wim , then i1, …, im is a solution.
Theorem 7. The problem of ambiguity of context-free grammar is algorithmically unsolvable.
Proof. If the problem of ambiguity is solvable, then Post correspondence problem would be solvable. And this is not so.
Theorem 8. Problem
L(G1) L(G2) = is algorithmically unsolvable.
Proof. Consider an arbitrary Post correspondence problem in the alphabet and construct context-free grammars GA and GB. Since L(GA) L(GB) is a set of solutions of the Post correspondence problem, then
L(GA) L(GB) = Post correspondence problem has no solution.
Therefore, if this problem is solvable for arbitrary G1 and G2, then Post correspondence problem will also be solvable. But this is not so.
Theorem 9. Problem
L(G1) = L(G2) is algorithmically unsolvable.
Proof. Let's show that L(GA ) is a context-free grammar. Really, there exists an algorithm which for any input word in the alphabet I gives an answer to the question of the word's belonging to the language L(GA ) . It is based on the fact that such a word must end by index symbols aim ... ai1 , nd the prefix of this word must be a word i1 ... im . If this is not so, then the input word does not belong to L(GA ) . Therefore, there exists an algorithm which for an arbitrary input word in the alphabet I gives an answer to the question about belonging this word to the language L(GA ) . Thus, this language is recursively enumerable set, that is, generated by context-free grammar.
Consider an arbitrary Post correspondence problem in the alphabet and construct context-free grammars G1 and G2, which generate languages LA LB and (Σ I )* , respectively, where I is still the alphabet of index symbols. The equality
LA LB LA LB is holds
Therefore, in L(G1) there are no words which are solutions of Post correspondence problem. Language L(G2) contains all words from (Σ I )* . So,
L(G1) and L(G2) coincide when the Post correspondence problem has no solution.
It follows that if the equivalence problem for context-free languages is algorithmically solvable, then Post correspondence problem will be solvable. And this is not so.
Theorem 10. Problem L(G1) L(G2) is algorithmically unsolvable.
Proof. Let G1 be a context-free grammar, which generates language ( I)* and G2 be a context-free grammar, which generates language LA LB , where I is an alphabet of index symbols. Then
L(G1) L(G2) LA LB = ( I)*.
That is, L(G1) L(G2) when the Post correspondence problem has no solution. It follows that if the inclusion problem for context-free languages is algorithmically solvable then the Post correspondence problem will be solvable. But this is not so.
Conclusions. Thus, an approach whith help of which the belonging of functions to classes of algorithmically calculated can be argued by constructing appropriate algorithms, unlike to algebraic terms, are proposed. It can be useful for programmers of different ages who want to learn the basics of computational theory and the theory of algorithms, as well as students of relevant specialties. It should also be noted that the proposed approach based on the concretization of Church's thesis allows to achieve a clearer formulation of various problems and processes for their solution. This is achieved primarily through the so-called PseudoPascal macro operators for the implementation of the simplest mechanical operations.
Provotar Oleksandr Ivanovych Doctor of Physical and Mathematical Sciences, Professor, Professor of Taras Shevchenko National University of Kyiv, number of publications in domestic publications – 120, in foreign – 30, h index 4, ORCID number 0000-0002-6556-3264, t. +38-050-444-17-35, email: aprowata1@bigmir.net. Provotar Olga Oleksandrivna, junior researcher at the V.M. Glushkov Cybernetics Institute NAS of Ukraine, number of publications in domestic publications – 10, in foreign – 2, ORCID number 0000-0002-6591-3615, email: provotar@huspi.com.