<p>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.)</p>

<p>For your other question, you gotto be more specific about what kind of Turing-machines you allow. Probably the answer is no, see <a href="http://en.wikipedia.org/wiki/Linear_speedup_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Linear_speedup_theorem</a>.</p>

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

CC BY-SA 3.0
2012-07-07T07:52:01.920Z
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
CC BY-SA 3.0
2012-07-07T09:09:09.187Z
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
CC BY-SA 3.0
2012-07-07T10:41:23.880Z
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
CC BY-SA 3.0
2012-07-07T10:43:12.787Z
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
CC BY-SA 3.0
2012-11-17T13:59:15.830Z
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
CC BY-SA 3.0
2012-11-24T17:02:23.900Z
I am sorry but probably your question still was (and is) not clear to me...
domotorp
CC BY-SA 3.0
2012-07-07T06:24:22.607Z
2012-07-07T18:07:37.773Z
2012-07-07T18:07:37.773Z
domotorp
<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-29T20:42:50.167Z
2014-06-29T20:42:50.167Z
Ben Standeven
<p>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. </p>

<hr>

<p>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\}$.</p>

<p>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.</p>

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

<ol>
<li>On input $A$, compute $i = N(A)$</li>
<li>Search $d(1,...,k)$ for index $i$ and output</li>
<li>If $i &gt; k$ then output $V(A)$</li>
</ol>

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

<p>Now, let us make two reasonable assumptions:</p>

<ol>
<li><p>$\forall A \quad T(A) \in \Omega(|A|)$: no self-delimiting program returns an answer faster than its description.</p></li>
<li><p>$Pr_{halt}\{ T(A) \in \omega(|A|)\} = p &gt; 0$: the probability $p$ that a halting program runs for strictly longer than its description is some non-zero.</p></li>
</ol>

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

CC BY-SA 3.0
2012-07-08T19:12:02.820Z
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
CC BY-SA 3.0
2012-07-08T19:15:39.993Z
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
CC BY-SA 3.0
2012-07-08T03:32:47.060Z
2012-07-08T03:32:47.060Z
Artem Kaznatcheev
<p>This post is a refinement of <a href="https://cstheory.stackexchange.com/questions/11941/average-performance-of-universal-computation">a previous question</a> which turned out to be trivial</p>
<p>It is also related to <a href="https://cstheory.stackexchange.com/questions/11902/efficient-universal-problem-solver">another previous question</a></p>
<p><strong>Motivation:</strong> 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 <a href="http://arxiv.org/abs/0712.3329" rel="nofollow noreferrer">Legg and Hutter</a> and other works on universal intelligence</p>
<p><strong>Formal statement of question</strong>: Consider an input-less algorithm <span class="math-container">$A$</span> generated randomly using a prefix-free universal Turing machine, like in the definition of Chaitin's constant. Suppose further we have an infinite sequence <span class="math-container">$A_1, A_2, A_3...$</span> of such algorithms, each generated randomly and independently of the others. Denote <span class="math-container">$t_1, t_2, t_3...$</span> the execution times of these algorithms. We can then define</p>
<p><span class="math-container">$$\nu(t):=E_{halt}(\max\left\{{n:\sum_{i=1}^n{t_i}&lt;t}\right\})$$</span></p>
<p>Here <span class="math-container">$E_{halt}$</span> is conditional expectation value, the condition being that all algorithms halt. In other words, <span class="math-container">$\nu(t)$</span> is the average number of algorithms that can be executed during time <span class="math-container">$t$</span>, 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 <span class="math-container">$A$</span> had a finite value <span class="math-container">$\tau$</span>, <span class="math-container">$\nu(t)$</span> would behave asymptotically as <span class="math-container">$t / \tau$</span>. However <span class="math-container">$\tau$</span> 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 <span class="math-container">$\nu(t)$</span> grows much slower than linearly.</p>
<p>Now consider <span class="math-container">$U$</span> a universal computer i.e. an algorithm taking an input-less algorithm <span class="math-container">$B$</span> for input and producing <span class="math-container">$B$</span>'s output for output. My point of view is that <span class="math-container">$B$</span> is a &quot;problem&quot; and <span class="math-container">$U$</span> is a &quot;universal problem solver&quot;. It seems reasonable to assume that if <span class="math-container">$U$</span> represents an intelligent agent it should in some sense perform better than simple execution of <span class="math-container">$B$</span>. 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</p>
<p><span class="math-container">$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$</span></p>
<p>Denote <span class="math-container">$t^U_1, t^U_2, t^U_3...$</span> the execution times of <span class="math-container">$U$</span> given the input <span class="math-container">$A_1, A_2, A_3...$</span>. Define</p>
<p><span class="math-container">$$\nu_U(t):=E_{halt}(\max\left\{{n:\sum_{i=1}^n{t^U_i}&lt;t}\right\})$$</span>
<span class="math-container">$$T:=\inf_U \limsup_{t \to \infty} \frac{\nu(t)}{\nu_U(t)}$$</span></p>
<p>Obviously <span class="math-container">$T &lt; \infty$</span>. Finally, the questions:</p>
<blockquote>
<p>Is T &gt; 0?</p>
<p>Is T achieved for a specific <span class="math-container">$U$</span> i.e. is it a minimum?</p>
</blockquote>

CC BY-SA 3.0
2012-07-06T19:53:38.130Z
This is sort of like taking the average value of a http://en.wikipedia.org/wiki/Kolmogorov_complexity
Joshua Herman
<cc.complexity-theory><ai.artificial-intel><universal-computation>
Complexity of universal computation on random input
Vanessa
# Complexity of universal computation on random input

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

This post is a refinement of [a previous question](https://cstheory.stackexchange.com/questions/11941/average-performance-of-universal-computation) which turned out to be trivial

It is also related to [another previous question](https://cstheory.stackexchange.com/questions/11902/efficient-universal-problem-solver)

**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](http://arxiv.org/abs/0712.3329) 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 username_4 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?

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

> **Comments:**
> **username_1**: This is sort of like taking the average value of a http://en.wikipedia.org/wiki/Kolmogorov_complexity  

---

## 3 answers

### Answer by username_2 on 2012-07-07. Score: 2

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

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  
> **username_0**: 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  
> **username_0**: 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  
> **username_0**: 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  
> **username_2**: I am sorry but probably your question still was (and is) not clear to me...  

---

### Answer by username_3 on 2014-06-29. Score: 0

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.


---

### Answer by username_4 on 2012-07-08. Score: 0

Maybe I misunderstood your question, or maybe my reasoning is flawed, but I disagree with @username_2 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.

> **Comments:**
> **username_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  
> **username_0**: Btw I don't think @username_2 argument that T > 0 is correct, see my comments below his answer. Currently I still don't know whether T > 0 or not  

---

