Premium
SYSTEM FUNCTIONS AND THEIR DECISION PROBLEMS
Author(s) -
Thuraisingham M. B.
Publication year - 1984
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.19840300703
Subject(s) - ninth , cleave , citation , operations research , work (physics) , library science , computer science , mathematics , combinatorics , engineering , physics , mechanical engineering , nuclear magnetic resonance , acoustics , enzyme
In his investigation of the one-one equivalence between general combinatorial decision problems, CLEAVE initiated the concept of system functions [l]. System functions are defined on natural numbers and their values are finite sets of natural numbers. They have many properties in common with those arising from Gijdel numbering various combinatorial systems. Thus the decision problems defined for these combinatorial systems can also be defined for system functions. Furthermore, if a property holds for a decision problem for all system functions, then it also holds for that decision problem for all these combinatorial systems. In his work, CLEAVE defined the decision problems such as the halting, derivability and confluence problems for system functions and his aim was to prove that these decision problems for various classes of system functions were either recursive or cylinders. CLEAVE considered cylindrical decision problems for the following reason : “If P, and P, are two general combinatorial decision problems which are manyone equivalent and if each instance of P, and P, is a cylinder, then they are one-one equivalent and this is the best possible equivalence one can obtain.” ([l],