Page 57

		3-12 For each and each , define . For each define a collection of languages by:

		.

		Show that for every , is identifiable.

		3-13 We define a generalization of the concept of memory limitation.

		3.55 Definition Let be given.

		(a) The result of removing the last n members of  s  is denoted by ; if , then .

		(b) The finite sequence consisting of the last n members of is denoted by  s last n; if then  s last n =  s .

		(c) Scientist F is n-memory limited just in case for all  s , , if and , then .

		Thus, memory limitation corresponds to 1-memory limitation. Show that for all and , some n-memory-limited scientist identifies if and only if some 1-memory-limited scientist identifies . Hint: Use the "padding function" described in Chapter 2.

		3-14 The present exercise concerns another generalization of memory-limitation.

		3.56 Definition A scientist is called weakly memory limited just in case there is a function with the following properties. For all  s , ,

		(a)

		(b)

		(c)

		Intuitively, F can remember any single previous datum of her choice. Clause (b) means that F can change the contents of her memory only by storing the datum currently in view. F is memory-limited in the sense that a given conjecture depends only on (a) the one datum she remembers, (b) the datum currently under examination, and (c) her latest conjecture.