<p>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). </p>

<p>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&gt;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.</p>

CC BY-SA 3.0
2013-02-16T19:45:26.783Z
Thx! However I didn't follow your last remark. In http://www.vetta.org/documents/disSol.pdf Shane Legg uses a prefix free universal Turing machine to define Solomonoff induction. What do you mean by a monotone machine? Can you give a reference?
Vanessa
CC BY-SA 3.0
2013-02-16T22:29:00.277Z
Indeed, I was mistaken. I looked at Li and Vitanyi, and there I saw Solomonoff induction goes by a-priori probability. The probability to observe a fixed computable sequence is positive. To me it seems more natural to define such a problem with monotone complexity. See cmi.univ-mrs.fr/~ashen/mathtext/uspshen/final.pdf for details. When Solomonoff induction would be defined with monotone machines, a fixed computable sequence is again observed with positive probability like it should be.
Bruno Bauwens
CC BY-SA 3.0
2013-02-16T15:54:11.453Z
2013-02-16T22:18:44.567Z
2013-02-16T22:18:44.567Z
Bruno Bauwens
<p>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 <em>not</em> a prefix of $t$ we also discard it and generate a new program. If $s_n$ <em>is</em> 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</p>

<p>Allowing the process to continue indefinitely, we get an infinite bit-string $s_{\infty}$. The question:</p>

<blockquote>
  <p>What is the probability $p$ that $s_{\infty}$ is computable? Is $p &gt; 0$?</p>
</blockquote>

<p>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$</p>

<p>*This process is closely related to the concept of Solomonoff induction</p>

<p>**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$</p>

CC BY-SA 3.0
2012-11-18T21:48:08.337Z
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 http://en.wikipedia.org/wiki/Chaitin's_constant.
Andrej Bauer
CC BY-SA 3.0
2012-11-18T21:51:13.997Z
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
Vanessa
CC BY-SA 3.0
2012-11-19T05:43:59.190Z
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
Vanessa
CC BY-SA 3.0
2012-11-19T05:47:10.477Z
@AndrejBauer Are tou unsatisfied with my clarification? Can you pls comment?
Vanessa
CC BY-SA 3.0
2012-11-19T13:33:45.283Z
I am probably being dense here, but why is $s$ a prefix of $s'$? I think you are making an assumption that I am not.
Andrej Bauer
CC BY-SA 3.0
2012-11-19T13:34:39.133Z
By the way, the answer obviously depends on the choice of $U$. It can probably be manipulated into any number we desire.
Andrej Bauer
CC BY-SA 3.0
2012-11-19T13:53:00.203Z
@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
Vanessa
CC BY-SA 3.0
2012-11-20T02:08:08.877Z
Thanks for explaining, the formulation seems ok. And yes, if $p = 0$ then that fact shouldn't depend on $U$.
Andrej Bauer
<computability><randomness><universal-computation><stochastic-process>
Are randomly generated infinite patterns computable?
Vanessa
# Are randomly generated infinite patterns computable?

(Asked by: username_0 on 2012-11-18)

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$

**Tags:** computability, randomness, universal-computation, stochastic-process
> **Comments:**
> **username_1**: 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 http://en.wikipedia.org/wiki/Chaitin's_constant.  
> **username_0**: 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  
> **username_0**: 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  
> **username_0**: @AndrejBauer Are tou unsatisfied with my clarification? Can you pls comment?  
> **username_1**: I am probably being dense here, but why is $s$ a prefix of $s'$? I think you are making an assumption that I am not.  
> **username_1**: By the way, the answer obviously depends on the choice of $U$. It can probably be manipulated into any number we desire.  
> **username_0**: @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  
> **username_1**: Thanks for explaining, the formulation seems ok. And yes, if $p = 0$ then that fact shouldn't depend on $U$.  

---

## 1 answers

### Answer by username_2 on 2013-02-16. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: Thx! However I didn't follow your last remark. In http://www.vetta.org/documents/disSol.pdf Shane Legg uses a prefix free universal Turing machine to define Solomonoff induction. What do you mean by a monotone machine? Can you give a reference?  
> **username_2**: Indeed, I was mistaken. I looked at Li and Vitanyi, and there I saw Solomonoff induction goes by a-priori probability. The probability to observe a fixed computable sequence is positive. To me it seems more natural to define such a problem with monotone complexity. See cmi.univ-mrs.fr/~ashen/mathtext/uspshen/final.pdf for details. When Solomonoff induction would be defined with monotone machines, a fixed computable sequence is again observed with positive probability like it should be.  

---

