Hostname: page-component-7b7567c8c-lpg2g Total loading time: 0 Render date: 2026-11-15T12:38:28.729Z Has data issue: false hasContentIssue false

Rice Theorems For D.R.E. Sets

Published online by Cambridge University Press:  20 November 2018

Louise Hay*
Affiliation:
University of Illinois at Chicago Circle, Chicago, Illinois
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Two of the basic theorems in the classification of index sets of classes of recursively enumerable (r.e.) sets are the following:

(i) The index set of a class C of r.e. sets is recursive if and only if C is empty or contains all r.e. sets; and

(ii) the index set of a class C or r.e. sets is recursively enumerable if and only if C is empty or consists of all r.e. sets which extend some element of a canonically enumerable class of finite sets.

The first theorem is due to Rice [7, p. 364, Corollary B]. The second was conjectured by Rice [7, p. 361] and proved independently by McNaughton, Shapiro, and Myhill [6].

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1975