Publication Details:

This issue of the Periodical is dedicated to the 85-th anniversary of Hrant B. Marandjian,Doctor of Physical and Mathematical Sciences, Professor, Corresponding Member of NAS RA, Academician of the Russian Academy of Natural Sciences.

Journal or Publication Title:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Date of publication:

2024

Volume:

62

ISSN:

2579-2784 ; e-2538-2788

Additional Information:

click here to follow the link

Coverage:

17-24

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 ��′).

Publisher:

Изд-во НАН РА

Format:

pdf

Identifier:

oai:arar.sci.am:405404

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան