(Conway). For every partial recursive function f defined on a subset D of the natural numbersthere 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.
(Conway). There exists a particular, explicitly constructible functionsuch 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.