Fix a prefix-free universal Turing machine $U$. Consider the following random process*. The state of the process is a bit-string $s$, initialized with the empty string (say). Suppose the value of the string on step $n$ is $s_n$. At the next step, we randomly generate a program $A$ using $U$, like in the definition of Chaitin's constant $\Omega$**. If $A$ doesn't halt we discard it and generate a new program. If it halts with output $t$ and $s_n$ is not a prefix of $t$ we also discard it and generate a new program. If $s_n$ is a prefix of $t$, we update the state according to $s_{n+1}:=t$. Note that $s_n$ is a prefix of $s_{n+1}$ i.e. at each step the string gets appendedAllowing the process to continue indefinitely, we get an infinite bit-string $s_{\infty}$. The question:What is the probability $p$ that $s_{\infty}$ is computable? Is $p > 0$?Of course $p$ a priori depends on $U$ but my intuition is that if it vanishes for some $U$ it vanishes for all, for approximately the same reason Kolmogorov complexity only weakly depends on $U$*This process is closely related to the concept of Solomonoff induction**This is done as follows. We generate an infinite sequence of bits $a$ by flipping a coin an infinite number of times. Since $U$ is prefix-free, there is a unique prefix $A$ of $a$ which is a valid program for $U$
Are randomly generated infinite patterns computable?
computability;randomness;universal computation;stochastic process
In the particular way you formulated the question the probability is 0. Because there are only countably many computable sequences, it suffices to show that for each computable sequence the probability is 0. So let's lets consider the sequence 000... (our reasoning works for any computable sequence). Suppose at some time step $s = 0^n$ for some $n$. Now, we search for a program that outputs a string starting with $0^n$ and halts. For each program outputting $0^m$ with $m>n$, there exists a program that is only $O(1)$ bits longer and also appends $1$ to this output (i.e. it outputs $0^m1$). Hence, there is a probability that $s$ is extended with wrong bits, and this probability does not depend on the length of $s$. Therefore, generating infinitely many zeros has 0 probability.