Skip to main content
1 of 2
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)

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

Dan
  • 1.3k
  • 1
  • 12
  • 15