Complexity of universal computation on random input This post is a refinement of a previous question which turned out to be trivial
It is also related to another previous question
Motivation: A property commonly ascribed to artificial intelligence is the ability to solve generic problems. In my opinion, this must be supplemented by a requirement of efficiency, otherwise any solvable problem can be solved by brute force which would hardly count for intelligence. Therefore it seems natural to explore the complexity bounds of universal problem solvers. Also, rather than treating all problems &quot;equally&quot;, it makes sense to focus on problems with low Kolmogorov complexity which is elegantly achieved by generating random programs for a prefix-free universal Turing machine. The significance of these random programs in the context of artificial intelligence was acknowledged in the context of Solomonoff induction, the intelligence measure introduced by Legg and Hutter and other works on universal intelligence
Formal statement of question: Consider an input-less algorithm $A$ generated randomly using a prefix-free universal Turing machine, like in the definition of Chaitin's constant. Suppose further we have an infinite sequence $A_1, A_2, A_3...$ of such algorithms, each generated randomly and independently of the others. Denote $t_1, t_2, t_3...$ the execution times of these algorithms. We can then define
$$\nu(t):=E_{halt}(\max\left\{{n:\sum_{i=1}^n{t_i}&lt;t}\right\})$$
Here $E_{halt}$ is conditional expectation value, the condition being that all algorithms halt. In other words, $\nu(t)$ is the average number of algorithms that can be executed during time $t$, assuming the algorithms are sampled randomly from our ensemble, but avoiding algorithms which don't halt. If the conditional expectation value of the execution time of $A$ had a finite value $\tau$, $\nu(t)$ would behave asymptotically as $t / \tau$. However $\tau$ is infinite since the busy beaver function grows (much) faster than exponentially, as pointed out by Artem Kaznatcheev in response to my previous question. Hence $\nu(t)$ grows much slower than linearly.
Now consider $U$ a universal computer i.e. an algorithm taking an input-less algorithm $B$ for input and producing $B$'s output for output. My point of view is that $B$ is a &quot;problem&quot; and $U$ is a &quot;universal problem solver&quot;. It seems reasonable to assume that if $U$ represents an intelligent agent it should in some sense perform better than simple execution of $B$. One is reminded of the anecdote about Gauss when his school teacher gave the class an assignment to sum all numbers from 1 to 100. Instead of doing it head-on, like the teacher intended, Gauss discovered the formula
$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$
Denote $t^U_1, t^U_2, t^U_3...$ the execution times of $U$ given the input $A_1, A_2, A_3...$. Define
$$\nu_U(t):=E_{halt}(\max\left\{{n:\sum_{i=1}^n{t^U_i}&lt;t}\right\})$$
$$T:=\inf_U \limsup_{t \to \infty} \frac{\nu(t)}{\nu_U(t)}$$
Obviously $T &lt; \infty$. Finally, the questions:

Is T &gt; 0?
Is T achieved for a specific $U$ i.e. is it a minimum?
Yes, T>0. I am not sure I correctly get all your conditions, so I suppose that each $A_i$ is an algorithm and each of them contains an upper bound for its running time. A constant fraction of the algorithms will be the following type: "Run U on ``This'' program and if it stops in less then k steps, then output something different from its output, otherwise stop after k steps". obviously U cannot run faster than such an algorithm. (Here faster means more than a constant factor faster.)

For your other question, you gotto be more specific about what kind of Turing-machines you allow. Probably the answer is no, see http://en.wikipedia.org/wiki/Linear_speedup_theorem.

Update 7/7 to Squark's comment: I see, you are right, I have proved that for every U the limsup >0. But if you take inf for all U, then you can take a U that knows the answer for the first many A_i and need not spend any time on them, and with high probability many of our random A_i will be from the first many, so T will go to 0. (Here I suppose that $t_i^U\le t_i$ which is not necessary, as programs can have never needed parts, but without this I cannot even prove $T&lt;\infty$.)