Rice and Rice-Shapiro Theorems for transfinite correction grammars

摘要

Hay and, then, Johnson extended the classic Rice and Rice-Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work (with some motivations presented) to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene’s important system of notations, O. Other cases are done for all transfinite notations in a very natural, proper subsystem O_(Cantor) of O, where O_(Cantor) has at least one notation for each constructive ordinal. In these latter cases it is open as to what happens for the entire set of transfinite notations in (O-O_(Cantor)).