ON THE UNRECOGNIZABILITY OF SETS.

Many of the results achieved concerning regularity or non-regularity of sets have been done in the context of equivalence relations of finite index and a fundamental lemma concerning the way certain input can be separated. Recently Marvin Minsky and Seymour Papert developed a set of criteria for non-regularity based on a limiting quantity which seems intuitively to represent the portion or percentage of strings that are in the regular set. In this paper we define for regular sets, in terms of natural Markov processes, another quantity, pA, which, generally speaking, again represents a kind of percentage of strings in the regular set and show that, when Minskys limits exist, these two quantities agree. From the quantity developed in this paper, however, more information can be gathered concerning the machine which recognizes the regular set and hence information about the regular set itself than can be gathered from Minskys criteria. Also described is a special machine which gives an upper bound for the growth rate of sets recognizable by a certain type of automaton. Finally it is shown that the set of well-formed trees written as strings is not a regular set. Author