Contents Next: Existence of stopping Up: Generalizations of problem. Previous: Generalizations of problem.

J. H. Conway [26] proved the remarkable result that a simple generalization of the problem is algorithmically undecidable. He considers the class of periodically piecewise linear functions having the structure

specified by the nonnegative integers . These are exactly the functions such that is periodic.

### Theorem O

(Conway). For every partial recursive function f defined on a subset D of the natural numbers there exists a function such that

(1) is periodic for some d and takes rational values.

(2) There is some iterate such that for some j if and only if m is in D.

(3) for the minimal such that is a power of 2.

Conway's proof actually gives in principle a procedure for explicitly constructing such a function g given a description of a Turing machine that computes f. He carried out this procedure to find a function g associated to a particular partial recursive function f having the property that , where is the nth prime; this is described in Guy [37]. By choosing a particular partial recursive function whose domain is not a recursive subset of , e.g., a function that encodes the halting problem for Turing machines, we obtain the following corollary of Theorem O.

### Theorem P

(Conway). There exists a particular, explicitly constructible function such that is periodic for a finite modulus d and takes rational values, for which there is no Turing machine that, when given n, always decides in a finite number of steps whether or not some iterate with is a power of 2.

Contents Next: Existence of stopping Up: Generalizations of problem. Previous: Generalizations of problem.