Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-16T18:22:21.793Z Has data issue: false hasContentIssue false
  • English
  • Français

Functions and functional on finite systems

Published online by Cambridge University Press:  12 March 2014

Libo Lo
Libo Lo*
Affiliation:
Department of Computer Science, Nagoya University of Commerce and Business Administration, Nagoya, Japan470-01
Get access Rights & Permissions [Opens in a new window]

Extract

The global function on finite systems is a new concept defined by Gurevich in [1] and discussed in [2] and [3]. In the last ten years this concept has become more and more useful in computer science and logic. Gurevich also pointed out the importance of global functionals on finite systems. In this paper we will give a brief introduction to the concepts of global functions and global functionals on finite systems.

In studying the natural number system N = 〈N, +,0〉 we often refer to its functions and functionals. There are a lot of books and papers in this area. Kleene in [4] gave a detailed introduction to the recursive functions of N. The functionals of N are normally very difficult to compute because here we need to tell the machine what the input function is, which is not very easy to do. In developing the theory of finite systems the functions and functionals are also very useful. For computing the functionals in finite systems we can take the entire graph of a function as the input, which is not possible in N. We will discuss recursive functions and functionals for finite systems. The definitions of recursive functions are very similar to the case in N, but we will have a very different situation. In N the number of elements is infinite. The number of all possible functions from N to N is the continuum. In a finite system the number of all possible functions is finite. It seems that there is no necessity to define the global functions.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 1 , March 1992 , pp. 118 - 130
Copyright
Copyright © Association for Symbolic Logic 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Gurevich, Y., Algebras of feasible functions, Proceedings of the 24th IEEE Symposium on Foundations of Computer Science (1983), pp. 210–214.Google Scholar
[2]Gurevich, Y., Toward logic tailored for computational complexity, Computation and proof theory (Richter, M.et al., editors), Lecture Notes in Mathematics, vol. 1104, Springer-Verlag, Berlin, 1984, pp. 175–216.CrossRefGoogle Scholar
[3]Gurevich, Y., Logic and the challenge of computer science, Trends in theoretical computer science (Börger, E., editor), Computer Science Press, Rockville, Maryland, 1988, pp. 1–57.Google Scholar
[4]Hopcroft, J. E. and Ullman, J. D., Introduction to automata theory, languages, and computation, Addison-Wesley, Reading, Massachusetts, 1979.Google Scholar
[5]Kleene, S. C., Introduction to metamathematics, Van Nostrand, New York, 1952.Google Scholar