Page 269

		For each  s , define

		We leave it as a straightforward exercise to check that M TxtMin y -identifies .

		The TxtMin y  paradigm can be related in a striking fashion to TxtEx. For this purpose, we introduce the following definition which is based on a related notion of Freivalds [61] (see Exercise 12-8).

		12.14 Definition (Case and Chi [27])

		(a) Suppose g and v are recursive functions. We say that is limiting standardizable via g with recursive estimate v (written: ) if and only if, for each , there is an iL with such that, for every i with Wi = L we have:

		1. , and

		2. .

		(b) We say that is text limiting standardizable with recursive estimate (written: ) if and only if, for some recursive g and v we have .

		Intuitively, the role of g in the definition of TxtLsr is to provide indirectly a limiting recursive solution to a special case of the grammar equivalence problem () where the grammars generate languages in ; the v places some extra constraints on how g reaches its limit.2 The notion of TxtLsr defined above is implicitly parameterized by the choice of acceptable programming system. Explicit parameterization is not called for, because it is easy to check that the class TxtLsr is independent of the choice of acceptable programming system. Here is the promised characterization of TxtMin y .

		12.15 Proposition For all , the following are equivalent.

		(a) For some acceptable programming system  y , .

		(b) .

		2This interpretation is due to John Case.