Page 70

		Although the canonical text for constitutes only one among uncountably many orderings of f, there is an algorithm A. that progressively converts any incoming text G into a canonical text G' for the same function. Informally, A works on G by reading and storing the members of G until some pair of the form (0, x) appears. (If G is for some , then exactly one such pair must eventually occur.) A writes this pair as the first member of G'. Next, A searches its memory for some pair of the form (1, x); if no such pair is found in memory, A reads and stores more of G until such a pair is found. This pair is written onto G', and A then searches for a pair of the form (2, x) . . . . This process continues indefinitely. Although A may be required to store ever larger initial segments of G, its storage requirements are finite at any given time. It is clear that A gradually produces a canonical text for content(G). Formally, we let be defined as follows.

		4.19 Definition For all , FA( s ) is the longest such that .

		FA is computable, and applying it to ever longer initial segments of a text produces ever longer initial segments of the corresponding, canonical text. That is:

		4.20 Lemma If G is an arbitrary text for , then is the canonical text for f.

		The ability to algorithmically transform any text into canonical order simplifies the Ex paradigm. This is shown by the following proposition.

		4.21 Proposition Let be given. if and only if there is a computable scientist that identifies the canonical text for any member of C.

		Proof: The left-to-right direction is immediate. For the other direction, we use an internal simulation argument. Suppose that computable scientist F identifies the canonical text for any member of . Define scientist F* as follows. For all , F*( s ) = F(FA(s)). F* is computable because it is the composition of computable functions. Moreover, F* converges to on text G for if F converges to i on the corresponding canonical text. Since F identifies the latter, F* identifies the former and thus identifies C.

		To prove claims of the form or we shall henceforth rely implicitly on Proposition 4.21, and consider only canonical texts. The following slight abuse of