[FOM] Can someone give me an example of...
Andrej Bauer
Andrej.Bauer at andrej.com
Sun Feb 19 18:03:43 EST 2006
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
More information about the FOM
mailing list