Page 199

		the informal idea of teamwork. When different scientists work separately on the same problem it is often the case that individual progress is recognizable by all concerned. The hypotheses of the individual scientists thus influence each other in a way that is not captured by the paradigms discussed in the present chapter.

		§9.3 Team Identification of Functions

		We first consider team identification of functions when the success of the team requires any one member in the team to be successful.

		The following result says that there are collections of functions for which a correct program can be synthesized by a team of (n + 1) scientists, at least one of which is successful, but for which even a finite variant program cannot be synthesized by a team of n scientists with the requirement that at least one of them be successful.

		9.5 Proposition (Smith [178]) For each , .

		Proof: For each , let

		.

		It is easy to verify that . We argue, using a diagonalization argument, that . This argument can easily be generalized to show that .

		Suppose, by way of contradiction, there exists a team of two scientists, M0 and M1, that witnesses . Then, by the implicit use of the operator recursion theorem, there exists a 1-1, monotonically increasing, recursive function p such that  j p(·) (and, hence, Wp(·)) is as described in stages below.

		We initialize  j p(3)(0) = p(0),  j p(3)(1) = p(1), and  j p(3)(2) = p(2). Enumerate p(3) into Wp(0). Set avail = 3. Intuitively, avail denotes the least number such that, for all i > avail, p(i) has not yet been used in the diagonalization. Let xs denote the least x such that  j p(3)(x) has not been defined before stage s. Go to stage 0.

		Begin ( Stage s ) 1. Set avail = avail + 1. Set cur = avail. Enumerate p(cur) into Wp(1). For each x < xs, set  j p(cur) (x) =  j p(3) (x).