Computability Theory

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 if π has a run of x or more 7’ ...