1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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) $\endgroup$
    – Marzio De Biasi
    Commented Jul 5, 2012 at 19:33
  • $\begingroup$ @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 $\endgroup$
    – Vanessa
    Commented Jul 5, 2012 at 20:06
  • 1
    $\begingroup$ 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 $\endgroup$
    – Marzio De Biasi
    Commented Jul 5, 2012 at 21:19

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Good point. We still need to prove that $T(U)$ is infinite for all $U$ but it seems very likely $\endgroup$
    – Vanessa
    Commented Jul 6, 2012 at 7:07
  • $\begingroup$ Actually it's obvious since it's enough to consider any problem with complexity $2^n$ or higher $\endgroup$
    – Vanessa
    Commented Jul 6, 2012 at 7:24
  • $\begingroup$ 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 $\endgroup$
    – Vanessa
    Commented Jul 6, 2012 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.