Abstract

In this paper we define the concept of a system function language which is a language generated by a system function. We identify system function languages with recursively enumerable sets which are non-simple and co-infinite. We then define restricted system function languages and identify them with recursive sets which are co-infinite. Finally we state and prove some independence and dependence relationships between system function languages and some of the more well-known decision problems. MSC: 03D05, 03D20, 03D25