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 **n**th
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.