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$

  • 1
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Nov 18 '12 at 21:48
  • $\begingroup$ 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 $\endgroup$ – Squark Nov 18 '12 at 21:51
  • 3
    $\begingroup$ 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 $\endgroup$ – Squark Nov 19 '12 at 5:43
  • 2
    $\begingroup$ By the way, the answer obviously depends on the choice of $U$. It can probably be manipulated into any number we desire. $\endgroup$ – Andrej Bauer Nov 19 '12 at 13:34
  • 1
    $\begingroup$ @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 $\endgroup$ – Squark Nov 19 '12 at 13:53

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.

  • $\begingroup$ Thx! However I didn't follow your last remark. In 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? $\endgroup$ – Squark Feb 16 '13 at 19:45
  • $\begingroup$ 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. $\endgroup$ – Bruno Bauwens Feb 16 '13 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.