|
|
|
|
|
(c) T begins with s if and only if . |
|
|
|
|
|
|
|
|
(d) , but , the empty sequence. |
|
|
|
|
|
|
|
|
(e) SEQ is just the collection of all finite sequences over . This collection is countably infinite. |
|
|
|
|
|
|
|
|
Consider again our scientist studying periodicity, and suppose that her research gives rise to the text T of 3.3 (representing 3.2). T(n) may be conceived as the data generated at the nth moment of investigation, so T[n] is all the evidence available to the scientist about periods up to the nth moment, the so-called "evidential state" of the scientist at that time. More generally, any constitutes a logically possible evidential state at the moment. Now within the present paradigm, empirical inquiry is conceived as the process of converting evidence into theories. Since the set of all possible evidential states is represented by SEQ and the set of all intelligible hypotheses is represented by N, it is natural to take a scientist to be any system that maps the former into the latter. Officially, then, a scientist within the language identification paradigm is any functionpartial or total, computable or noncomputablefrom SEQ to N. We use F as a variable for scientists, especially when it is not specified whether the scientist in question is computable. |
|
|
|
|
|
|
|
|
Let text T and be such that . Then WF(T[n]) denotes the language corresponding to the grammar that F produces upon examining the finite sequence of length n in T. We often say that this language is "conjectured by F on T[n]." If , then WF(T[n]) is not defined. |
|
|
|
|
|
|
|
|
Intuitively, it is helpful to picture a scientist as traveling down a text from left to right, examining the entries in turn. At each step, the scientist is confronted with a new member of SEQthat is, a new evidential situation s . The scientist may respond to s with either a new or previously-emitted hypothesis (in which case, she is defined on s ); alternatively, she may produce no hypothesis at all (in which case she is undefined on s ). |
|
|
|
|
|
|
|
|
To illustrate, the scientist in our periods example might implement the function defined as follows. Let P and O be the sets of prime numbers and odd numbers, respectively. Let n, o, and p be indexes for N, O, and P. |
|
|
|
|
|
|
|
|
3.8 For all : |
|
|
|
|