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

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

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

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

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