# Average performance of universal computation

This post is related to my previous question 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

• 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) – Marzio De Biasi Jul 5 '12 at 19:33
• @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 Jul 5 '12 at 20:06
• 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 Jul 5 '12 at 21:19

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, 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.

• Good point. We still need to prove that $T(U)$ is infinite for all $U$ but it seems very likely – Vanessa Jul 6 '12 at 7:07
• Actually it's obvious since it's enough to consider any problem with complexity $2^n$ or higher – Vanessa Jul 6 '12 at 7:24
• 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 arxiv.org/abs/0712.3329. On the other hand the use of simple expectation value as a performance measure is unsuccessful – Vanessa Jul 6 '12 at 11:04