Highly Random Function

Question

Call a function $f\colon\mathbb{R}\to\mathbb{R}$ highly random if:

• Say $T$ is a Turing machine which attempts to compute values of $f$. Given enough values to compute, the cumulative error of $T$'s estimates will be no better than any other which attempts to do the same, not even if given every other value than the one it is trying to compute. This is clearly a much stronger condition than $f$ being non-computable.
• For almost all choices of $(a,b)$, $f(a) \neq f(b).$ However, $f$ is not necessarily injective.

Here are some questions about "highly random functions" like $f$:

1. Are the requirements impossible to fulfill? That is, is there no such function because the characteristics are in some way contradictory?
2. If not, is it possible to define such a function?
3. Would it be possible to construct such a function if you had access to a random bit oracle?

For clarification and rigor's sake, a random bit oracle takes a query which consists of a real number. It responds with a bit. There is no algorithm or process which will predict the reponse bit any better than $\frac{1}{2}$ of the time, given access to any other set of queries and responses, except the one it is trying to predict. This is quite interesting by itself in my opinion, but it seems to me that it would be impossible to prove any specific phenomenon satisfied those constraints.

Strangely, it seems to me that access to some $f$ would allow the enumeration of the real numbers. You could just evaluate $f$ at every natural number and intuitively it seems like you would get to every real (the first condition of highly random functions implies a uniform distribution.)

Answer 1

When I read this question, I immediately thought of a way to (slightly non-rigorously) prove the impossibility of such a function.

First, we must prove a small result about how often an output of $f$ lies in any specific interval.

Let us create a new set $\mathbb M$ composed of elements of this form: $(r, f(r)$, $r \in \mathbb R$.

Now, $a$ and $b$ are two arbitrary non-equal real numbers. Say that anything more than almost none of $\mathbb M$ was composed of elements where $f(r) \in (a, b)$. Then every interval of the form $(a - n(b - a), b - n(b - a))$, $n \in \mathbb Z$ would have to have the same “measure,” in terms of how much of $\mathbb M$ was composed of elements where $f(r)$ is in that interval, otherwise the definition of $f$ would be violated, because some Turing machine picking numbers in one interval would have different cumulative error from one picking from another.

However, that means there are infinitely many non-overlapping subsets of $\mathbb M$ which each make up more than an “almost none” portion of it, which is impossible. Therefore, the assumption that anything more than almost none of $\mathbb M$ was composed of elements where $f(r) \in (a, b)$ is false.

Therefore: $f(r)$ almost never lies in a given interval $(a, b)$, where $a$ and $b$ are non-equal, finite, real numbers.

Now we can move onto the main part.

Say the function $f$ is as a sort of map, to make a set called $\mathbb L$. $\mathbb L$ consists of the set of all tuples $(r, f(r), f(r^3), f(r^5))$, where $r \in \mathbb R$. Now, for every element of $\mathbb L$ and its outputs $A = f(r)$, $B = f(r^3)$, $C=f(r^5)$, it can fall into one of 3 scenarios:

(1) Some of $A$, $B$, and $C$ are equal, but not all three.

(2) All three are equal.

(3) All three are different.

It's easy to see that according to the definition of $f$, almost none of $\mathbb L$ resides in scenario (1).

It's also easy to see that because almost no pairs of inputs $(a, b)$ have the property that $f(a) = f(b)$, almost no triples have the same, so almost none of $\mathbb L$ resides in scenario (2) either.

Now, let’s look at scenario (3). There are 6 possible specific outcomes of (3):

$A < B < C$

$A < C < B$

$B < A < C$

$B < C < A$

$C < B < A$

$C < A < B$

By the definition of $f$, $f(r)$ gives no information about $f(r^3)$ or $f(r^5)$ (by the first point), so $A$, $B$, and $C$ are independent, and they could be named differently without changing the composition of $\mathbb L$ with respect to the probabilities of (1), (2), (3), or any of the specific outcomes of (3). Therefore, none of the specific outcomes of (3) must make up a larger portion of $\mathbb L$ than any other.

Now, let us look how much of $\mathbb L$ is made up of elements where $A < B < C$.

Let us consider just $A$ and $C$ ($B$ is independent anyway). We have two real numbers whose difference is finite and non-zero, and therefore, almost no $B$s lie in between them, by the first “proof”, so almost none of $\mathbb L$ is made up of elements where $A < B < C$.

Since $A$, $B$, and $C$ are independent, all 6 of the specific outcomes make up the same portion of $\mathbb L$.

Therefore, almost none of $\mathbb L$ lies in any of the specific scenarios of (3), and almost none of $\mathbb L$ lies in scenario 3 as a whole.

We have shown that any element of $\mathbb L$ must fall into one of three scenarios, and that none of them make up any more than almost none of $\mathbb L$ as a whole, and since $\mathbb L$ has cardinality equal to $\mathbb R$, this is a contradiction.

The assumption that $f$ exists must be false.

This also implies that for any function over the real numbers, there exists a difference between the best and worst Turing machines at estimating $f$ over the real numbers, at least given access to the any other values of the function besides the one it is trying to compute.