Complexity of universal computation on random input

Question

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}<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 "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}\right\})$$ $$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?

Answer 1

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$.)

Answer 2

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.

Answer 3

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.