Page 101

		index on different texts for the same language in , nor need M necessarily converge on texts for languages outside . We next consider two constraints on convergence that limit the freedom of scientists in these ways.

		§5.4.1 Order Independence

		As the first constraint on convergence we consider scientists that converge to the same index on every text for a language.

		5.27 Definition (Blum and Blum [18])

		(a) M is order-independent on L just in case for all texts T, T' for L, if , then .

		(b) M is order-independent on ; just in case M is order-independent on each .

		(c) M is order-independent just in case M is order-independent on each .

		Thus an order-independent scientist is relatively insensitive to the choice of text for a language on which it is order-independent: any such text eventually leads it to the same index. Note that different texts for the same language may cause an order-independent scientist to examine different amounts of input before convergence begins (just as for order-dependent scientists).

		5.28 Definition (Blum and Blum [18])

		(a) .

		(b) .

		Clearly, . The effect of order independence on scientists may at first appear to be restrictive because of the following consideration. An order-independent learning policy seems to require the ability to determine the equivalence of distinct indexes, but the equivalence question cannot in general be answered by a computational process, indeed, the set is not even r.e. (sec Rogers [158, Section 5.2]). Contrary to expectation, order independence turns out not to be restrictive. This follows from the following extension of a result of Blum and Blum [18] by Fulk [71].