# 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 "equally", 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}

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 "problem" and $$U$$ is a "universal problem solver". 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} $$T:=\inf_U \limsup_{t \to \infty} \frac{\nu(t)}{\nu_U(t)}$$

Obviously $$T < \infty$$. Finally, the questions:

Is T > 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<\infty$.)

• Thx for the answer! The 1st question seems to be settled. Regarding the 2nd question, I'm not sure I understood you. I don't consider different Turing machines, I consider different programs running on a single universal Turing machine. So tricks like changing the size of the alphabet aren't allowed. Or did you mean something else? – Vanessa Jul 7 '12 at 7:52
• Even if you don't allow alphabet changes, I think any U can be beaten by a U' that does the same as U except for some special class that it can handle a constant factor faster, which makes T a small constant smaller. – domotorp Jul 7 '12 at 9:09
• Wait, this isn't quite right. Your algorithms are a constant fraction of the sequence but they are not a constant fraction of the execution time since there algorithms of the same length which are much slower. This can be remedied as follows. Instead of hardcoding k into the algorithm we can hardcode another algorithm and force U to take at least as many steps as the other algorithm. However, it still doesn't prove T is positive, since the size of the fraction depends on Us length. Thus for every fixed U the limsup above is positive but the infimum can still be 0 – Vanessa Jul 7 '12 at 10:41
• Also you are right that for any U we have U' which recognizes precisely the special algorithms above and produces the right answer. This will make it run faster by a finite factor. So the infimum cannot be achieved but I still don't know whether it vanishes – Vanessa Jul 7 '12 at 10:43
• Your argument that $T=0$ doesn't work since any finite set of $A_i$ is responsible for a vanishing fraction of the execution time. Also it's obvious that T is finite without any assumptions since you can use the trivial $U$ which simply runs any algorithm as is – Vanessa Nov 17 '12 at 13:59

Maybe I misunderstood your question, or maybe my reasoning is flawed, but I disagree with @domotorp and think $T = 0$ with the reason stemming from the freedom you give by using $\inf_U$ in your definition. I outline my argument below.

To make my life easier, I am going to make your definition of $A$s slightly more precise. By input-less I will think about algorithms that run on the all 0s input, and by output of $A$ I will take the decision problem approach: halt and return $D(A) \in \{0,1\}$.

The $A$s (including those that don't halt) have some ordering which is easy (i.e. we have an algorithm $N$ running in $O(|A|)$ such that $N(A) = i$ if $A$ is the $i$th program in our ordering) to compute from their code. Now I will define a magical infinite string $d$ (over $\{0,1,\bot\}$). Let $A$ be the $i$th machine in our ordering, if $A$ halts then $d(i) = D(A)$ else $d(i) = \bot$. By $d(1, ..., k)$ I will mean the string $d$ truncated to the first $k$ bits.

Fix a favorite universal machine $V$ and consider the following sequence of universal machines $U_k$:

1. On input $A$, compute $i = N(A)$
2. Search $d(1,...,k)$ for index $i$ and output
3. If $i > k$ then output $V(A)$

What is the run-time of $U_k$ on input $A$? If $N(A) \leq k$ then it is $O(|A|)$, else it is $O(|A| + T(V(A))$ where $T(V(A))$ is the runtime of $V$ simulating $A$. Since you use $\inf_U$ in your definitions, I can reason about $U_\infty$ which is not a finite machine and simulates any $A$ in time $O(|A|)$.

Now, let us make two reasonable assumptions:

1. $\forall A \quad T(A) \in \Omega(|A|)$: no self-delimiting program returns an answer faster than its description.

2. $Pr_{halt}\{ T(A) \in \omega(|A|)\} = p > 0$: the probability $p$ that a halting program runs for strictly longer than its description is some non-zero.

Then under these assumptions we have that $\nu(t) \in o(\nu_{U_\infty}(t))$ and so T = 0.

• Artem, if you hardcode the answers for a finite number of algorithms it will not affect my limsup at all since the limit is dominated by algorithms with long execution times, and the execution times of any finite set are bounded, obviously. The reason the long execution times dominate despite the exponential penalty for algorithm length is precisely that the busy beaver function grows much faster than exponentially. It is true that I use infimum but you cannot change places between the inf and the limsup – Vanessa Jul 8 '12 at 19:12
• Btw I don't think @domotorp argument that T > 0 is correct, see my comments below his answer. Currently I still don't know whether T > 0 or not – Vanessa Jul 8 '12 at 19:15

The summation in the definition of $\nu$ is really annoying, so define $\nu_i(t) = E_{halt}(\min \{n: t_n \ge t\})$. Clearly, we have $1/\nu_i(t) = \Theta(P_{halt}(t_r \ge t))$. So $\sum_{k \le t} \nu_i(t)/\nu_i(k) = \Theta(\sum_{k\le t} P_{halt}(t_r \ge k)/P_{halt}(t_r \ge t))$, which with high probability is $\Theta(\sum_i t_i)$ with the sum taken until some program has runtime exceeding $t$. By this means, we should be able to recover $\nu$ from $\nu_i$.

Now, by programming $U$ to recognize the likely programs with very long runtimes, we can arrange $P_{halt}(t^U_r \ge t)$ to approach 0 much more rapidly than $P_{halt}(t_r \ge t)$ does. So the $\limsup_{t \rightarrow \infty} P_{halt}(t_r^U \ge t)/P_{halt}(t_r \ge t) = \limsup_{t \rightarrow \infty} \nu_i(t)/\nu^U_i(t)$ can be made arbitrarily close to zero by suitable choice of $U$. The same result should hold for $\nu$ itself, since this construction doesn't alter the runtime of the fast programs, which should dominate the sum-factors we saw above.