Premium
Undecidable Problems Associated with Combinatiorial Systems and Their One‐One Degrees of Unsolvability
Author(s) -
Jedrzejowicz Joanna
Publication year - 1981
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.19810272508
Subject(s) - undecidable problem , computer science , cleave , combinatorics , mathematical economics , theoretical computer science , operations research , discrete mathematics , mathematics , decidability , physics , nuclear magnetic resonance , enzyme
The genesis of the problems investigated in this paper are the results on Turing degrees and many-one degrees of undecidable problems of J. C. SHEPHERDSON [9] and R. OVERBEEK [7] and the results of J. P. CLEAVE 111, [2], [3] on one-one degrees. As was proved in [I] each of the following: halting problem, derivability problem and confulence problem of a deterministic combinatorial system is cylindrical. Thus, it is clear that OVERBEEK'S result version on many-one degrees was the best possible improvement of SHEPHERDSON'S representation theorem. The aim of this paper is to show that in case of nondeterministic systems these problems need not be cylindrical. Besides, results concerning the place of problems in DERKER-MYHILL classification of r.e. sets are obtained (Chap. 4) and home improvement of &EAvE's paper [2] is given (Chap. 3). Some results are partly annouced in [a] but the essential proofs are given in this paper (Theorems 2 and 4). The author wishes to express his sincere gratitude to Prof. A. W. MOSTOWSKI for his help and encouragement.