[FOM] Can someone give me an example of...

[Andrej Bauer]

On Sunday 19 February 2006 17:24, Rob Arthan wrote:
> More precisely, writing N for the set of natural numbers and Q for the set
> of rationals, I think he was looking for a total recursive function f : N
> -> Q with range contained in some interval [A, B] such that for any
> recursively enumerable (r.e.) infinite subset X = {x_1, x_2, ...} of N, the
> sequence of values f(x_1), f(x_2), ... is not a Cauchy sequence.

> Here follows a sketch of how to construct such an f, which I think works.

If I understand your construction correctly, you've defined a sequence of 
reals, not rationals, i.e., f : N --> R. Nevertheless, such a sequence would 
still be interesting.

> It remains to enumerate a sequence Y_K of subsets of N, such that if X is
> any infinite r.e. set, then for some K, Y_K is an infinite subset of X. For
> this to yield the desired recursive f : N -> Q, we need to present the Y_K
> effectively, e.g., as a (total) recursive function g: N >< N -> {0, 1} such
> that n is in Y_K iff. g(n, K) = 1.

Agreed up to here, but I doubt what follows describes such a function g. 
Observe that, given such a g, the Y_K are recursive sets.

> This reduces to a scheduling problem: an 
> arbitrary r.e. set X is recogised by some Turing machine, T, say; if one
> conducts a fair parallel simulation of T(1), T(2), T(3), ..., discarding
> members of X that are less than ones already encountered, then, if X is
> infinite, one will eventually enumerate an infinite subset Y of X in
> increasing order.

This Y is r.e., but in general not recursive, correct?

> A fair parallel simulation of these simulations for all 
> possible Turing machines, T_m, gives an implementation of g and hence of f.

I presume the function g would be defined as

  g(n,K) = 1  if n is in Y_K
  g(n,K) = 0  if n is not in Y_K

Since the Y_K you obtain from the scheduling procedure described above are 
r.e. but not recursive, this g is not computable. So I am afraid your 
construction does not work (and relieved, obviously, as I claimed the 
opposite). Now it's your turn to poke holes in my argument.

Andrej Bauer