2021, issue 2, p. 63-67
Received 06.05.2021; Revised 12.05.2021; Accepted 24.06.2021
Published 30.06.2021; First Online 01.07.2021
https://doi.org/10.34229/2707-451X.21.2.6
Previous | Full text (in Ukrainian) | Next
Methods of Numeration of Discrete Sequences
N.A. Gupal
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Numeration, or code, discrete sequences act fundamental part in the theory of recognition and estimation. By the code get codes or indexes of the programs and calculated functions. It is set that the universal programs are that programs which will realize all other programs. This one of basic results in the theory of estimation. On the basis of numeration of discrete sequences of Godel proved a famous theorem about incompleteness of arithmetic.
Purpose of the article. To develop synonymous numerations by the natural numbers of eventual discrete sequences programs and calculable functions mutually.
Results. On the basis of numerations of eventual discrete sequences numerations are built for four commands of machine with unlimited registers (MUR) in the natural numbers of type of 4u, 4u +1, 4u+2, 4u+3 accordingly. Every program consists of complete list of commands. On the basis of bijection for four commands of MUR certainly mutually synonymous numerations for all programs of MUR. Thus, on the basis of the set program it is possible effectively to find its code number, and vice versa, on the basis of the set number it is possible effectively to find the program.
Conclusions. Synonymous numerations by the natural numbers of complete discrete sequences are developed mutually, programs for MUR and calculable functions. Leaning against numeration of the programs it is set in the theory of calculable functions, that the universal programs are, that programs which will realize all other programs. By application of the calculated functions and s-m-n theorem are got to operation on the calculated functions: combination φx and φy, giving work φxφy, operation of conversion of functions, effective operation of recursion. Thus, the index of function φxφy is on the indexes of x and y [2].
Keywords: numeration, Godel code number, diagonal method.
Cite as: Gupal N.A. Methods of Numeration of Discrete Sequences. Cybernetics and Computer Technologies. 2021. 2. P. 63–67. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.2.6
References
1. Shepherdson J.C., Sturgis H.E. Computability of recursive functions. J. Assoc. Comput. Machinery. 1963. 10 (2). P. 217–255. https://doi.org/10.1145/321160.321170
2. Rogers H. Jr. Theory of recursive functions and effective computability. New York, 1967, 624 p.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Ukrainian) | Next