Using categories as abstract structures to formalize computational models

DOI: 10.31673/2412-9070.2022.055255

Abstract

The paper provides an analysis of various formal models of computation, including recursive functions, fuzzy models, and categorical models. These models are subject to research in order to identify ways of performing calculations based on them. In the context of each of these models, the concept of computability and basic arithmetic operations is introduced, which allows to deepen the understanding of their structures and mechanisms. The main conclusion of the study is that the considered formal models of calculations can be simulated in the context of different categories. This approach paves the way for the construction of an abstract theory of computability and corresponding programming languages on a categorical basis. This approach has the potential to create a universal programming language that would support the description of tasks from different subject areas. It is possible to implement the approach by interpreting these problems in the appropriate categories and using a universal category apparatus for their solution. It deserves special attention that such a language should be aimed at solving scientific problems, which reflects its potential value in the field of scientific research. In addition, this study can lay the foundation for further developments in expanding the capabilities of formal computational models. Given the presence of categories including fuzzy sets, fuzzy functions and partially recursive functions, the considered calculation models can be the object of analysis in the context of these categories. This provides an opportunity to construct an abstract theory of computability and corresponding programming languages based on a categorical basis. The development of the Haskell programming language also represents a first step in this direction, highlighting the importance and potential benefits of this approach. It is possible to consider Haskell as an experimental plane for the development of categorical concepts in programming languages, which opens new horizons for further research in this area.

Keywords: formal models of calculations; fuzzy set; category; recursive function.

References
1. Barr M., Wells C. Category Theory for Computing Science // Reprints in Theory and Applications of Categories. 2012. No. 22.
2. Rosolini G. Categories and effective computation. Lecture Notes in Computer Science // Category Theory and Computer Science. Springer-Verlag, 1987. vol. 283.
3. Curien P.-L. Categorical Combinators, Sequential Algorithms and Functional Programming // Research Notes in Theoretical Computer Science, Pitman, 1986.
4. Hagino T. A categorical programming language. University of Edinburgh, 1987. 140 p.
5. Sergienko I. V., Parasyuk I. N., Provotar A. I. On the application of categorical methods in Computer Science // KISA, 2000. № 4.
6. Goldblatt R. Topoi. The categorial analysis of logic // North-Holland Publishing Company, 1979. Р. 486.
7. Zadeh L. Fuzzy sets // Inf. Control. 1965. Р. 338–353.
8. Ross T. Fuzzy Logic with Engineering Applications. John Wiley & Sons, Ltd, 2004. Chichester.
9. Carol L. Walker. Categories of fuzzy sets // Soft Computing. 2004. Vol. 8, №4. P. 299–304.
10. Barr M. Fuzzy sets and topos theory // Canadian Math. Bull. 1986. Vol. 24. P. 501–508.
11. Hudak P. The Haskell School of Expression – Learning Functional Programming through Multimedia. New York: Cambridge University Press, 2000.