A common way to measure working memory is called the “n-back” task. Presented with a sequential series of items, the person taking the test has to report when the current item is identical to the item that was presented a certain number (n) of items ago in the series. For example, the test taker might see a sequence of letters like
L K L R K H H N T T N X
presented one at a time. If the test is an easy 1-back task, she should press a button when she sees the second H and the second T. For a 3-back task, the right answers are K and N, since they are identical to items three places before them in the list. Most people find the 3-back condition to be challenging.
Of course, to folks who do streaming, this is easily recognized as a simple subcase of detecting a duplicate item in a stream (that problem allows n to vary over the entire stream), which in turn is a special case of the most frequent element estimation problem.
These are hard problems for sublinear space stream algorithms. It's interesting that they're taxing for human working memory as well.
To those who've recently taught finite state automaton, the n-back test is the standard way of showing that an n state NFA may require ~2^n states when implemented as a DFA:
ReplyDelete[01]*1[01]{n}