# Are randomly generated infinite patterns computable?

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 appended

Allowing 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$

-
What is $S$? You never mentioned it in your description. Also, your question does not make any sense, as in the definition of Chaitin's constant there is no "random generation of a program". The constant is defined as a certain infinite sum, see en.wikipedia.org/wiki/Chaitin's_constant. – Andrej Bauer Nov 18 '12 at 21:48
I wrote "Letting the process to continue, we get an infinite bit-string S" i.e. S is what you get after an infinite amount of time from s, as you let it go longer and longer. Regarding Chaitin's constant, it can be regarded as the probability of a random program to halt – Squark Nov 18 '12 at 21:51
Friends, if you are down voting the question, pls explain what is wrong with it. So far there has been one complaint to which I replied. I apologize if I express myself poorly, but give me a chance to correct/explain. I assure you the question makes sense – Squark Nov 19 '12 at 5:43
By the way, the answer obviously depends on the choice of $U$. It can probably be manipulated into any number we desire. – Andrej Bauer Nov 19 '12 at 13:34
@AndrejBauer : $s$ is a prefix of $s'$ by definition, because we only accept $A$ with this property. Essentially I take the conditional probability distribution of programs with this condition. Regarding dependance on $U$ my intuition is that the vanishing of $p$ doesn't depend on it for approximately the same reason Kolmogorov complexity only weakly depends on $U$. However if you can prove me wrong I'd be glad to hear it – Squark Nov 19 '12 at 13:53

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.