# Effective computation on linear data without random access

recently I've started thinking about caching problems in modern CPUs, where they struggle to adequately fetch program data (not instructions) in time, so that it can be computed further.
So then I came up with the idea, why don't we restrict random access on program data and make it all as a continuous stream (input and all eventual locals), which moves strictly in one direction through some "processing head", where you only have a possibility to read in some x amount of symols, write, let through and append symbols at the head position (this is a data stream, not an instruction stream).
The question is, whether you can effectively run computations in that system:
Is it possible to order all functions and allocate all local data/variables at compile time in such order that they will produce usable stream of data for all further functions, so that you will never need to "loop" the tape to access some particular element? (thus, emulating random access, by waiting for desired element to come by)
I've tried to look up this topic on the internet and found nothing. And maybe it is because this idea is obviously stupid, so no one bothers with it :)

• What have you tried? Have you tried going through an algorithms textbook to see which algorithms can be modified to be of this form? I think you'll quickly find that the answer is "no".
– D.W.
May 19, 2014 at 7:48
• What about binary search? May 19, 2014 at 7:54
• @D.W. I've answered below. May 19, 2014 at 19:30
• @Raphael binary search is a bitch. Most of recursive algorithms, which cannot be directly converted to a tail recursion are very problematic to realize with such "streaming". Many others are still ok, but it took a really long time to come up with datapath for these few algorithms that I've picked (Bubble Sort, FFT). May 19, 2014 at 19:33
• Now that I think about it in terms of "streaming", the answers to this question of mine may be interesting for you. Also, I think sorting with its $\Omega(n \log n)$ comparisons lower bound may be a good candidate for a counter example; you'd have to show that you have to revisit earlier elements, though. Another buzzword worth googline is "online algorithms". In other words, models similar to what you have in mind have been studied, and they are restricted in power compared to TMs. May 19, 2014 at 21:11