|
|
|
|
|
9
Team and Probabilistic Learning |
|
|
|
|
|
|
|
|
The paradigms presented so far have modeled empirical inquiry by a single, deterministic, computable scientist. In the present chapter, we consider paradigms that permit more liberal conceptions. |
|
|
|
|
|
|
|
|
Empirical inquiry in the scientific domain is seldom an individual enterprise. Many scientific breakthroughs result from the efforts of several scientists investigating a problem; scientific success is achieved if one or more of the scientists are successful. This observation about the practice of science can be partially incorporated into our model of empirical inquiry by a ''team" of computable scientists. The team is said to be successful just in case one or more members in the team are successful. |
|
|
|
|
|
|
|
|
Another variation on the notion of "scientist" is obtained by considering those machines which, in addition to their algorithmic nature, have the added ability to base their actions on the outcomes of random events. Such scientists can be modeled using probabilistic Turing machines (in the sense of Gill [78]). |
|
|
|
|
|
|
|
|
The present chapter considers identification of functions and languages by teams of computable scientists and by probabilistic scientists. |
|
|
|
|
|
|
|
|
§9.2 Motivation for Identification by Teams |
|
|
|
|
|
|
|
|
The next two propositions are commonly referred to as "nonunion theorems." They respectively establish that the classes Ex and TxtEx are not closed under union. That is, the union of two identifiable collections of functions (respectively, languages) is not necessarily identifiable. (Proposition 9.1 is a restatement of Theorem 4.25 due to L. Blum and M. Blum, and Proposition 9.2 restates a fact established in Chapter 4.) |
|
|
|
|
|
|
|
|
9.1 PropositionLet and . Then, both and are in Ex, but . |
|
|
|
|
|
|
|
|
9.2 PropositionLet and . Then, both and are in TxtEx, but . |
|
|
|
|