<p>By $T(A)$ I will mean the runtime of $A$ on the empty input, and will define $T(A) = \infty$ if $A$ doesn't halt. By $|A|$ I mean the length of $A$ in bits.</p>

<p>What you are trying to calculate in part (1) is:</p>

<p>$$T = \sum_{A | T(A) &lt; \infty} \frac{1}{2^{|A|}}T(A)$$</p>

<p>Where the fraction is the Chaitin probability of generating program $A$. For each length $n$ there is (at least) one machine $A_n$ such that for all halting $A$ with $|A| = n$ we have $T(A) \leq T(A_n) = BB(n)$. Here $BB$ is the relevant <a href="http://en.wikipedia.org/wiki/Busy_beaver" rel="nofollow noreferrer">busy-beaver function</a>, which grows faster than any computable function, in particular $BB(n) &gt; 2^n$. From this we have:</p>

<p>$$T \geq  \sum_{n = 1}^{\infty} \frac{1}{2^n}BB(n) &gt; \sum_{n = 1}^{\infty} 1$$</p>

<p>Thus your sum does not converge, and $T$ is not finite. I guess that answers the rest of your questions, too. If you want to achieve your goal, then you need to pick a better density function on programs, maybe something where probability of $A$ is proportional to say $\frac{1}{2^{BB(|A|)}}$. However, for learning more about this I recommend <a href="https://cs.stackexchange.com/">CS.SE</a>.</p>

CC BY-SA 3.0
2012-07-06T07:07:03.423Z
Good point. We still need to prove that $T(U)$ is infinite for all $U$ but it seems very likely
Vanessa
CC BY-SA 3.0
2012-07-06T07:24:52.397Z
Actually it's obvious since it's enough to consider any problem with complexity $2^n$ or higher
Vanessa
CC BY-SA 3.0
2012-07-06T11:04:59.507Z
Regarding the use of a different probability density I don't think it's what I need since this probability density is related to artificial intelligence through concepts such as Solomonoff induction and the intelligence measure introduced in http://arxiv.org/abs/0712.3329. On the other hand the use of simple expectation value as a performance measure is unsuccessful
Vanessa
CC BY-SA 3.0
2012-07-05T22:43:53.783Z
2012-07-05T22:49:04.767Z
2017-04-13T12:48:30.830Z
Artem Kaznatcheev
<p>This post is related to <a href="https://cstheory.stackexchange.com/questions/11902/efficient-universal-problem-solver">my previous question</a> but takes a different angle</p>

<p>There are several related questions in here</p>

<p>Consider an input-less algorithm $A$ generated randomly using a prefix-free universal Turing machine, like in the definition of Chaitin's constant. Consider $T$ the conditional expectation value of $A$'s execution time, the condition being "$A$ halts"</p>

<blockquote>
  <p>Is T finite?</p>
</blockquote>

<p>Consider $U$ an algorithm accepting input-less halting algorithms as input and producing their output as ouput. $U$ is essentially a universal Turing machine or perhaps a "universal algorithm" since we're assuming all algorithms run on the same "hardware". Consider $T(U)$ the conditional expectation value of the execution time of $U(A)$, the condition still being "$A$ halts"</p>

<blockquote>
  <p>Is $T(U)$ finite for some $U$?</p>
</blockquote>

<p>Obviously, the answer to the 2nd question is "yes" if the answer to the 1st question is "yes". If the answer to the 2nd question is "no", the following questions become trivial</p>

<p>Consider $T_{min} = \inf_{U} T(U)$</p>

<blockquote>
  <p>Is there $U_{opt}$ s.t. $T(U_{opt}) = T_{min}$?</p>
</blockquote>

<p>Consider infinite sequences $U_1, U_2...$ s.t. $\lim_{i \to \infty}T(U_i)=T_{min}$</p>

<blockquote>
  <p>Is there an algorithm $V$ that takes a natural number $i$ for input and outputs $U_i$ as above?</p>
</blockquote>

<p>Obviously, "yes" for the 3rd question implies "yes" for the 4th</p>

CC BY-SA 3.0
2012-07-05T19:33:22.810Z
what is exactly "the conditional expectation value of A's execution time"? We have that for every A that halts, $T(A)\leq S(|A|)$ where S(n) is the the largest number of steps taken by a n-states Turing machine started on an initially blank tape before halting. S(|A|) is finite, but obviously increasing with respect to |A| (see [the generalized busy beaver function](http://en.wikipedia.org/wiki/Busy_beaver))
Marzio De Biasi
CC BY-SA 3.0
2012-07-05T20:06:01.737Z
@MarzioDeBiasi A is a random variable, and so is its execution time. Hence I can ask what is its expectation value i.e. average. The conditioning is needed to exclude infinite execution times from the average
Vanessa
CC BY-SA 3.0
2012-07-05T21:19:36.400Z
ok; for every $A$, its execution time is $\geq 0$ so the expected execution time $T$ of $A$ is equal to $\Sigma_{i=1}^\infty P(A \geq i)$ (the sum of the probabilities of $A$ being greater than $i$) which is divergent
Marzio De Biasi
<cc.complexity-theory><ai.artificial-intel><universal-computation>
Average performance of universal computation
Vanessa
# Average performance of universal computation

(Asked by: username_0 on 2012-07-05)

This post is related to [my previous question](https://cstheory.stackexchange.com/questions/11902/efficient-universal-problem-solver) but takes a different angle

There are several related questions in here

Consider an input-less algorithm $A$ generated randomly using a prefix-free universal Turing machine, like in the definition of Chaitin's constant. Consider $T$ the conditional expectation value of $A$'s execution time, the condition being "$A$ halts"

> Is T finite?

Consider $U$ an algorithm accepting input-less halting algorithms as input and producing their output as ouput. $U$ is essentially a universal Turing machine or perhaps a "universal algorithm" since we're assuming all algorithms run on the same "hardware". Consider $T(U)$ the conditional expectation value of the execution time of $U(A)$, the condition still being "$A$ halts"

> Is $T(U)$ finite for some $U$?

Obviously, the answer to the 2nd question is "yes" if the answer to the 1st question is "yes". If the answer to the 2nd question is "no", the following questions become trivial

Consider $T\_{min} = \inf\_{U} T(U)$

> Is there $U\_{opt}$ s.t. $T(U\_{opt}) = T\_{min}$?

Consider infinite sequences $U\_1, U\_2...$ s.t. $\lim\_{i \to \infty}T(U\_i)=T\_{min}$

> Is there an algorithm $V$ that takes a natural number $i$ for input and outputs $U\_i$ as above?

Obviously, "yes" for the 3rd question implies "yes" for the 4th

**Tags:** cc.complexity-theory, ai.artificial-intel, universal-computation

> **Comments:**
> **username_1**: what is exactly "the conditional expectation value of A's execution time"? We have that for every A that halts, $T(A)\leq S(|A|)$ where S(n) is the the largest number of steps taken by a n-states Turing machine started on an initially blank tape before halting. S(|A|) is finite, but obviously increasing with respect to |A| (see [the generalized busy beaver function](http://en.wikipedia.org/wiki/Busy_beaver))  
> **username_0**: @MarzioDeBiasi A is a random variable, and so is its execution time. Hence I can ask what is its expectation value i.e. average. The conditioning is needed to exclude infinite execution times from the average  
> **username_1**: ok; for every $A$, its execution time is $\geq 0$ so the expected execution time $T$ of $A$ is equal to $\Sigma_{i=1}^\infty P(A \geq i)$ (the sum of the probabilities of $A$ being greater than $i$) which is divergent  

---

## 1 answers

### Answer by username_2 on 2012-07-05. Score: 3 | Accepted answer

By $T(A)$ I will mean the runtime of $A$ on the empty input, and will define $T(A) = \infty$ if $A$ doesn't halt. By $|A|$ I mean the length of $A$ in bits.

What you are trying to calculate in part (1) is:

$$T = \sum\_{A | T(A) < \infty} \frac{1}{2^{|A|}}T(A)$$

Where the fraction is the Chaitin probability of generating program $A$. For each length $n$ there is (at least) one machine $A\_n$ such that for all halting $A$ with $|A| = n$ we have $T(A) \leq T(A\_n) = BB(n)$. Here $BB$ is the relevant [busy-beaver function](http://en.wikipedia.org/wiki/Busy_beaver), which grows faster than any computable function, in particular $BB(n) > 2^n$. From this we have:

$$T \geq \sum\_{n = 1}^{\infty} \frac{1}{2^n}BB(n) > \sum\_{n = 1}^{\infty} 1$$

Thus your sum does not converge, and $T$ is not finite. I guess that answers the rest of your questions, too. If you want to achieve your goal, then you need to pick a better density function on programs, maybe something where probability of $A$ is proportional to say $\frac{1}{2^{BB(|A|)}}$. However, for learning more about this I recommend [CS.SE](https://cs.stackexchange.com/).

> **Comments:**
> **username_0**: Good point. We still need to prove that $T(U)$ is infinite for all $U$ but it seems very likely  
> **username_0**: Actually it's obvious since it's enough to consider any problem with complexity $2^n$ or higher  
> **username_0**: Regarding the use of a different probability density I don't think it's what I need since this probability density is related to artificial intelligence through concepts such as Solomonoff induction and the intelligence measure introduced in http://arxiv.org/abs/0712.3329. On the other hand the use of simple expectation value as a performance measure is unsuccessful  

---

