UDC 681.3 ELEMENTS OF CONCRETE ALGORITMICS: COMPUTABILITY AND SOLVABILITY О.І. Provotar, О.О. Provotar Taras Shevchenko national university of Kyiv Abstract. 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. Ключові слова: теза Чорча, розв’язність, універсальна функція. Ключевые слова: тезис Черча, разрешимость, универсальная функция. Key words: Church thesis, solvability, universal function. Анотацiя. Розглядається підхід до доведення фундаментальних результатів теорії рекурсивних функцій за допомогою використання конкретних алгоритмів. Для цього точно описуються основні конструкції алгоритму і переформульовується (конкретизується) теза Чорча для більш вузьких класів алгоритмічно обчислюваних функцій. За допомогою такого підходу належність функцій до класів алгоритмічно обчислюваних аргументується побудовою відповідних алгоритмів. Аннотация. Рассматривается подход к доказательству фундаментальных результатов теории рекурсивных функций с помощью использования конкретных алгоритмов. Для этого точно описываются основные конструкции алгоритма и уточняется (конкретизируется) тезис Черча для более узких классов алгоритмически вычислительных функций. С помощью такого подхода принадлежность функций к классам алгоритмически вычислимых аргументируется построением соответствующих алгоритмов. Introduction Everyone knows Church's thesis [1-3] that the class of algorithmically calculated functions coincides with the class of partially recursive functions. The class of partially recursive functions is determined mathematically accurately. Therefore, this thesis can be used both to prove the algorithmic computability of functions and to prove that the function is not algorithmically computable. To do this, we only need to show that such a function belongs to the class of partially recursive functions and in this case it is algorithmically calculated, or does not belong and, accordingly, is not algorithmically calculated. It is pretty difficult to show the algorithmic computability of functions by its belonging to the class of partially recursive functions, except for the simplest functions. In addition, in each case it requires the construction of a mathematical model of the function in the form of a term from the calculated operations on the basic functions. Basic functions, as we know [1,2], are called the simplest functions n o(x) = 0, s(x) = x + 1 and selector functions I m (x1, … , xn) = xm, where n  m  1. The main computational operations will be superposition operations Sn+1, primitive recursion R and minimization M. For example, a superposition operation Sn+1 allows from function g(x1, …, xn) and functions g1(x1, … , xm), ... , gn(x1, … , xm), create a function f(x1, … , xm) = g(g1(x1, … , xm), … , gn(x1, … , xm)), which is denoted by the term Sn+1(g, g1, … , gn). A natural question about the possibility of using concrete algorithms to prove the fundamental results of the theory of recursive functions without constructing appropriate computational terms arises. Or, in other words, to tell in a language understandable to programmers about the main results of the theory of algorithms (recursive functions), in particular about the problems of computability and solvability. Therefore, the purpose of the work is to offer approaches and means to solve the problem. To do this, it is proposed to accurately describe the basic constructions of the algorithm and reformulate (concretize) Chorch's thesis for narrower classes of algorithmically calculated functions. Concretization of the concept of algorithm Next, the algorithms will be defined as syntactically correct constructions in the PseudoPascal language, which is a simplified dialect of the Pascal language. The operators of this language will be the following: < identifier > = = < word > < operator > = = < identifier > = < arithmetic expression > < operator > = = if < relation > then < operator > else < operator > < operator > = = while < relation > do {< operator >, … , < operator >} < operator > = = for < relation > to < relation > {< operator >, … , < operator >} We concretize Church's thesis for classes of primitively recursive, recursive and partially recursive functions, respectively. 1. A class of functions calculated by the algorithms defined everywhere without using the while … do operator. This class is described as follows: Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 198 1) We assume that the simplest functions o(x) = 0, s(x) = x + 1 та функції-селектори n I m (x1, … , xn) = xm, де n  m  1 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 1y x, 2y x, … , [x/y] x, … , xy x. 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 = 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. 199 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 goes earlier than a pair if x + y < u + v, or if x + y = u + v and x < u, then the relation  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 in the Cantor sequence. The left and right elements of the pair 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: 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. Given that l(n)  n, r(n)  n function l(n) is calculated by the algorithm: function l(n) begin for i = 0 to n for j = 0 to n if с(i, j) = n then l = i end, and the function r(n) is calculated by an algorithm: function r(n) begin for i = 0 to n for j = 0 to n if с(i, j) = n then r = j end. So, с(x, y), l(n) and r(n) are primitive recursive functions. We show that the function f(x) = [ex] is primitive recursive functions. Really, inequality holds 200 xSn < ex < x(Sn + 1/n!n), where e = 1 + 1/1! + 1/2! + … + 1/n! + /n!n, 0 <  <1, Sn = 1 + 1/1! + 1/2! + … + 1/n!. Since lim ( x( S n  1 / n!n)  x  S n )  0 , then n [ x ( S n  1 / n!n)]  [ x  S n )]  0 for some n, that is [ x ( S n  1 / n!n)]  [ x  S n )] for some n. So, in order to find the value of [ex], it is necessary to find the minimum n for which the previous equality is fulfilled and to put [ex] = [хSn]. The graph of the function F(x1, …, xn) [1-3] is the set . 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: , 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. 201 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 function f(x) begin ...... f=... end, 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 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 U = {(i, x), K(i, x) = 1}. 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 1, K (i, x) 1 U(i, x) =  0, K (i, x)  1 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 function f(x) begin i := 0 while U(x, x) = 1 do i := i + 1 f := 1 end, 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 A1A2 … A4, where A1 = S  a SSb, A2 = S  Sbb, A3 = Sb  S, A4 = SS  aac. The set of all such words will be called the base. 202 Universal set.of words [4] we will be called the set V of words A1A2 … Anw such that the word w is infered in the grammar G with rules A1, A2, … , An, that is V = {A1A2 … Anw, 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 A1A2 … Anw such that w belongs to the recursively enumerable set, which is generated by the grammar with rules A1, A2, … , An, that is V = {A1A2 … Anw, 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 P = {(v1, w1), (v2, w2), … , (vn, wn)} 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 (vi1 , wi1 ), (vi2 , wi2 ), ... , (vik , wik ) of pairs of words that vi1 vi2 ... vik  wi1 wi2 ... wik , 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 A1A2 … Anw 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 A1A2 … Anw  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: 203 A  v1Aa1 v2Aa2 …  vnAan v1a1 v2a2 …  vnan. This grammar generates language L(G A )  { i1 ... im aim ... ai1 , 1  i1 , ..., i m  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 B  w1Ba1 w2Ba2 …  wnBan w1a1 w2a2 …  wnan. This grammar generates language L(G B )  {wi1 ...wim aim ... ai1 , 1  i1 , ..., im  n} . Let's form a grammar 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 Aa i1   i1 i2 Aa i2 ai1  ...   i1 i2 ...  im aim ... ai2 ai1 , S  B  wi1 Ba i1  wi1 wi2 Ba i2 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) 204 is algorithmically unsolvable. Proof. Let's show that L(G A ) 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(G A ) . 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(G A ) . 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(G A ) . 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 L A  L B 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. References 1. A.I. Maltsev. Algorithms and recursive functions. – Science: Moscow, 1965. – 390 p. 2. V.А. Uspenskij, А.Л. Semenov. Algorithm theory: basic diyscoveries and applications - Science: Moscow, 1987. – 288 p. 3. О.І. Provotar. Concret algoritmics. - Naukova Dumka: Kyiv. 2017. – 168 p. 4. D. Hopcroft, R. Motwani, D. Ullman. Introduction to the theory of automata, languages and calculations. - M: Williams, 2002. – 528 p. 5. M.S. Nikitchenko, S.S Shkilniak. Mathematical logic and theory of algorithms. - K: VPC "Kyiv University", 2008. – 528 p. About the authors: 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. 205 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. Place of work of the authors: Taras Shevchenko National University of Kyiv, 03187, Kyiv -187, Academician Glushkov Avenue, 2, b. 6. T.: (044) 259 0511. Fax: (044) 259 7044. E-mail: aprowata1@bigmir.net. V.M. GlushkovI Cybernetics Institute NAS of Ukraine, 03680, МСП, Kyiv -187, Academician Glushkov Avenue, 40. Т.: (044) 259 0511. Fax: (044) 259 7044. E-mail: provotar@huspi.com. +38-050-444-17-35, email: aprowata1@bigmir.net. 206