Timeline for Average performance of universal computation
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Jul 6, 2012 at 7:24 | vote | accept | Vanessa | ||
| Jul 6, 2012 at 7:07 | vote | accept | Vanessa | ||
| Jul 6, 2012 at 7:19 | |||||
| Jul 6, 2012 at 6:11 | vote | accept | Vanessa | ||
| Jul 6, 2012 at 7:06 | |||||
| Jul 5, 2012 at 22:43 | answer | added | Artem Kaznatcheev♦ | timeline score: 3 | |
| Jul 5, 2012 at 21:19 | comment | added | Marzio De Biasi | 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 | |
| Jul 5, 2012 at 20:06 | comment | added | Vanessa | @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 | |
| Jul 5, 2012 at 19:33 | comment | added | Marzio De Biasi | 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) | |
| Jul 5, 2012 at 18:22 | history | asked | Vanessa | CC BY-SA 3.0 |