Fast but Useless
A while ago Scott Aaronson mentioned the following question to me while discussing questions around my thesis and a post of his: is there a function asymptotically dominating all recursive functions that *doesn't* allow you to solve the halting problem? He said he'd asked Carl Jokusch, who gave a 'high-powered' proof. I found an easy proof that proved something stronger:
Theorem: Let RAND be the Kolmogorov-random strings; then there's a function f dominating all recursive functions such that RAND is 'immune' (one can't compute an infinite subset of it) even given oracle access to f.
(HALT is Turing reducible to RAND--even truth-table reducible, which is bizarre--so it follows that HALT is not Turing reducible to f. Actually, the theorem remains true if you replace RAND with any immune set.)
Proof: Let B(x), B(x), ... be a (nonconstructive) enumeration of all total recursive bounds. At each stage we set finitely many values of f to screw up the ith oracle machine M[i]'s attempt to decide an infinite RAND-subset. At stage i we restrict ourselves to setting new values f(x) >B[j](x) for j <= i; this gets the growth condition.
Case I: There's a finite partial completion of f, subject to the constraints/commitments so far, causing M[i] to accept some non-random string x.
Then of course, fix these f-values, along with a big value f(i) to ensure convergence of our partial f to a total function.
Case II: For no such partial completion can M[i] be so induced.
Then M[i] is not a problem: no matter how we set the function hereafter, M[i] can only accept a finite subset of RAND. Otherwise, we could code in the f-values committed so far along with programs for B(x), B(x), ... B[i](x) into oracle-free machine M', which on input x dovetails over all admissible partial completions of the oracle looking for one that makes M[i] accept x. Then M' accepts an infinite RAND subset, impossible.
So in Case II just fix a big value for f(i) to help
convergence. Continue over all i to get the desired f.
I've also explored a dual question (are there non-r.e.-hard infinite subsets of RAND?), with only partial success:
i) There is no algorithm that computes HALT when given oracle access to any infinite subset of RAND;
ii) There are infinite subsets of the 1/2-random strings (not compressible by a factor of two) that aren't r.e.-hard.
Happy to get questions or comments. Lance Fortnow and others have interesting results about the computational power of 'dense enough' subsets of 1/2-RAND.