Publication Details:
Journal or Publication Title:
Date of publication:
Volume:
ISSN:
Additional Information:
Title:
Creator:
Subject:
Uncontrolled Keywords:
e-reducibility ; partial degree ; partial computable function
Coverage:
Abstract:
The ordering of e-degrees (of total functions) is known to be isomorphic to the ordering of T-degrees. It is possible to form equivalence classes with respect to =е and in the set of all functions (not necessarily total). The resulting e-degrees are called partial degrees. In H. Rogers’ Theory of Recursive Functions and Effective Computability [1], a proof of the existence of a non-total partial degree is given along with a corollary to this theorem. The article contains a modification of the proof of the theorem given above, which allows us to significantly strengthen the results of the corollary, namely to prove that (∃��)[ �� is not partial computable & �� ≤" ��′ & (∀��)[�� ≤# �� ⇒ �� is computable]] (in the above-mentioned corollary, it is noted that the constructed function is only computably enumerable in ��′).