Let's call an infinite sequence of bits $f:N\rightarrow \{0,1\}$ absolutely random if any computably constructed subsequence is not computable, i.e. there aren't monotonic computable function $g:N \rightarrow N$ and computable function $h:N \rightarrow \{0,1\}$ such that $\forall n ~f(g(n)) = h(n)$.

Is it known definition? I'm sure it's not the same as Martin-Löf randomness, because Chaitin's constant is not absolutely random (we can construct infinite computable sequence of programs that are halting). EDIT: Looks like I was wrong and Chaitin's constant in fact is absolutely random.

How to prove that such function exists (or it's not)?

  • $\begingroup$ Why does not Chaitin's constant work? How do you construct g and h in this case? The n'th bit is given by the parity of the number of programs of size n, that halts, and I see no way to "peek" at a certain subsequence of this... Related: see also en.wikipedia.org/wiki/Chaitin%27s_constant#Super_Omega $\endgroup$ – Per Alexandersson Apr 1 '14 at 21:30
  • 1
    $\begingroup$ Isn't it the case that if we choose $f$ randomly (each value $f(n)$ independent, with probability 1/2 that $f(n)=0$), then the probability is 1 that $f$ is absolutely random? $\endgroup$ – Richard Stanley Apr 1 '14 at 22:40
  • $\begingroup$ Knuth gets stuck into the question of ways to define randomness in Section 3.5 of Volume 2 (Seminumerical Algorithms) of The Art Of Computer Programming, though maybe you are already beyond anything Knuth covers there. $\endgroup$ – Gerry Myerson Apr 1 '14 at 22:41
  • 4
    $\begingroup$ Recursion theory people call what you called as bi-immuness. It contains all the weakly-random and weakly-generic reals. $\endgroup$ – 喻 良 Apr 2 '14 at 1:29
  • 2
    $\begingroup$ Constructing an infinite computable sequence of halting programs shows that the Halting Problem is not bi-immune, but that argument doesn't work for Chaitin's constant. $\endgroup$ – Denis Hirschfeldt Apr 2 '14 at 2:05

As Liang Yu pointed out, this notion is known as bi-immunity. Chaitin's constant is in fact bi-immune, as is any Martin-Löf random real. Indeed, bi-immunity is much weaker than Martin-Löf randomness. Again as pointed out by Liang Yu, quite weak notions of randomness and (computability theoretic) genericity suffice to ensure bi-immunity, so the set of bi-immune reals is both comeager and conull.

| cite | improve this answer | |

We can easily construct such a function $f$, and indeed, there are continuum many such functions. The reason is that you've imposed only countably many requirements on $f$, which can each be satisfied by a finite piece of $f$, one after the other. So we can satisfy those requirements one-by-one.

Let's do the "forcing" manner of construction, which has an affinity with the Baire category theorem. That is, consider the space of all finite partial functions $p:n\to\mathbb{N}$, essentially the finite sequences of natural numbers, ordered by extension. For each computable functions $g$ and $h$, where $g$ is increasing, let $D_{g,h}$ be the set of such finite functions $p$ for which $p(g(n))\neq h(n)$ for some $n\in\text{dom}(p)$, that is, the set of conditions $p$ that have already satisfied the requirement imposed by $g$ and $h$. Any extension of such a $p$ to a total function $f$ will also satisfy the requirement impose by $g$ and $h$. The key thing to notice is that any condition $p$ can easily be extended to a condition $p'\in D_{g,h}$, because there will be some $n$ such that $p(g(n))$ is not yet defined, and we can extend $p$ to some $p'$ by defining $p'(g(n))$ in such a way that makes it different than $h(n)$, so that $p'\in D_{g,h}$. Another way to say this is that the sets $D_{g,h}$ are dense (and open) in the space of all finite partial functions. So we have countably many open dense requirements to meet. We can simply meet them one by one. That is, we can build a sequence of finite extensions $$f_0\subset f_1\subset f_2\cdots$$ such that the union function $f=\bigcup_n f_n$ has initial segments meeting all the requirements $D_{g,h}$. It follows that for every $g$ and $h$ there is some $n$ for which $f(g(n))\neq h(n)$ and so $f$ is absolutely random.

If you think carefully about it, what we have done in effect is to build a tree of finite approximations, such that every branch through this tree will be absolutely random. Thus, the construction provides continuum many absolutely random functions $f$.

| cite | improve this answer | |
  • $\begingroup$ Shortly, we sort all pairs $(g,h)$ and construct partial function $f$ step by step. At step $n$ we find big enough number $m$ and set $f(g_n(m)) = h_n(m) + 1$. In the end we just extend our partial function to total. Looks pretty straightforward :) $\endgroup$ – Dan Apr 2 '14 at 7:14
  • $\begingroup$ Yes, that's right. This kind of argument arises all over computability theory. $\endgroup$ – Joel David Hamkins Apr 2 '14 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.