Geodesic
On the existence problem of finite bases of identities in the algebras of recursive functions
Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 3, pp. 304-315 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Raphael Robinson showed that all primitive recursive functions depending on one argument, and only they could be obtained from two functions $s(x) = x +1$ and $q(x) = x - [\sqrt x]^2$ by using operations of addition $+$, superposition $*$ and iteration $i$. Julia Robinson proved that from the same two functions, using the addition $+$, superposition $*$ and operation $^{-1}$ of function inversion, one could obtain all general recursive functions (under a certain condition on the inversion operation) and all partially recursive functions. On the basis of these results, A. I. Maltsev brought into consideration the Raphael Robinson algebra of all unary primitive recursive functions and two Julia Robinson algebras: the partial algebra of all unary general recursive functions and the algebra of all unary partially recursive functions and proposed to study the properties of these algebras, including the question of the existence of finite bases of identities in these algebras. In this article we show that there is no finite basis of identities in any of the indicated algebras.
Keywords: algebras, recursive functions, identities, basis, iteration, function inversion.
Mots-clés : superposition 
@article{MAIS_2020_27_3_a1,
     author = {V. A. Sokolov},
     title = {On the existence problem of finite bases of identities in the algebras of recursive functions},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {304--315},
     year = {2020},
     volume = {27},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2020_27_3_a1/}
}
TY  - JOUR
AU  - V. A. Sokolov
TI  - On the existence problem of finite bases of identities in the algebras of recursive functions
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2020
SP  - 304
EP  - 315
VL  - 27
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MAIS_2020_27_3_a1/
LA  - ru
ID  - MAIS_2020_27_3_a1
ER  - 
%0 Journal Article
%A V. A. Sokolov
%T On the existence problem of finite bases of identities in the algebras of recursive functions
%J Modelirovanie i analiz informacionnyh sistem
%D 2020
%P 304-315
%V 27
%N 3
%U http://geodesic.mathdoc.fr/item/MAIS_2020_27_3_a1/
%G ru
%F MAIS_2020_27_3_a1
V. A. Sokolov. On the existence problem of finite bases of identities in the algebras of recursive functions. Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 3, pp. 304-315. http://geodesic.mathdoc.fr/item/MAIS_2020_27_3_a1/

[1] A. A. Markov, E. A. Kuznetsova, Rails flaw detection. Formation and analysis of signals, v. 1, Principles, KultInformPress, St. Petersburg, 2010

[2] A. A. Markov, E. A. Kuznetsova, Railsaw detection. Formation and analysis of signals, Data interpretation, v. 2, Ultra Print, St. Petersburg, 2014

[3] V. F. Tarabrin, A. V. Zverev, O. E. Gorbunov, E. V. Kuzmin, “About Data Filtration of the Defectogram Automatic Interpretation by Hardware and Software Complex ASTRA”, NDT World, 64:2 (2014), 5–9

[4] E. V. Kuzmin, O. E. Gorbunov, P. O. Plotnikov, V. A. Tyukin, V. A. Bashkin, “Application of Neural Networks for Recognizing Rail Structural Elements in Magnetic and Eddy Current Defectograms”, Automatic Control and Computer Sciences, 53:7 (2019), 628–637 | DOI | MR

[5] E. V. Kuzmin, O. E. Gorbunov, P. O. Plotnikov, V. A. Tyukin, “An Efficient Algorithm for Finding the Level of Useful Signals on Interpretation of Magnetic and Eddy Current Defectograms”, Automatic Control and Computer Sciences, 52:7 (2018), 867–870 | DOI | MR

[6] E. V. Kuzmin, O. E. Gorbunov, P. O. Plotnikov, V. A. Tyukin, “Finding the Level of Useful Signals on Interpretation of Magnetic and Eddy-Current Defectograms”, Automatic Control and Computer Sciences, 52:7 (2018), 658–666 | DOI | MR

[7] I. Goodfellow, Y. Bengio, A. Courville, Deep Learning, MIT Press, 2016 | MR | Zbl

[8] F. Chollet, Deep Learning with Python, Manning Publications Co, 2018

[9] TensorFlow, https://www.tensorflow.org/