Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

12 Computability Theory 8. Assume that S is a decidable set of natural numbers, and that f is a total effec- tively calculable function on N . Explain why {x | f (x) S} is decidable. (This set is called the inverse image of S under f .) 9. Assume that S is a semidecidable set of natural numbers and that f is an effec- tively calculable partial function on N . Explain why {x | f (x) and f (x) S} is semidecidable. 10. In the decimal expansion of , there might be a string of many consecutive 7's. Define the function f so that f (x) = 1 if there is a string of x or more consecutive 7's and f (x) = 0 otherwise: f (x) = 1 0 if has a run of x or more 7's otherwise. 11. 12. 13. 14. Explain, without using any special facts about or any number theory, why f is effectively calculable. Assume that g is a total nonincreasing function on N (that is, g(x) g(x + 1) for all x). Explain why g must be effectively calculable. Assume that f is a total function on the natural numbers and that f is eventually periodic. That is, there exist positive numbers m and p such that for all x greater than m, we have f (x + p) = f (x). Explain why f is effectively calculable. (a) Assume that f is a total effectively calculable function on the natural numbers. Explain why the range of f (that is, the set { f (x) | x N }) is semidecidable. (b) Now suppose f is an effectively calculable partial function (not necessarily total). Is it still true that the range must be semidecidable? Assume that f and g are effectively calculable partial functions on N . Explain why the set {x | f (x) = g(x) and both are defined} is semidecidable. 1.2 Formalizations An Overview In the preceding section, the concept of effective calculability was described only very informally. Now we want to make those ideas precise (i.e., make them part of mathematics). In fact, several approaches to doing this will be described: idealized computing devices, generative definitions (i.e., the least class containing certain initial functions and closed under certain constructions), programming languages, and defin- ability in formal languages. It is a significant fact that these very different approaches all yield exactly equivalent concepts. This section gives a general overview of a number of different (but equivalent) ways of formalizing the concept of effective calculability. Later chapters will develop a few of these ways in full detail.