Algorithmic decidability questions.

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.