Crank up your Turing machine -- it needs to perform an infinite number of tasks simultaneously. It's the Hilbert Hotel for Turing machines. Specifically: let us say the TM performs task n a fraction F(n) of the time [for each n=1,2,3,...] and task n uses as its memory "tape," a subset of the cells on the whole tape -- specifically the cells that task n uses, are the integers k>0 such that G(k)=n. Here SUM_{j>0} F(j)=1, F(j)>0 for all j>0, G(k) is positive-integer-valued, and for each n>0 there exist an infinite set of integers k>0 with G(k)=n. THE PUZZLE: Design a "good" choice of the magic functions F() and G(), such that this time sharing scheme is maximally efficient. Unfortunately there are several possible measures of "efficiency" and it is not obvious which to use... including (as function of n and T) max latency before task n does another step, the min number of steps performed on tasks 1,2,...,n (combined) after time T, and the min number of steps performed on tasks 1,2,...,n (not combined, just take the worst one) after time T. A (PROBABLY POOR) SOLUTION just to get the ball rolling, I will propose one fairly concrete scheme. Imagine the "tape" of the TM is the infinite square spiral fedc 432b 501a 6789 in the pixelated plane, and G(n)=|y|, where y is the y-coordinate of tape cell #n, if that tape location is reserved for use by task #n. (The x-axis, y=0, is used for bookkeeping by the operating system which is "task #0.") Also imagine "time" as spiralling around (a second copy of) the same kind of spiral. The operating system works on task G(t)+1 for t^P steps, then advances t to the next spot on the time spiral. If the constant P is chosen large enough, then I believe this will work, i.e. it will get an infinite amount of private-TM-steps done on every task. This particular solution, however, involves F(n)=0 for all n, i.e. each job is worked on a fraction asymptotically 0 of the time. As opposed to, say, F(n)=zeta(2)/n^2. I do not know what the "best" solution to this puzzle is, and it is not even clear to me what "best" should mean exactly... but it nevertheless seems to me to be a pretty interesting puzzle. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)