Premium
System function languages
Author(s) -
Thuraisingham M. B.
Publication year - 1993
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19930390140
Subject(s) - recursively enumerable language , function (biology) , recursively enumerable set , independence (probability theory) , simple (philosophy) , mathematics , computer science , discrete mathematics , statistics , evolutionary biology , biology , philosophy , epistemology
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.