Skip to main content
2 of 2
added 85 characters in body
Dan
  • 1.3k
  • 1
  • 12
  • 15

Absolutely algorithmically random infinite sequence

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)?

Dan
  • 1.3k
  • 1
  • 12
  • 15