Page 86

		distinct languages, , such that for each , , but . is said to have finite elasticity just in case does not have infinite elasticity.

		1. If a class of languages has finite thickness, then show that it has finite elasticity.

		2. Show that if an indexed family of computable languages has finite elasticity, then .

		4-10 Show that both and are members of Ex.

		4-11 Does the analogue to Proposition 4.30 hold for language identification?

		4-12 Let be given. Show that there is such that .

		4-13 Consider the scientist F defined in the proof of Theorem 3.43. It follows from Theorem 4.28 that F is not computable. Describe the aspect of F that renders it un-computable.

		4-14 Show that Proposition 3.46 can be strengthened to the following: There is such that no memory limited scientist (computable or not) identifies .

		4-15 Prove Proposition 4.39.

		4-16 Prove Proposition 4.47.

		4-17 Let be the set of all indexes x such that card(Wx) is finite. Show that J is performable on [·]f.

		4-18 Let be as defined in Exercise 4-2. Show that .

		4-19 Suppose that (not necessarily computable) identifies exactly. Show that for all , if and only if there is a locking sequence for F on L.

		4-20 (Advanced) Show that if and only if and is arithmetically indexable.

		Hint: Use Exercise 4-19.