Elements of concrete algorithmics: computability and solvability

O.I. Provotar, O.O. Provotar

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.

Problems in programming 2020; 2-3: 198-207


Keywords


Church thesis; solvability; universal function

References


Maltsev A.I. Algorithms and recursive functions. M.: Science. 1965.390 p.

Uspensky V.A., Semenov A.L. Algorithm theory: basic discoveries and applications. M.: Science. 1987. 288 p.

Provotar O.І. The algorithm is specific. Kiev. Naukova dumka. 2017.168 p.

Hopcroft D., Motvani R., Ullman D. Introduction to the theory of automata, languages and computations. M: “Williams”, 2002. 528 p.

Nikitchenko M.S., Shkilnyak S.S. Mathematical logic and theory of algorithms. К.: VPS “Kiev University”, 2008. 528 p.




DOI: https://doi.org/10.15407/pp2020.02-03.198

Refbacks

  • There are currently no refbacks.