Contents

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

(Conway).For every partial recursive functionfdefined on a subsetDof the natural numbers there exists a function such that(1)

is periodic for somedand takes rational values.(2)

There is some iterate such that for somejif and only ifmis inD.

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].

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

Contents