specified by the nonnegative integers . These are exactly the functions such that is periodic.
(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 . 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.
(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.