Abstract
A set A of words on a finite alphabet Σ is said to be generable if it is the closure of a computable inductive operator; in particular, if S is a semi-Thue system then the set of words derivable in S is generable. An RE set of words (equivalently, a phrase-structure or type 0 language in the sense of Chomsky [Information and Control 2 (1959), 137–167]) which is non-generable is constructed by means of a finite injury priority argument. The construction is refined to obtain a non-generable set of degree 0′ and, for any degree d, a non-generable set of degree ⩽ d.
Keywords
Get full access to this article
View all access options for this article.